RogerBW's Blog

Advent of Code 2022 10 January 2023

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
  • 2022: PostScript, not quite completed

As someone pointed out: "this is hilariously stupid". The plan was to stick with PostScript until its limitations started being a real nuisance, then switch to Rust.

I really like PostScript. Yes, it's slow. Yes, it has profound limitations (like no variable-length arrays, and just the one stack). But it's good for my mental flexibility, and I get a solid sense of joy in getting something to work. (And I'm not competing on speed. Someone apparently got a correct solution to day 1 part 1 15 seconds after the problem was posted, and in the UK that's at five in the morning.)

The biggest drawback for me is the lack of regular expressions. Yes, there's a search to find substrings in a string, but that's about it; this meant things like the breakdown of, e.g., day 4's input was rather more work than it needed to be. (On the other hand, while I was doing that I was able to give some thought to the data structures I was going to use and manipulate later.)

The first few days were pretty easy, and more to the point the part 2 challenges didn't get much harder - 3 and 4 were basically "interpret the input in a slightly different way" and didn't need much code modification at all.

Day 7 was the first reasonably meaty one - not as hard as it looked, but I had some quite fiddly string parsing (always a weakness in PostScript) and had to bodge together a sort-by-length in a hurry. (Hmm, I wonder whether I should extend my quicksort algorithm to take two lists, of items and their sorting values, and return an array of the items sorted by value.)

For day 8 in another language I might have built a cleaner structure rather than duplicating code for four directions, but the duplication got the job done.

Day 9 got fiddly because PostScript arrays aren't really first-class items, so dealing with nested arrays becomes unnecessarily fiddly and verbose as one has to do the aliasing explicitly. (For several later days I ended up indexing on x * (large number) + y.)

Day 10 was quite refreshing; there's an off-by-one in the timing, but otherwise this seemed quite straightforward. I did it inside-out: rather than incrementing a clock by 1 per cycle, I ran through the operators, and stored the result in a time-indexed array.

In Day 11 the parsing frustrated me, and I switched to Rust to solve the problem (and work out what was going on in part 2; in theory Rust's BigInts should be able to handle it, but in practice it just takes too long, so I did it the proper way instead). Then I went back, fixed the parsing, and did it in PostScript too.

Day 12: ah, Edsger my old friend. Turns out that Dijkstra's Algorithm is the exact right choice, because for part 2 I just reverse it and get the path length from goal to all cells, which I then filter for zero-height. (If I were doing this in Rust, I'd use a collection type optimised for finding minimum values, such as PriorityQueue. But in PostScript I don't have one of those.)

Day 13 was definitely a "PostScript as exercise weights" day.

Part 1: I pretty much have to use token for parsing, which (I later realise) means wrapping the string in { } before feeding it in. (Also split on comma and rejoin on space, but I've already written library functions for that.) Not a huge recursion fan but it seems pretty clearly the right way to do it here.

Part 2: oh right. PostScript doesn't have a native sort. I wrote a quicksort a few months back, but it relies on being able to use the native comparators on array elements rather than being passed a function. So I bodge that in, and then dictstack overflows (too much recursion), so I build a comparator table (do every possible comparison and then use that as a sort comparator); then several rounds of bugfixing. (Actually it was probably a different error causing the overflow but I leave the comparator table in anyway.) Since for simplicity I end up sorting the packet index numbers rather than the packets as such, I just have to look for the indices of the target packets in the sorted output list.

Day 14: either this was easier to parse or I'm getting better at doing parsing in PostScript. Erk. But the actual coding was relatively easy.

Day 15: did you know PostScript arrays and dicts are traditionally limited to 65,536 entries? GhostScript is not quite that limited, but still can't stretch to the full span, so I ended up writing an interval collapser. Even then it takes A While to run (six and a half minutes on my test machine). As a Finnish car mechanic once said, "it's not pretty, but it'll get you home".

Day 16: this was the first one at which I thought about giving up; it just became a slog. But the major insight was the realisation that I didn't care about moves that didn't end in a valve opening, so I could build a distance map between the useful valves (start point and the ones with flow > 0), for which I should probably have used Floyd-Warshall but I still had Dijkstra in my head so I did that repeatedly, then use a depth-first search without repetition but with exit on the time constraint to find the highest-scoring result.

For part 2, instead of keeping the single highest value, I kept the highest for each path (defined as an unordered collection of useful valves and therefore keyed by bitmap of path element indices), then searched out the two non-intersecting bitmaps with highest joint total.

Day 17: I felt quite unenthusiastic reading the problem statement. The shapes were the discouraging bit, so I converted them to bitfields of each row: so #### is 15, ..# is 4. Yes, left side is low bit. It seemed like a good idea at the time, largely for reasons which ended up not being relevant. Sequence of bitfields is bottom to top. Also precalculate the width of each shape for the right side excursion check.

My "chute" is also one bitfield per row, extended upwards as needed. So a collision check is:

  • check for left and right side excursions
  • check for bottom edge excursion
  • check each row against that row of the chute for any overlaps (yay bitwise and).

Once a shape has come to rest, write its patterns into the chute and prune off any empty rows at the top.

For part 2, which feels like a classic AoC "now do it with a number that's far too large", I look for repetitions - I store the height and the jet index each time the rock index comes round to zero. When I see a jet index for the second time, I've got a periodicity. Then the total height is the sum of

  • height at the start of the periodicity
  • height gained by the periodicity × number of repetitions
  • height gained by the last fragment of the periodicity at the top

Day 18 was a lot less work than the last few. Part 1's nearly trivial with the right data structure, and part 2 is basically a DFS on that structure. (I thought about looking inside for empty cells with six neighbours, but then what about clusters of empty space?)

Day 19 was a Complete Pain, with lots of short-cuts needed, and more importantly the test data were not substantially smaller than the live problem data; several of my trial runs got comprehensively wrong answers, and it wasn't at all clear why. But attempt #5 (counting other languages) got the job done, which I ended up finishing off a few days later. Part 2 was a very minor tweak.

For day 20: PostScript uses a stack. And I don't have to care about the original start point, insofar as that's even meaningful. So: (1) have a stack of enumerated entries, (2) for each number 0..=n-1 find that entry ID and then roll the stack so that it's at the top, (3) pull it out into a temp var, (4) roll the stack the right number of places, (5) stick it back in. There was even a mod operator in the right place ready for part 2.

Day 21: it takes a lot to make me use recursion, but sometimes it feels like the obvious way and this was one of those days. Then part 2 was an expanding binary search using "-" as the root op.

Day 22: enjoyable part 1, but I looked at part 2 and suffered a total enthusiasm failure. I think the geometry puzzles have generally been my least favourite. Still haven't done part 2 at time of writing.

Day 23: it looks like Conway’s Life, but I’m glad to say it isn’t. In fact I end up with a fixed-size list of x, y coordinates, then build a second one of proposed moves, and have a hasher for those coordinate pairs so that I can easily see whether there’s something at a particular spot.

Day 24: another enthusiasm failure. I can see how I'll have to go about this, a Dijkstra where each node is (x, y, time), but I don't wanna.

Day 25: straightforward and refreshing.

If you're preparing for an AoC, on the basis of the past few years, I think you should be reasonably familiar with (in your chosen language or languages):

  • multidimensional arrays (or whatever your language of choice uses to substitute for them);

  • depth-first and breadth-first search;

  • Dijkstra or A* pathfinding (Dijkstra has worked for me but A* would probably be handy to know); it might well be worth finding or writing or learning a generic pathfinding module with lots of hooks so that you can have that separate from the specifics of the problem;

  • Conway's Life;

  • modular arithmetic at least as far as the Chinese Remainder Theorem;

  • breaking down a string into specific arguments.

I mostly enjoyed it, but I'll be back with a more serious programming language next year, probably Rust again. Thanks as always to Eric Wastl and the AoC team.

See also:
Advent of Code 2019
Advent of Code 2020
Advent of Code 2021

  1. Posted by Owen Smith at 02:55pm on 10 January 2023

    The problems AoC is asking you to solve are almost completely unlike anything I do in my job as a low level embedded programmer (almost entirely in C and various assemblers), and for that matter have ever done. Do they say what real world problems they're meant to be similar to? Do you have any feel for that yourself?

  2. Posted by RogerBW at 03:03pm on 10 January 2023

    No. I have no interest in relating these to real-world problems. Once in a while I'll need to do a DFS or muck about with modular arithmetic, but mostly this is an exercise in coding agility and enlarging one's mental toolbox.

    (Also, I enjoy programming. I fear a lot of programmers don't.)

  3. Posted by Owen Smith at 02:24pm on 11 January 2023

    I enjoy programming but I scratch that itch more than enough at work. Doing other things in my free time keeps me fresh for work, and I have no desire for programming in my own time. The downside is this makes it harder to enlarge my mental toolbox, but to be fair I'm 56 so my current toolbox may be sufficient to keep me gainfully employed until retirement.

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.

Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech aviation base commerce battletech 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 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