Advent of Code 2022

by mark | 12 Nov 2023, 9:46 a.m.

I recently discovered Advent of Code, a bunch of puzzles with a Christmas theme that need to be solved by programming solutions. What I like is that the initial problem comes with a Part 2 which is either easy (if you did Part 1 sensibly) or a nightmare.

So here is what I thought of 2022's edition. Other ones as and when I complete them... 

I did 2022 in C, with a lot of flex and bison written to handle the inputs. Often flex actions were enough to do the puzzle, 

Day 1: Calorie Counting

Very simple. Add up some numbers with blank lines meaning take a subtotal and start again. You'll need to do a little sum for part 2. 

Day 2: Rock Paper Scissors

Again this is straightforward although the problem statement is a little tricky needing close attention. Again barely 20 lines of flex.

Day 3: Rucksack Reorganization

This involves splitting a string into two, identifying characters in common, assigning a score, and summing. Part 2 involves counting common items across lines which is a little tricky. 

Day 4: Camp Cleanup

I thought this was straightforward. Do you know what a proper subset is? And also what a non null intersection is? 

Day 5: Supply Stacks

The first one that needed some thought and resulted in a long solution, although most of that was due to me sticking with C so a hundred lines of malloc() and pointer chasing. The actual algo is very simple, and part 2 wasn't hard. 

First time I think C was a problem, as all I did was have list of pointers and easy to blow up. This will be a recurring theme. 

Day 6: Tuning Trouble

This was relatively easy. Scan through the text and determine whether the mild conditions on non repeating characters have been met. Didn't even need flex just in raw C.

Day 7: No Space Left On Device

Haha I remember this one. Basically build a tree and seek through it finding appropriate nodes. 

Difficulty is, of course, using C, so there's a lot of mallocing to do and some of the answers are filename sensitive. Very irritating. 

Also, of course, in the real world directories take up space themselves to store the linked list of contents (or however they store it depending on filesystems). A nice little puzzle all the same.

Day 8: Treetop Tree House

Oh this was fun. Form a map and determine running totals of where things can be seen in straight lines. I ended up doing a whole bunch of loops for this, and I'm sure there is a nice functional solution. 

Probably half my code is malloc(), free() and pointer chasing. 

Not too difficult thinking about it. 

Day 9: Rope Bridge

I really enjoyed this one, because it is how a whole bunch of computer games involving things like snakes and so on are implemented. Move a chain around and how often do certain links occupy certain spots?

Also I used flex to read the inputs, so it was a case of reading a line, doing it, and then reading the next one. 

I recall this being quite tricky. 

Day 10: Cathode-Ray Tube

Oh this was great. Inspired by how ancient console games wrote to the TV by timing the position of the CRT beam - they'd literally write bits to be immediately displayed or not. I don't know how they managed it. Doing dumb desktop stuff is hard enough. 

Solution was ultimately very short as you're either moving a dot or turning a pixel on but it is very precise. 

Part 1 was logging values at certain points; part 2 was drawing the screen. I didn't like the font he used. 

I did really enjoy this. Such a neat puzzle. 

Day 11: Monkey in the Middle

Ah. This. Actually wasn't too bad. A very annoying lex to set up the initial objects and then you are literally just doing what the instruction say. 

Also rediscovered how annoying C's qsort is. Pass in a function pointer... 

Day 12: Hill Climbing Algorithm

This was an exercise in 'do you know Dijkstra's Algorithm'? There are others like A* but the original and best works in essentially no time at all. 

Part 2 was a little trickier and needed an adapted approach 'Reverse Dijkstra' where you work back from the goal to the start. 

Again satisfying especially if you don't already know these things. 

Day 13: Distress Signal

This involved an actual parse so I brought out Bison to form the structure of the lists in the input file. Then some rudimentary tree walking to come up with the answer. For part 2 I cheated and just added the two additional nodes to the input. Worst bit was figuring out how to create a sort function for qsort but I already kind of had it from part 1. 

Day 14: Regolith Reservoir

Ah this one. Again much like computer games from the past letting gravity do stuff to falling particles. 

Wasn't too bad in the end. According to The Internet this is ackshually a delicate finite automata problem that is dead easy to solve if you are versed in such things. I did it grain by agonising grain instead. 

Day 15: Beacon Exclusion Zone

An irritating geometrical one. I didn't like it.

Day 16: Proboscidea Volcanium

The valves. Basically set up a graph and do a search for the optimal solution. 

Part 2 was rotten as you now had another entity and its actions to track. Rotten. 

Day 17: Pyroclastic Flow

This is just Tetris. However I cheated and eyeballed what the cycle length was and hard coded it. Doing it properly would involve saving state and I couldn't bring myself to do it. 

Day 18: Boiling Boulders

Flood filling for part 2, part 1 was almost like diffusion limited aggregation. Not too hard overall. But then...

Day 19: Not Enough Minerals

Horrible NP complete breadth first search. There are a couple of filters you can put in to trim the search space e.g. don't explore making a new factory if you couldn't possibly consume its output. But nasty

Day 20: Grove Positioning System

This was just permuting an input vector. Not too bad... 

Day 21: Monkey Math

Haha. Well. This was basically building an expression tree and evaluating it for part 1, so I broke out a calculator I had written in bison and adapted it slightly (needed lazy evaluation). 

Part 2 was essentially find an inverse operation. I didnt. I used binary search. Reset all nodes, adjust the input node based on the previous iteration, iterate until the output node is the desired value. Inverse operations have some delicacies with division of negative numbers and I didn't want to deal with it. 

I really enjoyed this one, mainly as I already had the answer written somewhere else.

Day 22: Monkey Map

Oh. Oh no.

This one. 

You basically have a cube mesh and you're following a point on it. 

But of course this is 3D. 

getting the mesh set up was absolutely, unbeliveably abysmal. Full of tricky off by one errors absolutely everywhere. Hardcoded edge mappings. 

Broke the part 1 answer solving it and, frankly, I don't care. Horrible. Glad it's over. Got a little paper cube still as a horrible memento. 

Day 23: Unstable Diffusion

Ah. This was easy after the brutality of day 22. Barely worth mentioning. 

Day 24: Blizzard Basin

Pathfinding again although with a constantly updating map. I ended up iterating the map with additional marks for "this cell can be occupied at this step somehow".

Part 2 was a bit of a pig but not too bad. Change the bool for a set of three states OUT, RETURN, FINAL and cease when the goal cell is FINAL. 

Day 25: Full of Hot Air

The last. A straightforward thing where numbers are expressed in powers of five, but using -2 -1 0 1 2 not 0 1 2 3 4. 

Overall - well I enjoyed it.