Sean McLemon | Advent of Code

2024-12-20 - Race Condition

(original .ipynb)

from collections import defaultdict

puzzle_input_str = open("./puzzle_input/day20.txt").read()
test_input_str = """###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############"""


def neighbours(track, r, c):
    max_r = len(track)
    max_c = len(track[0])
    candidates = (
        (r-1, c), (r+1, c),
        (r, c-1), (r, c+1)
    )
    for maybe_r, maybe_c in candidates:
        if maybe_r == r and maybe_c == c:
            continue
        if maybe_r >= max_r or maybe_r < 0:
            continue
        if maybe_c >= max_c or maybe_c < 0:
            continue
        yield (maybe_r, maybe_c)


def next_move(track, r, c, visited):
    for nr, nc in neighbours(track, r, c):
        if (nr, nc) in visited:
            continue
        if track[nr][nc] == "." or track[nr][nc] == "E":
            return (nr, nc)


def parse_input(input_str):
    track = input_str.splitlines()
    start, finish = None, None
    for r, line in enumerate(track):
        for c, section in enumerate(line):
            if section == "S":
                start = (r, c)
            elif section == "E":
                finish = (r, c)
    return track, start, finish


def time_race(track, start, finish):
    timed_track = [
        [None for section in line]
        for line in track
    ]
    
    visited = set()
    picoseconds = -1
    r, c = start
    
    while track[r][c] != "E":
        visited.add((r, c))
        picoseconds += 1
        next_r, next_c = next_move(track, r, c, visited)
        timed_track[r][c] = picoseconds
        r, c = next_r, next_c
    timed_track[r][c] = picoseconds + 1
    return timed_track


def is_track(timed_track, r, c):
    return timed_track[r][c] is not None


def find_cheats_from(timed_track, r, c, max_distance):
    queue = [
        (1, nr, nc)
        for nr, nc
        in neighbours(timed_track, r, c)
    ]
    visited = {(r,c)}
    while queue:
        distance, nr, nc = queue.pop(0)
        if (nr, nc) not in visited and distance <= max_distance:
            visited.add((nr,nc))
            if is_track(timed_track, nr, nc):
                saving = timed_track[nr][nc] - timed_track[r][c] - distance
                if saving > 0:
                    yield saving
            queue += [
                (distance+1, nr2, nc2)
                for nr2, nc2
                in neighbours(timed_track, nr, nc)
            ]
        

def find_cheats(timed_track, distance):
    for r, row in enumerate(timed_track):
        for c, col in enumerate(row):
            if col == None:
                continue
            yield from find_cheats_from(timed_track, r, c, distance)


def part_one(input_str, min_saving=100, distance=2):
    track, start, finish = parse_input(input_str)
    timed_track = time_race(track, start, finish)   
    
    cheats = find_cheats(timed_track, distance)
    cheat_counts = defaultdict(lambda:0)
    for time_saved in cheats:
        cheat_counts[time_saved] += 1

    return sum(
        cheat_counts[cheat]
        for cheat
        in cheat_counts
        if cheat >= min_saving
    )

assert 1 == part_one(test_input_str, 64)

print("part one:", part_one(puzzle_input_str))

part one: 1363

def part_two(input_str, min_saving=100):
    return part_one(input_str, min_saving, 20)

assert 3 == part_two(test_input_str, 76)

# 980343 is too low >:-(
print("part two:", part_two(puzzle_input_str))

part two: 1007186