Advent of Code 2024, Day 11

For part 1, I used brute force. My original solution used list slicing and concatenation instead of list insertions. I find insertions harder to read, but I found out that they are faster when I tried to apply the same code to part 2.

For part 2, I knew I needed some kind of memoization. The Sierpisnki triangle, cellular automata, and bifurcating graphs came to mind. After I had the details right, I lost time because of a bug: instead of w, I had reused n as a variable name in my helper function. This messed up the recursion; it seemed as if my function flat out refused to be executed with (17, 25).

Part 1

import sys

def transform(L):
    i = 0
    while i < len(L):
        if L[i] == 0:
            L[i] = 1
        elif len(str(L[i])) % 2 == 0:
            s = str(L[i])
            w = len(s)
            a, b = s[:w//2], s[w//2:]
            a, b = int(a), int(b)
            L.insert(i, a)
            i += 1
            L[i] = b
        else:
            L[i] *= 2024
        i += 1
    return L

with open(sys.argv[1]) as f:
    L = [int(w) for w in f.read().split()]

generations = int(sys.argv[2]) if 2 < len(sys.argv) else 25

for i in range(generations):
    L = transform(L)
    print("progress", (i+1) / generations, "now at", len(L))
print(len(L))

Part 2

import sys

def after(i, n):
    if (i, n) in mem:
        return mem[(i, n)]
    if n == 0:
        r = 1
    elif i == 0:
        r = after(1, n-1)
    elif len(str(i)) % 2 == 0:
        s = str(i)
        w = len(s)
        a, b = s[:w//2], s[w//2:]
        a, b = int(a), int(b)
        r = after(a, n-1) + after(b, n-1)
    else:
        r = after(i*2024, n-1)
    mem[(i, n)] = r
    return r

with open(sys.argv[1]) as f:
    L = [int(w) for w in f.read().split()]

generations = int(sys.argv[2]) if 2 < len(sys.argv) else 75

mem = {}

s = 0
for i in L:
    s += after(i, generations)
print(s)

2024-12-11