RogerBW's Blog

I did Advent of Code again, and had a really good time. Spoilers.

Language choices:

• 2018: beginner Rust, floundered a lot, gave up after five days.
• 2019: Perl, completed
• 2020: Rust, but switching to Perl after two days; completed
• 2021: Rust… completed!

I've been doing the Perl Weekly Challenges in Rust all this year, and that's certainly helped me get used to the language.

I defied the temptation to do these in PostScript, which while it's great fun does lack many modern language features that I rather like having, which in turn makes it quite hard to do complex things in it. Rust is the language I'm working hardest on learning.

Looking at some other solutions, several people were happy to compile their puzzle inputs into their code; I wrote mine to read the puzzle input file (apart from anything else, string parsing in Rust is very different from the Perl I'm used to where you just throw everything at a regexp).

Day 3 (binary data) was a little fiddly, but day 4 (bingo) was the one that got suddenly crunchy with deep data structure manipulation.

Day 6 was the first one for which I felt clever. The question's presented to guide you into tracking individual fish timers: but all fish with the same timer value are functionally identical, so you can stick them in a single variable to indicate how many there are. This becomes a list: [a, b, c, ...] where a is the count of timer-0 fish, b is the count of timer-1, etc., ending at timer-8.

Then all I need do for each generation is to pull the first value, shift all the others down one place, push a 0 onto the end, then add that first value to the new slot 6 and slot 8. Simple! And Rust has a handy VecDeque for doing this with reasonable efficiency. (You could use a wrapping indexer value instead, but hey.) The output value is simply the sum of the nine values in the list. And therefore the only change I had to make for part 2 was the generation counter. (All right, I did switch to 64-bit integers.)

On day 8 I thought about writing a full solver, but instead just coded up the logic rules I'd worked out on paper instead. The order of letters is a distraction; represent each character as a bitmask where a = 1, b = 2, c = 4, etc.

Four numbers are easy because they have unique bit counts (1, 4, 7, 8 as the first part hinted).

Then use binary logic. digit-1 gives you a value for c OR f; digit-7 and not digit-1 gives you b OR d. (In each case you don't know which is which.)

Of the three six-bar characters, one contains only c; so take (c OR f) AND NOT (char) for each character, and the one that's non-zero ("matches") gives you the value of c (and therefore f). That's digit-6. (b OR d) AND (char) matches for digit-0, and the remaining one is digit-9.

Then for the five-bar characters: the one that matches both c and f is digit-3, c and not f is digit-2, f and not c is digit-5. Done!

Day 11 had some similarities with 9: a digit grid, and the need to evaluate neighbours. Mostly the challenge was in preventing an infinite loop. Part 2 was, I think deliberately, very nearly trivial given a working solution to part 1. (OK, it's a bit game-of-life-like. Never mind.)

Day 14 was a lot like day 6 – I thought about doing part 1 with a VecDeque, but even ten iterations would blow up to a megabyte multiplied by my input size, and it just seemed easier to keep track of the count of each sort of pair (this ended up being a HashMap of (char,char) to a u32 count, or in part two u128 just to be on the safe side). And of course one has to keep track of which pairs will be removed, because they all get removed before the new ones (which might duplicate them) are added. Then just count the occurrences of the first half of each pair, and add on one for the final character in the string, which remains constant all the way through the process.

Day 15 looked like Dijkstra, but I didn't have the details immediately in my mind, so I built a different exhaustive search algorithm… which on this set of input data turns out to be over 60× faster. That was a bit unexpected. (Clearly I did the Dijkstra badly!)

Day 16 caused even Roger to use recursion; I'm not normally a fan, but here it just seemed to make sense.

Day 18 was really quite tough; it started off looking like a binary tree, but all the next-left and next-right elements lent themselves to a linear representation instead; I ended up using regexps to calculate magnitude, which is obviously slower than it would have been if I'd used a tree parser there at the end.

Day 19 was the hardest yet and I struggled to find enthusiasm – like day 20 last year (the weekend problems tend to be tougher). Plugged through to the end though.

Day 21 was a pleasant jump from a trivial part 1 to a rather hard part 2 – a combination of a depth-first search with a multiplyer count and some fiddly looping to turn the resulting score map into the desired result.

Days 22-24 felt like a slog – 23 in particular, which was basically a fiddly path generator in front of fairly standard Dijkstra. I mean, I know pathfinding is a canonical moderately-hard problem, but it did seem as though there were an awful lot of it this time.

But in spite of a certain lack of enthusiasm towards the end I had a good time again, and I expect to be back next year. Perhaps more importantly, I think I have a greater facility with Rust than I did when I started. Definitely recommended if programming is a thing you enjoy, or if you would like it to be.