« posts | «« home

Day 5: Supply Stacks

View puzzle page »

Skip to the code?

If you’d like to read my solution first, the code is available on GitHub.

Puzzle 1

The input for this puzzle is in two parts. The first is a series of 9 stacks of ‘crates’ which must be moved around in a specific order, which forms the second part of the input.

The crate stacks take the form of:

[A] [C]
[B] [D] [E]
 1   2   3

Instructions take the form of move 1 from 2 to 3 where the first numeral is the number of crates to move, the second is the source stack, and the third is the destination stack. So the instruction reads as “move one crate from the second stack to the third”.

Hold on tight cos we’re going round the houses in this one.

Solution

The first problem to solve is reading in the stacks. We’re going to store them to lists. Python has some functions like deque which can operate like real stacks but we don’t actually need them to be real stacks.

There are 9 stacks, which are each a column. There are 8 rows, describing the crate at each layer of the stack. Sometimes these rows are empty for some stacks - some stacks have 8 crates but some only have 3.

Each row is 35 characters long ((4*9)-1). The crate on a stack is described as '[c] ' - note the trailing space. The space is omitted in the final stack (9) which gives us the 35-char length. This fixed pattern means we can loop and extract the crate at each stack, store it to a multi-dimensional array, and end up with a data structure that maps the crates.

from collections import defaultdict

crates = defaultdict(list)

with open("day5_input.txt", encoding="utf-8") as f:
    for line in f.readlines():
        if line.startswith(' 1') or line == '\n':
            continue
        row = [line[i:i+4].strip() for i in range(0, len(line), 4)]
        [crates[count+1].append(crate) for count, crate in enumerate(row) if crate != '']

I’m really leaning into some Python built-in and native functionality here so if you’re applying this logic in a different language, it might take more work.

First, the defaultdict creates an addressable dict-like object with a factory for a type. This means we can append straight into it, by index, without having to first create lists.

We have a couple of breaking conditionals. The first of these is catching the line which labels the stacks - this isn’t useful to us here. The next is catching the empty line which separates the stacks from the instructions. For either of these, we can just continue.

For each row in the stacks, we’re using a list comprehension to capture segments of 4 characters, which gives us the '[c] ' pattern from earlier - bracket, character, bracket, space. With this, we’ll pick up the newline character on the 9th column. To get rid of the whitespace and newline, we call strip on the result. We end up with something like ['[A]', '', '', '', '', '', '[B]', '[C]', ''] for each row.

We then want to append this row to the crates dictionary, adding 1 to the crates index so it’s not zero-indexed to match the move instructions. If the crate is empty, we don’t want it added to the stack so we insert a conditional for empty strings.

After consuming the stacks, we’re left with something like {1: ['[A]', '[B]', '[C]'], 7: ['[D]', '[E]'], 8: ['[F]', '[G]', '[H]'], 5:[...]}. The top crate in each stack is the leftmost element. The crates dictionary is not automatically sorted by key which we will need to account for later.

Now is time to consume and act on the move instructions. Each instruction is a string of format move CRATES from STACK to STACK. We can call split on the line to get a list that looks like ['move', '5', 'from', '3', 'to', '6']. We could just access the necessary elements by index but we’ll send them to variables for convenience. They’ll need to be integers for us to use them as indexes.

if line.startswith('move'):
    instruction = line.split()
    from_stack = int(instruction[3])
    to_stack = int(instruction[5])
    no_crates = int(instruction[1])

We start by adding a conditional below our other conditional which executes on the ‘move…’ lines. To identify which crates we need to move, we’ll slice out the portion (crates) of the list (stack). We need to reverse this slice to emulate the behaviour of popping off the stack - LIFO.

move = crates[from_stack][:no_crates]
crates_to_move.reverse()

This slice needs to be inserted at the front of the target list since we’re treating the leftmost element as the top of the stack. This can be done with a little operator abuse.

crates[to_stack] = crates_to_move + crates[to_stack]

Now the elements have been copied, we need to erase them from the source list. Once this is complete, we want to move to the next line, rather than repeat the row extraction from earlier.

del crates[from_stack][:no_crates]
continue

Now we can run through the loop and the product in crates will have our solution to puzzle 1 - the leftmost element in each list, ordered by the key. The easiest way to grab these out for a readable (and importantly copy-pastable answer) is with a join. We grab the 0th element from each list in crates, iterating through them from 1-9 using the range function to generate the lookup keys in the right order. The chained replace methods are just convenience to get rid of the brackets.

''.join([crates[i][0] for i in range(1, 10)])).replace('[', '').replace(']', ''

Puzzle 2

The second puzzle asks that we repeat the process but instead of treating the moves between lists as sequences of popping individual elements off the stack, instead we move the whole desired group of elements as one, retaining their original order.

Solution

This is surprisingly easy with our existing code. We simply remove the line which reverses the order of the crates_to_move. We were already moving the items as a group and reversing them to get the stack-popping-like order, so we just stop doing that.

...
crates_to_move = crates[from_stack][:no_crates]
# crates_to_move.reverse()
crates[to_stack] = crates_to_move + crates[to_stack]
...

We run our code again and the string output is our answer to puzzle 2.

Source Code

View the code on GitHub.

Would you like to read something else by me?

« «

» »

« posts | «« home