Advent of Code 2022: Day 5

If you haven't already, take a look at the prep work we did on day 0, and view the puzzle description on AoC.

Today, we're moving crates with cranes. Our puzzle input describes the initial stacks of crates and the moves we're to make with the crane.

    [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

Our puzzle inputs are getting more complicated! Though we're not quite to needing a PEG parser yet.

The stacks are the first component of our input. We can represent each stack with a list, of which there are a variable number. So we'll need to determine the number of lists from the input. Each stack always contains 3 characters—either a crate ([A]) or 3 spaces (). And stacks are separated by a space. Thus our total number of stacks is equal to the length of the first line of input, plus one (to account for the missing separator after the last stack), divided by four (the width of the stack plus the width of the separator).

And while populating the lists with crates, we'll be traversing the stacks top-down; we'll need to make sure to add elements to the beginning of the list instead of the end. The crates will be every 4^th character starting with the 2^nd character on each line. We can use Python's built-in string slicing to do this: line[1::4]. If the character is a letter, there's a crate. If it's a space, there's no crate.

The movement instructions are the second component of our input. Each line contains the number of crates to move, the 1-based index of the stack to move them from, and the 1-based index of the stack to move them to. We'll use our integer parsing routine from day 4 to parse these values, making sure to convert them to 0-based indices for our stack lists.

Our input contains both components. So we'll need to switch between the two as we parse. We can observe that stack lines will start with either an open bracket or three spaces, and movement lines will start with move. All other lines can be ignored.

import re
from solver import Solver
from typing import TypeAlias


def parse_integers(line: str) -> list[int]:
    integer_strs = re.sub(r"[^\d]", " ", line)
    return list(map(int, integer_strs.split()))


Crate: TypeAlias = str
Stack: TypeAlias = list[Crate]
Count: TypeAlias = int
From: TypeAlias = int
To: TypeAlias = int
Instruction: TypeAlias = tuple[Count, From, To]


class SupplyStacks(Solver):
    stacks: list[Stack]
    instructions: list[Instruction]

    def parse_input(self) -> None:
        stack_count = (len(self.input_lines[0]) + 1) // 4
        self.stacks = [[] for _ in range(stack_count)]
        self.instructions = []

        for line in self.input_lines:
            if line.startswith("[") or line.startswith("   "):
                self.parse_stacks(line)
            elif line.startswith("move"):
                self.parse_instruction(line)

    def parse_stacks(self, line: str) -> None:
        for crate, stack in zip(line[1::4], self.stacks):
            if crate != " ":
                stack.insert(0, crate)

    def parse_instruction(self, line: str) -> None:
        count, from_, to = parse_integers(line)
        self.instructions.append((count, from_ - 1, to - 1))

That will parse our input into stack lists and instructions:

>>> stacks
[
    ["N", "Z"],
    ["M", "C", "D"],
    ["P"],
]
>>> instructions
[
    (1, 1, 0)
    (3, 0, 2)
    (2, 1, 0)
    (1, 0, 1)
]

Part One

For part one, we're to apply the movement instructions, moving each crate one at a time. Once done, the desired output is the crate on top of each stack.

Since we'll be mutating the stacks, let's make a copy of them first so part two will have unmodified stacks to work with.

class SupplyStacks(Solver):
    ...

    def solve_part_one(self) -> str:
        stacks = [stack.copy() for stack in self.stacks]

        for count, from_, to in self.instructions:
            for _ in range(count):
                stacks[to].append(stacks[from_].pop())

        return "".join(stack[-1] for stack in stacks)

Testing it with the sample input produces the correct answer CMZ.

Part Two

The desired output for part two is the same as part one. The difference is, for each movement instruction we're going to move the crates together instead of one at a time. This is easy enough to do with slices.

class SupplyStacks(Solver):
    ...

    def solve_part_two(self) -> str:
        stacks = [stack.copy() for stack in self.stacks]

        for count, from_, to in self.instructions:
            stacks[to] += stacks[from_][-count:]
            stacks[from_] = stacks[from_][:-count]

        return "".join(stack[-1] for stack in stacks)

Testing it with the sample input produces the correct answer MCD.

You can try this solution in your browser with Pyodide.