My Advent of Code 2024

I participated in Advent of Code this year.

If you’re not familiar with it, Advent of Code is a programming challenge that runs every year over the first 25 days of December. Each day, the organizer, Eric Wastl, posts a prompt. Each participant gets a unique bit of input and has to provide a solution generated using their unique input. Then, once you have provided the correct solution, a second phase of the problem is revealed. There’s never any new input, but a complication is introduced that requires more solving and generates a new solution. Each part of the problem earns you a “star,” for a total of 50 possible stars each year.

The two-phase design of each puzzle is the thing I find most interesting about AoC. Coding up solutions to little toy problems is fun (and the tougher coding challenges remind me of the undergrad problem sets I cut my teeth on, thanks Stan), but, as any working programmer can tell you, having to go back over working code and make it do something else is a much more realistic slice of coding life.

I’m no expert on AoC. 2024 was my first year, and there are people who have solved every problem for ten straight years at this point. But I did solve both parts of all 25 problems, so I wrote up these notes on my takeaways in general and my favorite 2024 problem in particular.

General Thoughts

Especially because of AoC’s surprise reveal structure, you’re generally better off taking a direct approach. Getting fancy, and especially trying to optimize prematurely, can land you in a world of regret. I fell prey to this a couple of times early this year.

However, once you get the second part of the problem, it is important to reconsider your approach. The closest I came to missing a second star was Day 13. My initial solution was a simple greedy algorithm, but it was unworkable for the second phase. I spent longer than I would like to admit trying to break the problem down into something that would still allow me to use my original solution. I had to step away and give myself a brain break before I realized that I was actually looking at a (quite simple) bit of linear algebra. Two equations, two unknowns, one embarrassed programmer.

I know a lot of people use AoC and other coding challenges as opportunities to learn new programming languages or to challenge themselves by using unconventional or even counterproductive tools and technologies. For example, bsky user Corvus completed AoC using GameMaker to generate some cool visualizations. I used Python, which is kind of easy mode, even if you restrict yourself to standard libraries, as I did. Maybe next year will be a good opportunity to venture into Go or Rust.

Honorable Mention - Swapped Ripple Carry Adder

Before I write about my favorite problem this past year, I want to give an honorable mention to Day 24. The first part of the problem involved computing the state of a network of binary logic gates (AND, OR, and XOR) based on a set of inputs. That’s a pretty straightforward setup.

Then came the twist. Part two revealed that the inputs were supposed to be interpreted as the binary digits (that is, the 1s and 0s) of two large numbers. The network itself was supposed to operate as an adder producing their sum (also in binary). However, somewhere in the network, five wires had been swapped, and the problem was to identify the five pairs which, when switched back, would make the adder work properly.

At this point, I noticed something interesting: there were only 222 gates in the network. That seemed small for a 45-bit adder, so I started working out how many gates you’d actually need. I found a five-gate module for handling each bit position with carries, and for the least significant bits, which don’t have a carry, two gates suffice. Adding it all up, 222 was exactly the right number. That couldn’t be a coincidence. Instead of searching blindly, I built a static analyzer that looked for that five-gate pattern for each cluster of input and carry bits and complained about the ones that didn’t match. I used that to swap the gates manually in the input file and ran it through my original solution to validate the results. Definitely not the fastest way to solve, but I’d like to think my old computer architecture professors would be proud.

My Favorite Problem - Imaginary Disassembly

The problem I enjoyed most this year was undoubtedly Day 17. The setup presented a simple machine language for a hypothetical 3-bit computer featuring eight instructions, three registers, and no addressable memory. The instruction set included:

• A conditional jump
• A modulo-8 operation
• An operation to XOR two registers
• A set of operations that divide registers by a power of 2
• An output operation

The input consisted of the initial state for the machine and a sequence of numbers to be used as a program. Unsurprisingly, the first part of the problem involved writing a little emulator to generate the output stream for the program. As I was working on the first part, I couldn’t help thinking ahead to the second part. With no way to change the program or initial state, I honestly did not know what to expect until I submitted my solution (which, incidentally, would have made those computer architecture professors proud, because it worked on the first go).

Then came the reveal: the program was supposed to be a quine—a program that generates its own source code as output. However, one of the initial register values needed to be changed to get the desired behavior (which, if you’re being a stickler, is bending the rules a bit for a quine), and the task was to find the smallest working value. Of course, you could try to approach this by brute forcing the register value, but that’s going to break down pretty rapidly. So, I started by “disassembling” the program into assembly by hand. The resulting pseudocode looked like this:

B := A mod 8  
B := B XOR 6  
C := A / (2^B)  
B := B XOR C  
B := B XOR 4  
OUTPUT B  
A := A / 8  
IF A != 0 THEN JUMP 0

The code processes the value in register A three bits at a time. Each iteration, it’s doing some bit munging between A’s three least significant bits and some of its other bits. Then it outputs the result of that munging, shifts A right by three bits, and repeats the loop until there’s nothing left.

So, the solution turns out to be pretty simple. The basic plan is to work backwards, building up a solution three bits at a time. The first iteration looks at which values of A from zero to seven will yield the final number in the program. Then, those values get shifted three bits to the left and the process is repeated for the next-to-last number, and so on.

Of all the AoC problems this year, this was the one that put the biggest smile on my face. It was clever, challenging, and ultimately not all that complicated. Thanks and congratulations to the organizers for ten years of challenges!

I’ve provided my actual code below. As proud as I am of it, I want to note that my priority was speed and efficacy. Under other circumstances, I would structure this code differently. I stored the emulator state in global variables for Part One, and it would have been a pain for me to do the right thing for Part Two and move that state into a structure that could be passed into the emulator for each run. So, no points for beauty here, but it did get the job done.

import sys

src_reg_A = int(sys.stdin.readline()[12:])
src_reg_B = int(sys.stdin.readline()[12:])
src_reg_C = int(sys.stdin.readline()[12:])
sys.stdin.readline() # Skip blank line
txt_program = sys.stdin.readline()[9:].rstrip().split(',')
program = [int(x) for x in txt_program]
reg_IP = 0
output = []

reg_A = None
reg_B = None
reg_C = None

def resetState():
    global reg_A
    global reg_B
    global reg_C
    global reg_IP
    global output

    reg_A = src_reg_A
    reg_B = src_reg_B
    reg_C = src_reg_C
    reg_IP = 0
    output = []

def decode_combo(operand):
    val = None
    if operand < 4:
        val = operand
    elif operand == 4:
        val = reg_A
    elif operand == 5:
        val = reg_B
    elif operand == 6:
        val = reg_C
    return val

def div_A(operand):
    divisor = 2 ** decode_combo(operand)
    return reg_A // divisor

def execute(opcode, operand):
    global reg_A
    global reg_B
    global reg_C
    global output
    match opcode:
        case 0: # adv
            reg_A = div_A(operand)
        case 1: # bxl
            reg_B = reg_B ^ operand
        case 2: # bst
            reg_B = decode_combo(operand) % 8
        case 3: #jnz
            if reg_A:
                return operand
        case 4: # bxc
            reg_B = reg_B ^ reg_C
        case 5: # out
            output.append(str(decode_combo(operand) % 8))
        case 6: # bdv
            reg_B = div_A(operand)
        case 7: # cdv
            reg_C = div_A(operand)

def runSim():
    global reg_IP
    while reg_IP < len(program) - 1:
        new_IP = execute(program[reg_IP], program[reg_IP + 1])
        if new_IP != None:
            reg_IP = new_IP
        else:
            reg_IP += 2

base_vals = [0]
while base_vals:
    base = base_vals.pop()
    solutions = []
    for i in range(8):
        checkA = (base << 3) + i
        resetState()
        reg_A = checkA
        runSim()
        if output == txt_program[-len(output):]:
            if len(output) == len(txt_program):
                print(f'SOLUTION FOUND {checkA}')
            else:
                solutions.append(checkA)
    if solutions:
        base_vals.extend(reversed(solutions))