RogerBW's Blog

Advent of Code 2021 27 December 2021

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.

See also:
Advent of Code 2019
Advent of Code 2020


  1. Posted by Owen Smith at 03:24pm on 27 December 2021

    The best part of Perl is the regexp string parsing. There's a library that provides it in C. A sign to me of a language that has gone in the wrong direction is anything that doesn't copy Perl's regexp stuff, I'll add Rust to my "got it wrong" list. Only applies to languages designed after Perl obviously.

  2. Posted by Owen Smith at 03:42pm on 27 December 2021

    I find it interesting you do these things for fun, like the Perl weekly challenges. Given almost the entire of my job is writing code or diagnosing why code has gone wrong, I actively avoid writing code in my own time. I need to do something different so that I'm fresh for work. This does mean work dictates the languages I use so I'm not learning much new, but if I get well paid I don't regard that as a problem. I've spent most of my career writing C, with a sideline in various CPUs assembly (which I love doing) and briefly some C++ (which I hated).

  3. Posted by RogerBW at 03:49pm on 27 December 2021

    In Perl, essentially every problem is solved by regexps and hashes. In Rust, you have alternatives which may do a better job.

    The code I write for the Weekly Challenges and AoC is profoundly unlike the code I write for work, partly because I have more choice of language but also because the problem space is wider. This is feeding back into better overall coding skills, because I meet problems at home that I can't just solve with Standard Perl Tricks, so my repertoire of techniques becomes wider.

Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 2300ad 3d printing action advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech bayern beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 crime crystal cthulhu eternal cycling dead of winter doctor who documentary drama driving drone ecchi economics en garde espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 essen 2022 essen 2023 essen 2024 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo 2021 hugo 2022 hugo 2023 hugo 2024 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards mpd museum music mystery naval noir non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs ruby rust scala science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1