12
Stuck on day 6, part 2 (sh.itjust.works)
submitted 2 weeks ago* (last edited 2 weeks ago) by Chais@sh.itjust.works to c/advent_of_code@programming.dev

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

  1. Add the current position and heading to the recorded path
  2. Check if turning right would lead back onto the recorded path in the same direction we walked it before
  3. Check if the next field is obstructed
    1. If so, turn right
    2. Repeat until no longer blocked
  4. 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))
you are viewing a single comment's thread
view the rest of the comments
[-] Pyro@programming.dev 2 points 2 weeks ago

Can you add your current code to the question? Maybe it's an edge case you're missing.

this post was submitted on 06 Dec 2024
12 points (100.0% liked)

Advent Of Code

920 readers
64 users here now

An unofficial home for the advent of code community on programming.dev!

Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

AoC 2024

Solution Threads

M T W T F S S
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25

Rules/Guidelines

Relevant Communities

Relevant Links

Credits

Icon base by Lorc under CC BY 3.0 with modifications to add a gradient

console.log('Hello World')

founded 1 year ago
MODERATORS