Jesper Dramsch , , read in 4 minutes

A yes, the vertical stacks are starting!

What is Advent of Code?

In this little series, I want to write about the thought processes I have behind solving the puzzles presented in Advent of Code.

During the Advent of Code small coding puzzles are presented with varying levels of difficulty. They're always Christmas-themed text puzzles where you help elves out of some mess to save the holidays. The puzzles are deliberately ambiguous to not bias puzzlers into a certain solution, they always have an example input in the text to explain some details and an input file for each day that comes in the form of a text file you can download. The solution is a simple number or a string you enter, which is checked by the website automatically. After you finish part 1, part 2 unlocks, which is a variation on part 2. This can be a little twist on part 1 or a large twist that changes the problem formulation into a problem that would take brute force solutions to compute longer than the heat death of the universe would take.

Find my solutions here:

These descriptions won't be a perfect narrative, but rather how I think about these problems and where I see different solutions. I apologise for the possibility of rambling!

The example input

I saw this one and immediately knew the parsing would be the most important.

The example had some sort of column structure and the after an empty newline, there are some instructions.

[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

The moves would be easy to parse. Regex will make easy work of those 3 numbers.

The implementation

First, I decided to target that newline. I wanted to "do it right" and have a data structure that uses the right amount of columns for the top part. So first I extracted the last number from the column numbering.

I knew I wanted to use a stack for each column, but technically Python doesn't have strict stacks. Python has a "double-ended queue" called deque() in the collections module. Why a stack? They're extremely fast to append and pop from, which is the main operation here, when moving things around.

For this implementation, I knew it would be important whether we move multiple containers in one, or one at a time.

So, one at a time. Perfect for a for loop.

Part Deux

Part two upgraded that cratemover to move stacks in bulk.

That means my crates are now moved in the wrong order.

I didn't want to re-write the entire thing, so instead I implemented a little intermediate storage: crane.

The slower crane moves piece by piece and the newer crane simply reverses that stack, but since it's just a queue, it's cheap to reverse before adding it to the new column.

Error Log

There are definitely more errors I made on this one. I should use deque() more often...

  • AttributeError: 'NoneType' object has no attribute 'group' messed up the regex and called .group when it was supposed to be .groups()
  • IndexError: string index out of range somehow messed up the indices. Different lines have different length, so I define ii dynamically instead.
  • for i, start, end in moves: ValueError: too many values to unpack (expected 3) mixed up stacks and moves when returning the parser function...
  • stacks[end-1].append(stacks[start-1].pop()) IndexError: pop from an empty deque didn't consider that stacks would be empty, gotta escape that.
  • Messed up the moving, so the example doesn't pass: AssertionError: assert 'ZMN' == 'CMZ'
  • Somehow messed up the parsing of the stacks. My standard parser strips the string, which doesn't work here.
  • ="\n") AttributeError: 'list' object has no attribute 'split' simply don't need to split if I have the parser set up right
  • Forget to delete debug print statements. Not an error but I definitely had my screen full of deques.
  • somehow got a None on the crane deque(). Let's investigate: stacks[end-1].extend(crane.reverse()) TypeError: 'NoneType' object is not iterable – ah yes, the deque().reverse() is in-place.
  • Mixed up the example and full data test results, so they failed, when the code worked.