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))

15 comments

I think your step 2 is incorrect. Traversing the direction you came from is perfectly legitimate. But if you move onto a location+heading that you traversed before, that is a loop.
- But if you move onto a location+heading that you traversed before, that is a loop.
  Which is the express goal of part 2.
  Conversely walking in the opposite direction would lead me right past any obstacle that cause me to turn. So it's not particularly useful.
  
  Well, since I solved it by allowing re-traversal in the opposite direction, perhaps you might want to re-think your assessment of my suggestion... whenever you get tired of being stuck on that problem.
- I'm only casting a ray to detect where turning right now would lead. So to stick with your example:
  
  .O.. -^+# #++. ..#.
  If the guard had come from the left and run this little loop I'd detect this location to place an obstacle.
  Alternatively, if I switch back to recursive rays, I'd detect this location a little later:
  
  .O.. .^.# #|.. .|#.
Can you add your current code to the question? Maybe it's an edge case you're missing.
- Done
I'd suggest doing a really naive solution first to check your algorithm: that is, build a whole new map with the new obstruction added along with all the others, then compute the path as in part 1 (but don't forget to check for a loop!)
That will get you the correct answer, and then you can check your desired algorithm in various cases to see where it goes wrong.
- This is what I just did. Ran in 4 seconds.
  I kept track of bumps into obstructions. If I've seen a bump before, I figure I'm in a loop and I bail.
I also got stuck on part 2 for a while. What does your code do when you run into a corner and have to turn twice on one spot?
- It just keeps turning. See 3.2. Worst case is it has to turn twice and walk back where it came.
  
  Okay, then do you account for having to put down an obstacle before joining back on the walked path?
I totally brute forced this one, and it only took about 2 seconds to run, so I call that a win.
Keep track of all points visited on part 1.
loop over them, placing an extra rock at that position each time through.
run part 1
if you ever end up at any position you had already visited while facing the same direction, then you're in a loop.
Otherwise, stop if you go off the map.