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
- If so, turn right
- 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:
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))
Of course. But in the end it boils down to: company does something I don't condone, so I don't give them money.