Advent of Code: 2022 Day 5 in R

advent of code

puzzle

Published

September 10, 2023

Day 5: Supply Stacks

The expedition can depart as soon as the final supplies have been unloaded from the ships. Supplies are stored in stacks of marked crates, but because the needed supplies are buried under many other crates, the crates need to be rearranged.

The ship has a giant cargo crane capable of moving crates between stacks. To ensure none of the crates get crushed or fall over, the crane operator will rearrange them in a series of carefully-planned steps. After the crates are rearranged, the desired crates will be at the top of each stack.

The Elves don’t want to interrupt the crane operator during this delicate procedure, but they forgot to ask her which crate will end up where, and they want to be ready to unload them as soon as possible so they can embark.

They do, however, have a drawing of the starting stacks of crates and the rearrangement procedure (your puzzle input). For example:

    [D]    
[N] [C]    
[Z] [M] [P]
 1   2   3 

move 1 from 2 to 1
move 3 from 1 to 3
move 2 from 2 to 1
move 1 from 1 to 2

In this example, there are three stacks of crates. Stack 1 contains two crates: crate Z is on the bottom, and crate N is on top. Stack 2 contains three crates; from bottom to top, they are crates M, C, and D. Finally, stack 3 contains a single crate, P.

Then, the rearrangement procedure is given. In each step of the procedure, a quantity of crates is moved from one stack to a different stack. In the first step of the above rearrangement procedure, one crate is moved from stack 2 to stack 1, resulting in this configuration:

[D]        
[N] [C]    
[Z] [M] [P]
 1   2   3

In the second step, three crates are moved from stack 1 to stack 3. Crates are moved one at a time, so the first crate to be moved (D) ends up below the second and third crates:

        [Z]
        [N]
    [C] [D]
    [M] [P]
 1   2   3

Then, both crates are moved from stack 2 to stack 1. Again, because crates are moved one at a time, crate C ends up below crate M:

        [Z]
        [N]
[M]     [D]
[C]     [P]
 1   2   3

Finally, one crate is moved from stack 1 to stack 2:

        [Z]
        [N]
        [D]
[C] [M] [P]
 1   2   3

Part 1

The Elves just need to know which crate will end up on top of each stack; in this example, the top crates are C in stack 1, M in stack 2, and Z in stack 3, so you should combine these together and give the Elves the message CMZ.

After the rearrangement procedure completes, what crate ends up on top of each stack?

Well this will be much more challenging than the previous few puzzles. We need to read the visual representation of the different stacks into a usable data format, and then we need to parse the instructions.

I know I’m going to need at least some of the tidyverse packages, so I’ll load the whole thing now.

library(tidyverse)

Link to test_input.txt and the real input.txt.

First I’ll just read in the raw file as is.

test_data <- readLines("test_input.txt")
test_data

[1] "    [D]    "        "[N] [C]    "        "[Z] [M] [P]"       
[4] " 1   2   3 "        ""                   "move 1 from 2 to 1"
[7] "move 3 from 1 to 3" "move 2 from 2 to 1" "move 1 from 1 to 2"

Parsing Crates

I want to keep all of the lines that represent crates. I think I can disregard the line with the stack numbers because it won’t be easy to make that line up as far as R is concerned. I slice up to the line where the string is "" and subtract 2 – one for that line and one for the line of stack numbers.

crates <- test_data[1:(which(test_data == "") - 2)]
crates

[1] "    [D]    " "[N] [C]    " "[Z] [M] [P]"

I can now “read” that vector as if it’s a fixed width file. I first open a textConnection(), use read.fwf() on that connection, then close the connection. I use column widths of 4, to get the three characters in [D] as well as a trailing space.

connection <- textConnection(crates)
crates <- read.fwf(
  connection, 
  widths = rep(4, 3), 
  strip.white = TRUE, 
  na.strings = ""
  )
close(connection)

That’s something I can work with! Next I’m going to feed those stacks into vectors in a list, removing NAs and reversing order so that the first element in the list is the bottom of the stack.

stacks <- vector("list", ncol(crates))
for (i in seq_along(stacks)) {
  stacks[[i]] <- rev(crates[[i]])
  stacks[[i]] <- stacks[[i]][!is.na(stacks[[i]])]
}
stacks

[[1]]
[1] "[Z]" "[N]"

[[2]]
[1] "[M]" "[C]" "[D]"

[[3]]
[1] "[P]"

To translate: We had stack 1 having two crates: N on top and Z on bottom. We now have a list element that is a vector of c("[Z]", "[N]"), representing Z first as being in the bottom position. That way, I know that no matter how many crates are in any given stack, the first element is the bottom, the last element is the top, and length() is the number of crates.

Next I’m just going to clean up by removing the brackets from the crate labels. Notice that I have to escape the brackets themselves because brackets are part of regular expressions to denote a set of characters to be included. But because of the raw character syntax available since R 4.0.0, I can use r"{}" and avoid having to double-escape everything.

for (i in seq_along(stacks)) {
  stacks[[i]] <- str_remove_all(stacks[[i]], r"{[\[\]]}")
}
stacks

[[1]]
[1] "Z" "N"

[[2]]
[1] "M" "C" "D"

[[3]]
[1] "P"

Parsing Instructions

Now it’s time to read in the instructions from the file. We still have the test_data object that includes the full text of the input. I can now read it starting after the line that’s just the empty string.

instructions_vector <- test_data[(which(test_data == "") + 1):length(test_data)]
instructions_vector

[1] "move 1 from 2 to 1" "move 3 from 1 to 3" "move 2 from 2 to 1"
[4] "move 1 from 1 to 2"

I can make this into a data frame with columns number, from, and to by pulling out the numbers from each line. The regular expression I use indicates that I want to “capture” the first one or more digits that appear, then skip whatever comes next until the next set of digits, and then repeat for a third set of digits, which I expect to be the end of the string. So in total I’m pulling out three sets of digits, represented by the three (\d+) elements.

matches <- str_match(instructions_vector, r"{(\d+).*(\d+).*(\d+)$}")
matches

     [,1]            [,2] [,3] [,4]
[1,] "1 from 2 to 1" "1"  "2"  "1" 
[2,] "3 from 1 to 3" "3"  "1"  "3" 
[3,] "2 from 2 to 1" "2"  "2"  "1" 
[4,] "1 from 1 to 2" "1"  "1"  "2"

The first column of matches is the full string, and each column thereafter has the captured group. Now I’ll turn it into a data frame by converting those strings into numeric, converting to tibble, and renaming the variables.

instructions <- 
  apply(matches[, -1], MARGIN = 2, FUN = as.numeric) |> 
  as_tibble() |> 
  rename(number = V1, from = V2, to = V3) 
instructions

# A tibble: 4 × 3
  number  from    to
   <dbl> <dbl> <dbl>
1      1     2     1
2      3     1     3
3      2     2     1
4      1     1     2

Executing Instructions

I’ll start with just the first row of instructions: move 1 from 2 to 1. We expect to end up with stack 1 being c("Z", "N", "D") and stack 2 being c("M", "C").

move <- function(stacks, number, from, to) {
  for (i in seq_len(number)) {
1    stacks[[to]] <- c(stacks[[to]], stacks[[from]][length(stacks[[from]])])
2    stacks[[from]] <- stacks[[from]][-length(stacks[[from]])]
  }
  stacks
}

1: The stacks vector where the crates are moving to becomes the vector concatenated with the final element in the stacks vector where the crates are coming from.
2: The stacks vector where the crates are coming from gets reassigned to that vector minus the element at length(vector) – the final element.

Iterating over the instruction set:

execute_instructions <- function(stacks, instructions) {
  for (i in seq_len(nrow(instructions))) {
    stacks <- move(stacks, instructions$number[i], instructions$from[i], instructions$to[i])
  }
  stacks
}

execute_instructions(stacks, instructions)

[[1]]
[1] "C"

[[2]]
[1] "M"

[[3]]
[1] "P" "D" "N" "Z"

That looks like the example!

Now we just have to read off the crate letters on top of each stack.

read_crate_labels <- function(stacks) {
  labels <- character(length(stacks))
  for (i in seq_along(stacks)) {
    labels[i] <- stacks[[i]][length(stacks[[i]])]
  }
  paste(labels, collapse = "")
}

read_crate_labels(execute_instructions(stacks, instructions))

[1] "CMZ"

Putting It All Together

Let’s put it all together into a clean function.

parse_stacks <- function(input_data, num_stacks) {
  crates <- input_data[1:(which(input_data == "") - 2)]
  connection <- textConnection(crates)
  crates <- read.fwf(connection, widths = rep(4, num_stacks), strip.white = TRUE, na.strings = "")
  close(connection)
  stacks <- vector("list", ncol(crates))
  for (i in seq_along(stacks)) {
    stacks[[i]] <- rev(crates[[i]])
    stacks[[i]] <- stacks[[i]][!is.na(stacks[[i]])]
    stacks[[i]] <- str_remove_all(stacks[[i]], r"([\[\]])")
  }

  stacks
}

parse_instructions <- function(input_data) {
  instructions_vector <- input_data[(which(input_data == "") + 1):length(input_data)]
  number_matches <- str_match(instructions_vector, r"((\d+).*(\d+).*(\d+)$)")
  instructions <- 
    apply(number_matches[, -1], MARGIN = 2, FUN = as.numeric) |> 
    as_tibble() |> 
    rename(number = V1, from = V2, to = V3) 
  
  instructions
}

part_1 <- function(input_data, num_stacks) {
  stacks <- parse_stacks(input_data, num_stacks)
  instructions <- parse_instructions(input_data)
  stacks <- execute_instructions(stacks, instructions)
  
  read_crate_labels(stacks)
}

On the test data:

test_data <- readLines("test_input.txt")
part_1(test_data, 3)

[1] "CMZ"

That looks like what we want! Now let’s try it on the real data. I have looked at the input file and know that it has 9 stacks.

real_data <- readLines("input.txt")
part_1(real_data, 9)

[1] "ZWHVFWQWW"

Another gold star! This was a tricky one. Let’s see what part 2 has in store.

Part 2

As you watch the crane operator expertly rearrange the crates, you notice the process isn’t following your prediction.

Some mud was covering the writing on the side of the crane, and you quickly wipe it away. The crane isn’t a CrateMover 9000 - it’s a CrateMover 9001.

The CrateMover 9001 is notable for many new and exciting features: air conditioning, leather seats, an extra cup holder, and the ability to pick up and move multiple crates at once.

Again considering the example above, the crates begin in the same configuration:

    [D]    
[N] [C]    
[Z] [M] [P]
 1   2   3

Moving a single crate from stack 2 to stack 1 behaves the same as before:

[D]        
[N] [C]    
[Z] [M] [P]
 1   2   3

However, the action of moving three crates from stack 1 to stack 3 means that those three moved crates stay in the same order, resulting in this new configuration:

        [D]
        [N]
    [C] [Z]
    [M] [P]
 1   2   3

Next, as both crates are moved from stack 2 to stack 1, they retain their order as well:

        [D]
        [N]
[C]     [Z]
[M]     [P]
 1   2   3

Finally, a single crate is still moved from stack 1 to stack 2, but now it’s crate C that gets moved:

        [D]
        [N]
        [Z]
[M] [C] [P]
 1   2   3

In this example, the CrateMover 9001 has put the crates in a totally different order: MCD.

Before the rearrangement process finishes, update your simulation so that the Elves know where they should stand to be ready to unload the final supplies. After the rearrangement procedure completes, what crate ends up on top of each stack?

We’ll still need to get the crates and instructions out of the input data.

test_data <- readLines("test_input.txt")
stacks <- parse_stacks(test_data, 3)
instructions <- parse_instructions(test_data)

This time, we need to change the move() and execute_instructions() functions.

move_2 <- function(stacks, number, from, to) {
1  len_from <- length(stacks[[from]])
2  moving <- stacks[[from]][(len_from - (number - 1)) : len_from]
3  stacks[[to]] <- c(
    stacks[[to]],
    moving
  )
4  stacks[[to]] <- stacks[[to]][!is.na(stacks[[to]])]
5  if (number == len_from) {
    stacks[[from]] <- NA
  } else {
6    stacks[[from]] <- stacks[[from]][1:(len_from - number)]
  }

  stacks
}

1: I make a placeholder variable for the length of the from stacks just to save typing and visual clarity
2: I make a vector holding the elements that will be moved
3: The new to stacks will be a concatenation of the old stack and the vector of crates being moved.
4: If there was an NA in the to stack (i.e. if it had been empty prior to this move), remove the NA
5: If I’m moving the entire stack, I need to “save its place” with an NA. Otherwise, assigning it just c() will actually delete that element from the stacks list.
6: Otherwise, lop off the number of items from the from stack

i <- 1
stacks_1 <- move(stacks, instructions$number[i], instructions$from[i], instructions$to[i])
stacks_1

[[1]]
[1] "Z" "N" "D"

[[2]]
[1] "M" "C"

[[3]]
[1] "P"

i <- 2
stacks_2 <- move(stacks_1, instructions$number[i], instructions$from[i], instructions$to[i])
stacks_2

[[1]]
character(0)

[[2]]
[1] "M" "C"

[[3]]
[1] "P" "D" "N" "Z"

i <- 3
stacks_3 <- move(stacks_2, instructions$number[i], instructions$from[i], instructions$to[i])
stacks_3

[[1]]
[1] "C" "M"

[[2]]
character(0)

[[3]]
[1] "P" "D" "N" "Z"

i <- 4
stacks_4 <- move(stacks_3, instructions$number[i], instructions$from[i], instructions$to[i])
stacks_4

[[1]]
[1] "C"

[[2]]
[1] "M"

[[3]]
[1] "P" "D" "N" "Z"

execute_instructions_2 <- function(stacks, instructions) {
  for (i in seq_len(nrow(instructions))) {
    stacks <- move_2(
      stacks,
      instructions$number[i],
      instructions$from[i],
      instructions$to[i]
    )
  }
  
  stacks
}

stacks_final <- execute_instructions_2(stacks, instructions)
read_crate_labels(stacks_final)

[1] "MCD"

I had a lot of troubleshooting because I mixed up the order of arguments to move() in the execute_instructions() function, but I won’t belabor the point. We got the right answer for the example. Now to put it all together.

part_2 <- function(input_data, num_stacks) {
  stacks <- parse_stacks(input_data, num_stacks)
  instructions <- parse_instructions(input_data)
  stacks <- execute_instructions_2(stacks, instructions)
  
  read_crate_labels(stacks)
}

part_2(test_data, 3)

[1] "MCD"

Real data:

part_2(real_data, 9)

[1] "HZFZCCWWV"

Correct! This one was tough, but I really enjoyed it.

You can find all of my Advent of Code solutions on GitHub.