Advent of Code 2024, Day 6

For part 2, I thought about sharing information about cyclic states across obstacle positions, but whether a state will end up in a cycle or not depends on the position of the obstacle, so it wouldn’t work.

So I had to brute-force it, and the code was very slow. I read that others had the same problem. But I later read about two optimizations: use complex numbers for coordinates instead of pairs of integers, and only check states for repetition at turns instead of during straight walks. The resulting code was more than 100 times faster.

Part 1 (0.05 seconds)

import sys

def count_visited(lines, i, j):
    diri, dirj = -1, 0
    visited = {(i, j)}
    while True:
        newi, newj = i+diri, j+dirj
        if not 0 <= newi < len(lines): break
        if not 0 <= newj < len(lines[newi]): break
        if lines[newi][newj] == "#":
            diri, dirj = dirj, -diri
        else:
            i, j = newi, newj
            visited.add((i, j))
    return len(visited)

with open(sys.argv[1]) as f:
    lines = f.readlines()
    lines = [line.strip() for line in lines]

for i in range(len(lines)):
    for j in range(len(lines[i])):
        if lines[i][j] == "^":
            starti, startj = i, j
            break

print(count_visited(lines, starti, startj))

Part 2, with arrays (13 minutes)

import sys

def get_trail(lines, i, j, obsi, obsj):
    diri, dirj = -1, 0
    states = [(i, j, diri, dirj)]
    while True:
        newi, newj = i+diri, j+dirj
        if not 0 <= newi < len(lines): break
        if not 0 <= newj < len(lines[newi]): break
        if lines[newi][newj] == "#" or (newi, newj) == (obsi, obsj):
            diri, dirj = dirj, -diri
            states.append((i, j, diri, dirj))
        elif (newi, newj, diri, dirj) in states:
            return []
        else:
            i, j = newi, newj
            states.append((i, j, diri, dirj))
    return states

with open(sys.argv[1]) as f:
    lines = f.readlines()
    lines = [line.strip() for line in lines]

for i in range(len(lines)):
    for j in range(len(lines[i])):
        if lines[i][j] == "^":
            starti, startj = i, j
            break

trail = get_trail(lines, starti, startj, -1, -1)
candidates = set([(i, j) for (i, j, _, _) in trail])
s = 0
x = 0
for (i, j) in candidates:
    x += 1
    print("progress", x / len(candidates))
    s += get_trail(lines, starti, startj, i, j) == []
print(s)

Part 2, with complex numbers (7 seconds)

import sys

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

walls = set()
for i, line in enumerate(lines):
    for j, c in enumerate(line):
        if c == "#":
            walls.add(i + j*1j)
        elif c == "^":
            start = i + j*1j

max_i = len(lines)-1
max_j = len(lines[i])-1
def is_outside(pos):
    return not (0 <= pos.real <= max_i and 0 <= pos.imag <= max_j)

def get_trail():
    pos = start
    facing = -1
    tiles = {pos}
    while True:
        new = pos+facing
        if is_outside(new): break
        if new in walls:
            facing *= -1j
        else:
            pos = new
            tiles.add(pos)
    return tiles

def is_loop(obs):
    pos = start
    facing = -1
    after_turns = {(pos, facing)}
    while True:
        new = pos+facing
        if is_outside(new): return False
        if new == obs or new in walls:
            facing *= -1j
            if (pos, facing) in after_turns: return True
            after_turns.add((pos, facing))
        else:
            pos = new

candidates = get_trail() - {start}
print(sum(is_loop(obs) for obs in candidates))

2024-12-25