Day 24: Planet of Discord

---

Links:

• Puzzle on adventofcode.com
• Source Code

It was about time we finally got some cellular automata. I was really surprised by the tiny input size. I expected the second part to make something crazy out of it but I didn’t see the return of the recursive space coming.

I don’t have a lot to say about the first part. It’s cellular automata, call it game of life if you must, there’s already enough information about it out there.

I do have a somewhat funny story to tell though (it’s not really funny but please just bear with me). Just because I felt like it I decided to store the cells in a one-dimensional array.
I’m sure you’ve already heard about this but just to make sure, there is a bijection (one-to-one mapping) from a two- to a one-dimensional array. An element at (x, y) in two dimensions maps to the index (y * width + x) in one dimension.
Adding width to the index moves to the same column on the next row.
To go from one to two dimension it follow that $y = \lfloor \frac{index} {width} \rfloor$ and $x= index \bmod width$.

Many languages use this “trick” to store multidimensional arrays. They are laid out in row- or column-major order with some abstractions on top. In a way, even a one-dimensional integer array is a two-dimensional array of bits which is kept in row-major order in memory.

“This is boring, where is the funny part?”:
When counting the amount of bugs adjacent to a position I used the naive implementation of just checking the four indices (i + 1), (i - 1), (i + width), (i - width) in the array.
I wouldn’t blame you for not seeing the problem right away but imagine what happens when i is $width - 1$. In that case (i + 1) would no longer map to the desired (x + 1, y) but to (0, y + 1). In the example:

....A
B..#.
#..##
..#..
#....

A would be considered adjacent to B. That’s not what we want so I had to add a check for this. I guess the only lesson here is that you shouldn’t forget to check your bounds, even when you’re using Rust.

Apart from this hiccup nothing interesting happened while solving the first part so let’s move on to the second part.

I always love it when puzzles come back in an alternate form so of course I enjoyed the second part which brings back the recursive spaces from day 20. But this post is getting kind of long so I’ll keep this brief. Let’s first establish that the lower the level the further “out” the grid. The center position of the grid with level l contains the grid at level l + 1.

All we really need to change is the way we count neighbours of a position. When the position is on the outer border we need to consider the position touching it from the outer grid (l - 1). If the position is next to the center position (i.e. on the inner border) we need to consider all positions on the border touch that side from the inner grid (l + 1). We still count all the neighbours from the same grid like before.

We can collect the positions that need to be “toggled” (from empty to bug or vice versa) for each layer separately. It’s essential that we also do this for the levels above the highest and below lowest layer. Even though these layers are themselves empty, they have an inner or outer border with another layer which can be influenced.

This sounds a lot shorter than it actually is. There are a lot of cases to cover. The puzzle’s description does sound a bit more complex than it actually is though. There isn’t a lot that hasn’t already been done with cellular automate but this was a really creative puzzle and I thoroughly enjoyed it.

In other news, Clippy started complaining about the “cognitive complexity” of my trusty puzzle selection match statement. I saw this as a great excuse to finally get rid of it. Because I didn’t want to rewrite every single module I decided to use the same logic - more or less - but with macros this time. The macro I ended up with takes identifiers (the module names of the days) imports them (“mod day_xx”) and creates a function that builds a map from the puzzle identifier to the solver function. The puzzle identifier is the composition of the day and part (ex: day 5, part 2 = (5, 2)).

Instead of having 24 “mod day_xx” lines and another three lines for each day in the match statement now there’s only a macro invocation with the module names:

day_modules![
    day_01, day_02, day_03, day_04, day_05, day_06, day_07, day_08, day_09, day_10, day_11, day_12,
    day_13, day_14, day_15, day_16, day_17, day_18, day_19, day_20, day_21, day_22, day_23, day_24
];

Getting the correct solver function is as easy as getting the value from a map:

let solver = puzzles.get(&(day, part));
let result = solver(input);

40 lines instead of 148 is a convincing argument I think. Sayonara big old match statement, you served me well!

---

Overview
Previous day Next day