Hung-Yi's LogoHung-Yi’s Journal

Advent of Code 2022: Day 5

A TypeScript solution for the Advent of Code 2022, Day 5 puzzle: stack manipulation, simulation, and a whole load of parsing.

Today’s puzzle asks us to model stacks of crates, then simulate using a crane to shuffle the crates around. After shuffling, we get the final answer by inspecting the tops of all the stacks.

This involves using the stack data structure and a lot of pushing and popping…or at least that’s what part 1 of the puzzle wants you to think. Once part 2 is revealed, the stack push and pop mental model starts feeling less than ideal, and we’re left with a more general solution that uses list splicing and reversing. Oh, and the input parsing is particularly challenging!

The puzzle input data looks something like this.

    [D]              ─┐
[N] [C]               ├─ stack data
[Z] [M] [P]          ─┘
 1   2   3           ─── stack IDs

move 1 from 2 to 1   ─┐
move 3 from 1 to 3    ├─ move data
move 2 from 2 to 1    │
move 1 from 1 to 2   ─┘

First we partition the input data into two sections, which are separated by a blank line. The first section is the stackData while the second section is the moveData. They’re entirely different, so they must be processed separately. We also take special care to single out the line (above the blank) that denotes the stackIds.

const lines: string[] = puzzleInput.split('\n');
const blankLinePosition = lines.findIndex(line => line === '');
const stackData = lines.slice(0, blankLinePosition - 1);
const stackIds = lines[blankLinePosition - 1];
const moveData = lines.slice(blankLinePosition + 1);

Now we parse the moveData into a list of moves that have an amount of crates, and a from and to direction. This is made a little easier by passing a regular expression to split(), letting us split the string on multiple tokens (e.g. “move ”, “ from ”, “ to ”).

Unfortunately, due use of the regex, the split result still contains parts that we’re not interested in. We can skip those by destructuring the array with blanks in the places that we’re not interested in.

const moves = moveData
  // split on either "move ", " from " or " to "
  .map(move => move.split(/(move | from | to )/))
  // use blanks in destructuring to skip unimportant parts
  .map(([,,amount,, from,, to]) => ({
    amount: parseInt(amount),
    from,
    to
  }));

Then we want the stackData parsed into a Map<string, string[]> (i.e. a lookup table of stacks as string[], keyed by the stack ID). But instead of parsing the data just once, we wrap it in a function makeStackMap() that produces a fresh Map on demand, since we are going to have to run the simulation more than once with the state reset.1

To handle the weird parsing requirement for the visually laid-out stacks, we inspect the stackIds line. By detecting in which places this line has valid stack IDs, we can look through the rest of the stackData lines using those place indices and get the letters for the corresponding stack.

const makeStackMap = () =>
  stackIds.split('').reduce(
    (stacks, stackId, ii) => {
      if (stackId?.trim() !== '') {
        // For each non-empty stack ID
        // get its place index (ii)
        stacks.set(
          stackId,
          // find all the letters in the
          // stack data in place ii
          stackData
            .map(row => row[ii]?.trim())
            .filter(x => !!x)
        )
      }
      return stacks;
    },
    new Map<string, string[]>()
  );

Define a helper function getTopLetters() to get the final answer of the puzzle from any given state of stacks: this is the top letter of all of the stacks in order, joined together as one string.

const getTopLetters = (stackMap: Map<string, string[]>) =>
  Array.from(stackMap.values())
    .map(stack => stack[0])
    .join('');

Now we write the simulate() function, which:

  1. Makes a fresh Map of stacks at the starting state;
  2. Loops through all the moves and performs them on the stacks;
  3. Returns the final answer from the tops of the stacks

The function takes a reverse boolean flag which indicates whether to reverse the order of the crates on the destination stack for any given movement.

const simulate = (reverse: boolean) => {
  const stacks = makeStackMap();

  for (const {amount, from, to} of moves) {
    const fromStack = stacks.get(from);
    const toStack = stacks.get(to);
    const transfer = fromStack.splice(0, amount)
    if (reverse) transfer.reverse();
    toStack.splice(0, 0, ...transfer);
  }

  return getTopLetters(stacks);
}

Now the only difference between part 1 and part 2 is whether the movements reverse order of the crates or not, so we call simulate() with true and false separately.

const part1 = simulate(true);
const part2 = simulate(false);

Final Solution

const lines: string[] = puzzleInput.split('\n');
const blankLinePosition = lines.findIndex(line => line === '');
const stackData = lines.slice(0, blankLinePosition - 1);
const stackIds = lines[blankLinePosition - 1];
const moveData = lines.slice(blankLinePosition + 1);

const moves = moveData
  // split on either "move ", " from " or " to "
  .map(move => move.split(/(move | from | to )/))
  // use blanks in destructuring to skip unimportant parts
  .map(([,,amount,, from,, to]) => ({
    amount: parseInt(amount),
    from,
    to
  }));

const makeStackMap = () =>
  stackIds.split('').reduce(
    (stacks, stackId, ii) => {
      if (stackId?.trim() !== '') {
        // For each non-empty stack ID
        // get its place index (ii)
        stacks.set(
          stackId,
          // find all the letters in the
          // stack data in place ii
          stackData
            .map(row => row[ii]?.trim())
            .filter(x => !!x)
        )
      }
      return stacks;
    },
    new Map<string, string[]>()
  );

const getTopLetters = (stackMap: Map<string, string[]>) =>
  Array.from(stackMap.values())
    .map(stack => stack[0])
    .join('');

const simulate = (reverse: boolean) => {
  const stacks = makeStackMap();

  for (const {amount, from, to} of moves) {
    const fromStack = stacks.get(from);
    const toStack = stacks.get(to);
    const transfer = fromStack.splice(0, amount)
    if (reverse) transfer.reverse();
    toStack.splice(0, 0, ...transfer);
  }

  return getTopLetters(stacks);
}

const part1 = simulate(true);
const part2 = simulate(false);

console.log("Part 1:", part1);
console.log("Part 2:", part2);
Part 1: CFFHVVHNC
Part 2: FSZWBPTBG

Footnotes:

1

It’s possible to write a “pure” solution using immutable data structures or with side-effect-free operations, but for simplicity’s sake I’m sticking with the mutable style today.