Advent of Code, Day 16-19

After a bit of a rough holiday season - travel and low motivation led to reduced coding time - I finally managed to solve the hardest of the Advent of Code puzzles so far: Day 19. Day 16 and 18 were pretty gnarly, too.

Day 16 (puzzle here):

This tricky puzzle required parsing a very long hexadecimal packet into its constituent binary sub-packets, interpreting each packet's header bits, and using that information to further (recursively) break down packets to perform mathematical and logical operations. Packets could be an expression of a literal value, or an operator containing sub-packets that could be either literal values or other operator packets.

My solution for day 16 on GitHub

What made this particularly tricky for me was figuring out how to pass values between stack layers in order to keep track of the length and/or count of sub-packets inside each operator packet. Once I managed to pass those values around, the problem became less intimidating and I was able to perform the required operations.

Day 18 (puzzle here):

This puzzle really tested my debugging skills, as there were a ton of edge cases to catch and account for. The premise was to add numbers, but each 'number' was actually a pair [x,y], where x and y are considered 'regular numbers.' Some examples of these 'numbers,' one per line:

[1,2]
[[1,2],3]
[9,[8,7]]
[[1,9],[8,5]]
[[[[1,2],[3,4]],[[5,6],[7,8]]],9]
[[[9,[3,8]],[[0,9],6]],[[[3,7],[4,9]],3]]
[[[[1,3],[5,3]],[[1,3],[8,7]]],[[[4,9],[6,9]],[[8,2],[7,3]]]]

As 'numbers' are added to each other, there were certain conditions that triggered a reduction, which itself had two possible steps. And, finally, once all of the 'numbers' were added up properly, there was a further calculation done on the resulting 'number' to get its magnitude.

My solution for day 18 on GitHub

I chose to mostly work with these 'numbers' as their string representation, which had upsides and downsides. Some checks, like whether a pair was nested a certain number of levels deep, were a little easier because I was able to keep a running tally of opening and closing brackets ([ and ]). However, performing operations on the regular numbers required type conversions into integers, as well as a number of checks to make sure two-digit numbers were parsed when necessary. There were also some nasty edge cases, like performing an operation on one particular string but leaving a matching string earlier or later in the sequence alone.

After what felt like dozens of tests, run-throughs, and bugfixes, I did finally manage to arrive at the correct puzzle answer. I thought that was a pretty wild puzzle, until I moved on to...

Day 19 (puzzle here):

This puzzle required mapping 3D space, given scanners that didn't know their own position and the beacons scattered through space (in this case, the deep ocean) that each scanner could detect. The key was finding pairs of scanners that had overlapping detection ranges, meaning each scanner in a pair detected 12 or more of the same beacons (albeit from their own orientation, which could have been rotated any number of times by 90 degrees on each axis).

My solution for day 19 on GitHub

I chose to keep track of scanners and beacons as class objects, making it easier to refer to specific properties of each object and to use object methods. The first task was to find a way to determine which scanners shared beacons with other scanners, and to do that, I matched scanners as parent and child (starting with scanner 0, at coordinates [0, 0, 0]). Part of this discovery was making sure no scanner was assigned to more than one parent; while many of the scanners shared beacons with multiple other scanners, limiting which ones were paired meant fewer conversions and comparisons later on.

One of the toughest parts of this particular puzzle was accounting for scanner axes to be mismatched (one scanner's x was another scanner's y or z), and also accounting for which direction a scanner faced on each of it's axes relative to those of it's parent.

I came up with multiple versions of code to both try to match scanners with shared beacons, and to determine a consistent way to relate scanners' coordinate systems to each other. For matching, I ended up with a series of nested dictionaries, keeping track of the sums and differences of every beacon's x, y, and z coordinate with those of every beacon from another scanner. The number of times a particular sum or difference showed up determined whether or not there were shared beacons between the two scanners, and my dictionary setup gave me enough information to determine a child scanner's position relative to its parent.

That same information also lent itself to the creation of a transformation 'matrix' for each scanner, in order to convert the child scanner's beacon coordinates into it's parent scanner's coordinate system. This took the form of

[[2, -1], [0, 1], [1, -1]]

where the three pairs related to the x, y, and z coordinates of a beacon, and the values in each pair represented which parent axis that coordinate transformed to, and what orientation conversion to apply. For the 'matrix' above, a child beacon's x coordinate is on the parent's z axis, and the child scanner is facing away from the parent scanner on that axis.

While this seems a little hack-y, I wasn't able to find or fathom a cleaner way to come up with these relationships. I did discover that the SciPy module contains actual matrices for doing transformation and rotation conversions, but applying these was beyond the ability of my tired brain as December wound down. So, I stuck with my simplistic method. A recursive call through the various chains of parent/child scanners gathered all the beacons into one list, converting them along the way so that a single dictionary of unique beacons could be compiled and counted.

The second part of the puzzle required knowing the absolute positions of all the scanners. With most of the legwork done already, it was fairly straightforward to apply transforms to each scanner's relative position recursively to determine it's absolute position relative to the origin scanner. From there, a simple calculation determined the distance between the two farthest-apart scanners.

Whew!

I know there's one more really tough puzzle coming up on day 23, but finally solving day 19 today has given me extra resolve to tough it out and complete all of the Advent of Code puzzles. Here's hoping it doesn't take much longer!