Advent of Code 2024, Day 14

In part 2, I first tried printing all of the configurations and then grepping for horizontal lines, but that was too slow.

I then tried looking for contiguous horizontal lines in the code (instead of in an external pipeline). I did this with a recursive check at every coordinate, which made the check quadratic in the number of coordinates.

It only got faster when I checked pairs of adjacent coordinates instead of entire contiguous lines. This made the check linear in the number of coordinates.

For the threshold, I first picked 200 and then checked the result by manual inspection. It turns out that in my input, there were 268 horizontal adjacencies in the target frame, which was the first value greater than 66.

Part 1

import sys

def move(bots):
    for i, (px, py, vx, vy) in enumerate(bots):
        px, py = (px+vx+W)%W, (py+vy+H)%H
        bots[i] = (px, py, vx, vy)
    return bots

def safety_factor(bots):
    n = [[0, 0], [0, 0]]
    for px, py, _, _ in bots:
        if px == W//2 or py == H//2: continue
        n[px*2 > W][py*2 > H] += 1
    return n[0][0] * n[0][1] * n[1][0] * n[1][1]

bots = []
with open(sys.argv[1]) as f:
    for line in f:
        p, v = line.split()
        p, v = p[2:], v[2:]
        px, py = p.split(",")
        vx, vy = v.split(",")
        px, py, vx, vy = int(px), int(py), int(vx), int(vy)
        bots.append((px, py, vx, vy))

W = int(sys.argv[2]) if 2 < len(sys.argv) else 101
H = int(sys.argv[3]) if 3 < len(sys.argv) else 103

for _ in range(100):
    bots = move(bots)

print(safety_factor(bots))

Part 2

import sys

def move(bots):
    for i, (px, py, vx, vy) in enumerate(bots):
        px, py = (px+vx+W)%W, (py+vy+H)%H
        bots[i] = (px, py, vx, vy)
    return bots

def adjacencies(bots):
    locs = set([(px, py) for px, py, _, _ in bots])
    n = 0
    for x in range(W):
        for y in range(H):
            n += (x, y) in locs and (x+1, y) in locs
    return n

def display(bots):
    locs = set([(px, py) for px, py, _, _ in bots])
    for y in range(H):
        for x in range(W):
            if (x, y) in locs:
                print("#", end="")
            else:
                print(".", end="")
        print()

bots = []
with open(sys.argv[1]) as f:
    for line in f:
        p, v = line.split()
        p, v = p[2:], v[2:]
        px, py = p.split(",")
        vx, vy = v.split(",")
        px, py, vx, vy = int(px), int(py), int(vx), int(vy)
        bots.append((px, py, vx, vy))

W = int(sys.argv[2]) if 2 < len(sys.argv) else 101
H = int(sys.argv[3]) if 3 < len(sys.argv) else 103

i = 0
while True:
    bots = move(bots)
    i += 1
    if adjacencies(bots) > 100:
        display(bots)
        break
print(i)

2024-12-19