← Back View problem

Day 5 — Supply Stacks

Part 1

It’s day 5 and things are starting to get interesting! This one has easily taken me the longest to solve so far, but we got there in the end. Let’s get started.

The first thing we want to do is separate the move instructions from the crate configurations. We can destructure both values by splitting on a double newline.

const [cratesString, movesString] = input.split(/[\n\r]{2,}/g);

Next we’ll generate our set of moves. We’ll use split again to separate each line into an array, and then we’ll map over each move in the list, and break it down to a tuple that contains the amount, starting stack, and ending stack. We can use a regular expression and match to easily pull out the numbers from the string.

const moves = movesString
  .split("\n")
  .map((move) => (move.match(/\d+/g) ?? []).map(Number));

This will take an input like:

move 2 from 5 to 4
move 1 from 2 to 5

and transform it into a 3D array that looks something like:

[
  [2, 5, 4],
  [1, 2, 5],
]

Next we’re going to take the string representing the stacks, and parse it into another 3D array, this time as items in a row. The first step is to split the string by newline, and also slice off the last row, as they are just numbers labelling each stack.

let rows = cratesString.split("\n").slice(0, -1);

Now that we have the rows, my next thought was to split each row into individual items, so we have nice clean data to shuffle around when we implement the move commands. Admittedly this part took me the longest to figure out, due to the tricky regex I used to split the string. I’m sure there’s a better way to do this, but this is what I came up with.

let rows = cratesString
  .split("\n")
  .slice(0, -1)
  .map((row) => {
    const nonPaddedRowItems = (
      row.match(/( ?\[[A-Z]\] ?)|( {3} ?)/g) ?? []
    ).map((i) => i.trim().replace(/\[|\]/g, ""));

    return Array(9)
      .fill("")
      .map((_, i) => nonPaddedRowItems[i] || "");
  });

You might be thinking, “What’s with the nonPaddedRowItems variable?” This wasn’t strictly necessary, but unfortunately when I tried pasting the sample input into VSCode, it always strips all the trailing space from the first row of stacks. This causes the match call to omit some empty spaces that we want to keep around. My solution was to generate the items as is, and then map them on to an array with a fixed length of the total column count (9).

The regex itself is pretty juicy, and I quite frankly have no idea how optimal it is, but it does the job. Let’s take a closer look at it.

/( ?\[[A-Z]\] ?)|( {3} ?)/g;

Breaking it down a bit, the first step is to capture an optional space, an opening square bracket, a capital letter, a closing square bracket, and another optional space.

/( ?\[[A-Z]\] ?)/g;

This will match the items in the stack, and the spaces between them. The second part is to match 3 spaces, followed by another optional space. This will match the empty spaces in a stack.

/( {3} ?)/g;

This match call will take a string like:

[Z]     [P] [Q] [B]     [S] [W] [P]

and convert it to an array like this:

["[Z] ", "    ", "[P] ", "[Q] ", "[B] ", "    ", "[S] ", "[W] ", "[P]"];

Not bad! But we should tidy these up a bit. We’ll map over the items, trim all white space, and remove any square brackets.

const nonPaddedRowItems = (row.match(/( ?\[[A-Z]\] ?)|( {3} ?)/g) ?? []).map(
  (item) => item.trim().replace(/\[|\]/g, "")
);

Now we have a nice clean row of data.

["Z", "", "P", "Q", "B", "", "S", "W", "P"];

Rows are great, but all things considered, we actually want to be working in columns (aka stacks). Let’s write a quick function to transform an array of rows into an array of columns.

function rowsToCols(rows: string[][]): string[][] {
  const [row] = rows;

  return row.map((_, col) => rows.map((row) => row[col]));
}

This will transform an array of rows like

[
  ["A", "B", "C"],
  ["D", "E", "F"],
  ["G", "H", "I"],
];

into an array of columns like

[
  ["A", "D", "G"],
  ["B", "E", "H"],
  ["C", "F", "I"],
];

Now we can use this function to take our array of rows and turn them into columns. We’ll also now filter out any empty values, as we don’t need to worry about them.

let cols = rowsToCols(rows).map((col) => col.filter(Boolean));

Time to operate the crane! We’ll loop over each move, and perform some array manipulation on the columns to move the items around.

moves.forEach(([count, from, to]) => {
  // the commands use a 1-based index, but our array is 0-based
  from = from - 1;
  to = to - 1;

  const removed = cols[from].slice(0, count);

  cols[from] = cols[from].slice(count, cols[from].length);
  cols[to] = [...removed.reverse(), ...cols[to]];
});

First we use slice to make a copy of the items we’re moving to a new stack. We then set the value of the original stack to the slice that remains. Finally we spread our copied slice onto the new target, ensuring that we reverse it so the items end up stacked in the correct order.

Now all that is left to do is grab the top item of each column, and combine them into a string. We’ll bring back our old friend reduce to do this for us.

cols.reduce((result, col) => {
  result = `${result}${col[0]}`;

  return result;
}, "");

The list of crates that will end up at the top of each stack after all the movement commands is BZLVHBWQF 🏗️

Part 2

Part 2 of this puzzle is somehow even easier than yesterday’s part 2. We simply don’t reverse the items we are adding to the new stack!

Instead of

cols[to] = [...removed.reverse(), ...cols[to]];

we do

cols[to] = [...removed, ...cols[to]];

We once again have the correct answer: TDGJQTZSL 🫡

← Back View problem