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))
The reason I compare them to autocomplete is that they're token predictors, just like autocomplete.
They take your prompt and predict the first word of the answer. Then they take the result and predict the next word. Repeat until a minimum length is reached and the answer seems complete. Yes, they're a tad smarter than autocorrect, but they understand just as little of the text they produce. The text will be mostly grammatically correct, but they don't understand it. Much like a compiler can tell you if your code is syntactically correct, but can't judge the logic.