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
• 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.