Advent of Code 2024, Day 9

This was the hardest day so far, and surprisingly prone to bugs.

For part 1, I soon found a linear-time algorithm that simply runs through the line once, sums up the numbers along the way, and treats gaps by popping a file from the back and counting the file instead of the gap.

For part 2, I had two important insights:

• When moving a file from the back into a gap, you don’t have to replace the old location of the file with a gap (and/or join it to neighboring gaps): files can only move to the left, so once a file has been considered, its old location (and everything to its right) becomes irrelevant for further moves.
• You don’t have to actually move the file — updating its offset suffices. The order of elements is only relevant for finding a leftmost gap with sufficient size, and the gaps are already in order (and stay that way). This makes the solution constant-space.

In addition to (mistakenly) thinking I had to join gaps, I forgot that file id’s are unique and that files are contiguous, so I mistakenly thought I had to join files as well after moving them.

Other than that, there is nothing smart about my solution for part 2: it moves the files in quadratic time and then sums them up. There is probably a more efficient algorithm, but this one is good enough.

Part 1

import sys

def split(line):
    L = []
    offs = 0
    for i, c in enumerate(line):
        n, x = int(c), i//2
        if i % 2 == 0:
            L.append((offs, n, x))
        else:
            L.append((offs, n, None))
        offs += n
    return L

def poplast(L):
    offs, n, x, lastx = 0, 0, 0, 0
    while len(L) > 0 and (n == 0 or x == None):
        offs, n, x = L.pop()
    if n > 0:
        lastx = x
        n -= 1
    while len(L) > 0 and (n == 0 or x == None):
        offs, n, x = L.pop()
    if n > 0:
        L.append((offs, n, x))
    return L, lastx

def checksum(L):
    s = 0
    while len(L) > 0:
        offs, n, x = L.pop(0)
        for pos in range(offs, offs+n):
            if x != None:
                s += pos * x
            else:
                L, lastx = poplast(L)
                s += pos * lastx
    return s

with open(sys.argv[1]) as f:
    line = f.read().strip()

L = split(line)
print(checksum(L))

Part 2

import sys

def split(line):
    L = []
    offs = 0
    for i, c in enumerate(line):
        n, x = int(c), i//2
        if i % 2 == 0:
            L.append((offs, n, x))
        else:
            L.append((offs, n, None))
        offs += n
    return L

def move(L):
    for i in range(len(L)-1, -1, -1):
        print("progress", 1 - i/len(L))
        offs, n, x = L[i]
        if x == None or n == 0: continue
        for j in range(i):
            offs_gap, n_gap, x_gap = L[j]
            if x_gap != None or n_gap < n: continue
            L[i] = (offs_gap, n, x)
            L[j] = (offs_gap+n, n_gap-n, x_gap)
            break
    return L

def checksum(L):
    s = 0
    for (offs, n, x) in L:
        if x == None: continue
        for pos in range(offs, offs+n):
            s += pos * x
    return s

with open(sys.argv[1]) as f:
    line = f.read().strip()

L = split(line)
L = move(L)
print(checksum(L))

2024-12-12