Sean McLemon | Advent of Code

2024-12-18 - RAM Run

(original .ipynb)

%%time
from advent import dijkstra

puzzle_input_str = open("./puzzle_input/day18.txt").read()
test_input_str = """5,4
4,2
4,5
3,0
2,1
6,3
2,4
1,5
0,6
3,3
2,6
5,1
1,2
5,5
2,5
6,5
1,4
0,4
6,4
1,1
6,1
1,0
0,5
1,6
2,0"""


def parse_input(input_str):
    def wrapped():
        for line in input_str.splitlines():
            c, r = line.split(",")
            yield int(r), int(c)
    return list(wrapped())

            
def neighbours(r, c, max_r, max_c):
    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 build_graph(max_r, max_c, corrupted_bytes):
    graph = {}
    for r in range(max_r+1):
        for c in range(max_c+1):
            children = {}
            for neighbour in neighbours(r, c, max_r+1, max_c+1):
                if neighbour not in corrupted_bytes:
                    children[neighbour] = 1
            graph[(r,c)] = children
    return graph


def part_one(input_str, dest_r=70, dest_c=70, num_bytes=1024):
    corrupted_bytes = parse_input(input_str)
    graph = build_graph(dest_r, dest_c, corrupted_bytes[:num_bytes])
    return dijkstra(graph, (0,0), (dest_r, dest_c))
    

assert 22 == part_one(test_input_str, 6, 6, 12)

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

part one: 348
CPU times: user 3.14 s, sys: 3.82 ms, total: 3.14 s
Wall time: 3.15 s

from math import inf

def has_solution(dest_r, dest_c, corrupted_bytes):
    graph = build_graph(dest_r, dest_c, corrupted_bytes)
    return inf != dijkstra(graph, (0,0), (dest_r, dest_c))


def check_solution(dest_r, dest_c, num_bytes, corrupted_bytes):
    previous = has_solution(dest_r, dest_c, corrupted_bytes[:num_bytes-1])
    current = has_solution(dest_r, dest_c, corrupted_bytes[:num_bytes])
    if previous:
        if current:
            return -1
        return 0
    return 1


def part_two(input_str, dest_r=70, dest_c=70, num_bytes=1024):
    all_corrupted_bytes = parse_input(input_str)

    lower = num_bytes
    upper = len(all_corrupted_bytes) - 1
    pivot = lower + ((upper - lower) // 2)
    
    while upper != lower:
        result = check_solution(dest_r, dest_c, pivot, all_corrupted_bytes)
        if result == 0:
            return all_corrupted_bytes[pivot-1][::-1]
        if result < 0:
            lower = pivot
        else:
            upper = pivot
        pivot = lower + ((upper - lower) // 2)
            
    raise Exception("No solution found, wtf")


assert (6, 1) == part_two(test_input_str, 6, 6, 12)


print("part two:", part_two(puzzle_input_str))

part two: (54, 44)