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))
I don't like this type of question. In my experience knowing one language has little impact on learning another. What matters much more is understanding the underlying concepts.
If you grok OOP it doesn't matter if you go from Java to C# or from C++ to Python. Yes, there are differences, but they're mostly syntactic in nature.
So assuming you got the hang of imperative programming and maybe had some exposure to functional programming, too, the concept you're likely to struggle with the most is ownership. Simply because it's a concept that's fairly unique to Rust.
Having come from Java, via C++ and Python and having dabbled with Haskell a bit, I feel like The Book does a decent job of explaining Rust in general and its oddities in particular.