#i already made up a hexagonal map generating algorithm i should use it!

[mordcore]

me upon realizing that in order to make a video game i'm gonna have to program it 😭😭😭

i know how to program i just hate it!!!

i love programming i just don't know how to do it.

programming hurted me.

[a-coda]

Advent of Code

As a child, advent calendars always added to the sense of anticipation in the lead up to Christmas. In my day you would be lucky to get a small picture behind each of the doors. These days, children expect chocolates or sweets. My wife has once even had a "Ginvent Calendar", with gin behind each door.

This year I marked Advent by having a go at the "Advent of Code" which has Christmas-themed programming puzzles posted each day. Most days are in two parts, with an easier puzzle followed by a harder one. Traditionally, I've posted a (mostly ignored) programming puzzle to our development team each Christmas. Last year I just recycled one of the Advent of Code puzzles, but this year I suggested we attempt the whole thing. The puzzles are so well thought out, in comparison to my efforts, that it seemed pointless to compete.

In the end, several of the team had a go. Some of the puzzles were harder than others, but I managed to solve them all by Boxing Day. What follows are some personal anecdotes from the various days with some general thoughts at the end. Note that there are some spoilers and the notes won't mean much if you've not done the puzzles. So in this case just skip to the end.

a sum-finder. I implemented the search tree via recursive calls. I drifted into using Python right from the start. It just felt like the easiest way to hack the puzzles quickly. In the past I had thought about using the puzzles to learn a new language. A colleague had done that with Rust in a previous year. Despite these good intentions, expediency took a firm hold. That said, in several puzzles I would have liked immutable collections or at least Lisp-style lists.

a pattern counter. Not that interesting except patterns were emerging in the programs themselves. Regular expressions got used a lot to read in the puzzle data. I learnt about things like match.group(1,2,3) which returns a tuple of the first three match groups, so you don't have to write (m.group(1), m.group(2), m.group(3)).

a grid tracer. The first interesting one because it was unfamiliar. Some other patterns started emerging: problem parameters got promoted to command line arguments, and data structure printers got hacked to help debugging. These two were often added between part 1 and part 2 of each problem.

a data validator. This felt like a bit of a slog. It was mostly about capturing the validation rules as code. Even though I made a point of reminding myself at the start that re.search doesn't match the whole string I still forgot it later. Duh.

an indexing problem. I patted myself on the back for realizing that the index was a binary number (or pair of binary numbers as I did it). At this point the solutions were still neat and I would do a little code golfing after the solution to tidy them up a bit and make them more concise.

another pattern counter. Pre-calculating some things during data reading kept the later code simple.

a recursive calculator. This was one of those puzzles where I had to reread the description several times to try and understand what it was asking for. It entailed a slightly tricky recursive sum and product, which was again made easier by creating more supporting data structures while reading the input data.

an interpreter. Probably my favourite individual puzzle because it was so sweet, especially after a bit of refactoring to make the language more data-driven.

another sum-finder. I found I didn't particularly like these.

an order-finder. This was the first one that made me pause for thought. An overly naive search algorithm from part 1 hit a computational complexity wall in part 2. I beat the problem by realizing that the search only had to be done on small islands of the data, but a colleague pointed out there was a better linear solution. The code was starting to get a bit ragged, with commented out debugging statements.

the game of life. The classic simulation but with some out-of-bounds spaces and some line-of-sight rules. It helped to print the board.

a map navigator. I liked this one even though I forgot to convert degrees to radians and that rotation matrices go anti-clockwise. I even introduced an abstract data type (ADT) to see if it would simplify the code (I'm not sure it ever did - I mostly used lists, tuples, strings, and numbers). The second parts of the puzzles were starting to get their own files now (usually bootstrapped by copying and pasting the first part's file).

a prime number theorem. I actually got stalled on this one for a bit. It eventually turned out I had a bug in the code and was missing a modulus. In effect I wasn't accounting for small primes far to the right. I left the puzzle and went on to complete a couple of others before coming back to this one. I checked what I was doing by Googling for hints, but in the end I had to take a long hard look at the data and find my own bug.

some bit twiddling. Part 1 felt like I found the expected bitwise operations, but part 2 felt like I was bashing square pegs into round holes.

a number sequence problem. Another pat on the back, this time for keeping a dictionary of recent occurrences and not searching back down the list of numbers each time. Another recurring pattern is evident: running a sequence of steps over the data. I liked to code the step as its own function.

a constraint solver. A nice one about labelling fields that satisfy the known constraints. Half the code was parsing the textual rules into data.

another game of life simulation. This time it was in more dimensions. I generalized from 3 dimensions to N instead of just doing 4. This made it more of a drag. I started naming auxiliary functions with placeholder names (social services should have been called). Also, I tacked on extra space along each dimension to make room at each step. This felt very ugly. I should have used a sparser representation like I did for day 24.

an expression evaluator. I used another actual ADT and wrote a simple but horrible tokenizer. The evaluator was okay but I hacked the precedence by inserting parentheses into the token stream. Don't try this at home kids.

another pattern matcher. Probably my biggest hack. My code compiled the pattern rules into a single regular expression. This was cute but meant the recursive rules in part 2 needed special treatment. One rule just compiled into a repeated pattern with +. Unfortunately, the other rule entailed matching balanced sub-patterns, which every schoolchild knows regular languages can't do. Perhaps some recursive pattern extensions might have worked, but I assumed there would be no more than 10 elements of the sub-patterns and compiled the rule into a large alternative of the possible symmetrical matchers. Yuck.

a map assembler. I did this one the most methodically. It had proper comments and unit tests. Overall it took the most code but perhaps it was just dealing with all the edge cases (ba dum tss). But seriously, it seemed to take a lot of code for rotating and flipping the tiles even after knowing how they must be connected. So probably there was a better approach. It was still satisfying the see the answer come out after all that work. Curiously, this one involved little debugging. I wonder if perhaps there is some connection between preparation and outcome?

a constraint solver. I tried a dumb approach first based on searching all the possible bindings. That didn't look like it was terminating any time soon. So I reverted to a previously successful technique of intersecting the associations and then then refining them based on the already unique ones.

a recursive card game. This card game playing puzzle seemed to be going okay, but the real data didn't converge for part 2. Had a quick Google for a hint after battling with it for a while, and the first hit was from someone who said they'd misread the question. Sure enough I had too. My recursive games were on the whole deck instead of the part dictated by the cards played. Duh. The description was clear enough and included a whole worked game. I just hadn't read it properly. It still seemed to need some game state memoization to run tolerably fast.

a circular sequence. Took three attempts. A brute force approach using an array was good enough for part 1, but no way was it going to work on part 2. Even optimizing it to use ranges was still 'non-terminating' for the array-based solution. So I Googled for a little inspiration and found the phrase "linked lists" and slapped my forehead hard. I switched to a dictionary of labels to labels and the solution popped out very easily, without any further optimization. Embarrassing. Was it time to ceremonially hand in my Lisp symbol and fall on a sharpened parenthesis?

another game of life. This one sounded neat because it was about a hex grid, but I didn't know how hex grids are usually indexed. So for the first time I did a little bit of general research at the start. Turns out there are a bunch of ways to index a hex grid. I opted for using 3-axes as that seemed natural despite the redundancy. The map itself was just a dictionary of locations. I should have looked up how to have structured dictionary keys in Python (implement __hash__) but I couldn't be bothered so I (look away now) serialized and deserialized the locations to and from strings. I still had a bug which I couldn't find until I hacked a crude hex board printer and realized I wasn't carrying the unchanged cells over from one iteration to the next.

a cryptographic puzzle. Came out quite short but only after some faffing around. Main trick seemed to be to keep the transformation ticking along instead of recalculating it from scratch each time. There was slight disappointment (tinged with relief) that there was no part 2.

Some general lessons I felt I (re)learned:

Read the questions very carefully, then reread them.

Try and use terms from the questions. Don't invent your own terminology and then have to map back and forth.

Make the trace output exactly like the examples to help comparison.

Next time I'd consider using BDD to turn their examples directly into tests. Next time.

Try the problem for a while by yourself, then think about it offline, and only then Google for hints.

Next time I'd consider using some form of source control from the start, or just a better set of file naming conventions.

Regular expressions go a long way, but can then they can get in the way.

Next time I'll consider doing it using a language I'm learning.

Sometimes when you get stuck you have to start again.

During some low moments it all felt like make-work that I'd inflicted on myself, but in the end it was a nice set of training exercises. I'd encourage others to have a go at their leisure.

"Practice is the best of all instructors." -- Publilius Syrus