Sean McLemon | Advent of Code

2024-12-06 - Guard Gallivant

(original .ipynb)

Day 6 puzzle input is a little 2D of empty space, obstacle and a guard (".", "#" and "^" respectively), mine is here). Part 1 involves following a set of rules governing the guard's movement and identifying the number of distinct places he visits before leaving the area. Part 2 involves finding the number of places you can add an obstacle to so that the guard ends up in a loop.

puzzle_input_str = open("./puzzle_input/day6.txt").read()
test_input_str = """....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#..."""


directions = (
    (-1, 0),
    (0, 1),
    (1, 0),
    (0, -1)
)


def parse_input(input_str):
    grid = []
    start_r, start_c = None, None
    for r, row in enumerate(input_str.splitlines()):
        maybe_start_c = row.find("^")
        if maybe_start_c > 0:
            start_r = r
            start_c = maybe_start_c
        grid.append([c for c in row])
    return (start_r, start_c, grid)


def out_of_bounds(grid, r, c):
    if r < 0 or c < 0:
        return True
    if r >= len(grid) or c >= len(grid[0]):
        return True
    return False


def is_guard(grid, r, c):
    return grid[r][c] == "#"


def try_move(grid, r, c, direction):
    dr, dc = directions[direction]
    next_r, next_c = r+dr, c+dc
    
    if out_of_bounds(grid, next_r, next_c):
        return None
    
    while is_guard(grid, next_r, next_c):
        direction = (direction + 1) % len(directions)
        dr, dc = directions[direction]
        next_r, next_c = r+dr, c+dc
    
    return (next_r, next_c, direction)
        
    
def part_one(input_str):
    r, c, grid = parse_input(input_str)
    direction = 0
    positions = {(r,c)}
    
    while True:
        next_move = try_move(grid, r, c, direction)
        if not next_move:
            break
        r, c, direction = next_move
        positions.add(
            (r,c)
        )
    
    return len(positions)


assert 41 == part_one(test_input_str)

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

part one: 5305

from copy import deepcopy

def add_obstruction(grid, obstruction):
    new_grid = deepcopy(grid)
    r, c = obstruction
    new_grid[r][c] = "#"
    return new_grid
    

def part_two(input_str):
    start_r, start_c, grid = parse_input(input_str)
    count_positions = 0
    
    potential_obstructions = {(start_r, start_c)}
    r, c, direction = start_r, start_c, 0
    while True:
        next_move = try_move(grid, r, c, direction)
        if not next_move:
            break
        r, c, direction = next_move
        potential_obstructions.add((r,c))
    
    while potential_obstructions:
        visited = {(start_r, start_c, 0)}
        obstruction = potential_obstructions.pop()
        new_grid = add_obstruction(grid, obstruction)
        r, c, direction = start_r, start_c, 0
        while True:
            next_move = try_move(new_grid, r, c, direction)
            if not next_move:
                break
            if next_move in visited:
                count_positions += 1
                break
            r, c, direction = next_move
            visited.add(next_move)
    
    return count_positions


assert 6 == part_two(test_input_str)

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

part two: 2143