7mo ago

Stuck on day 6, part 2

I'm not looking for a solution or even code, just a hint. Here's what I currently do:

Add the current position and heading to the recorded path
Check if turning right would lead back onto the recorded path in the same direction we walked it before
Check if the next field is obstructed
1. If so, turn right
2. Repeat until no longer blocked
Update current position

This approach works fine for the unit test, but yields a result too low for the puzzle input. I tried adding recursion to the party check, but even 20 levels of recursion didn't sufficiently increase the amount of options found, suggesting I'm missing a mechanism to identify them.

Any clues?

Current state of affairs:

 python

    
from math import sumprod
from operator import add
from pathlib import Path


def parse_input(input: str) -> list[list[int]]:
    return input.strip().splitlines()


def find_guard(world: list[list[int]]) -> tuple[int]:
    for y, line in enumerate(world):
        x = line.find("^")
        if x > -1:
            return (y, x)
    return (-1, -1)  # No guard


def turn(heading: tuple[int]) -> tuple[int]:
    mat = [(0, 1), (-1, 0)]
    return tuple([sumprod(col, heading) for col in mat])


def step(pos: tuple[int], heading: tuple[int]) -> tuple[int]:
    return tuple(map(add, pos, heading))


def is_blocked(world: list[list[str]], guard: tuple[int], heading: tuple[int]) -> bool:
    pos = step(guard, heading)
    try:
        return world[pos[0]][pos[1]] == "#"
    except IndexError:
        return False


def cast_ray(
    world: list[list[int]], start: tuple[int], heading: tuple[int]
) -> list[tuple[int]]:
    pos = step(start, heading)
    ray = []
    try:
        while world[pos[0]][pos[1]] != "#":
            ray.append(pos)
            pos = step(pos, heading)
    except IndexError:
        # Left the world
        ...
    return ray


def part_one(input: str) -> int:
    world = parse_input(input)
    guard = find_guard(world)
    heading = (-1, 0)
    while (
        guard[0] >= 0
        and guard[0] < len(world)
        and guard[1] >= 0
        and guard[1] < len(world[guard[0]])
    ):
        while is_blocked(world, guard, heading):
            heading = turn(heading)
        world[guard[0]] = f"{world[guard[0]][:guard[1]]}X{world[guard[0]][guard[1]+1:]}"
        guard = tuple(map(add, guard, heading))
    return sum([line.count("X") for line in world])


def part_two(input: str) -> int:
    world = parse_input(input)
    guard = find_guard(world)
    heading = (-1, 0)
    path = {}
    options = 0
    while (
        guard[0] >= 0
        and guard[0] < len(world)
        and guard[1] >= 0
        and guard[1] < len(world[guard[0]])
    ):
        path.setdefault(guard, []).append(heading)
        turned = turn(heading)
        if turned in path.get(guard, []) or turned in [
            d
            for p in set(cast_ray(world, guard, turned)).intersection(set(path.keys()))
            for d in path[p]
        ]:
            # Crossing previous path and turning would cause us to retrace our steps
            # or turning would lead us back into our previous path
            options += 1
        while is_blocked(world, guard, heading):
            heading = turned
        world[guard[0]] = f"{world[guard[0]][:guard[1]]}X{world[guard[0]][guard[1]+1:]}"
        guard = tuple(map(add, guard, heading))
    return options


if __name__ == "__main__":
    input = Path("input").read_text("utf-8")
    print(part_one(input))
    print(part_two(input))