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

Advent Of Code

920 readers
2 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
 

I know that we can brute force it by placing an obstacle at every valid position in the path, but is there a more elegant / efficient solution?

you are viewing a single comment's thread
view the rest of the comments
[–] [email protected] 1 points 1 month ago

You gave me an idea!

  • Give each obstacle in the initial map an ID, and build three indexes by ID, by row, and by column.
  • Use the list of obstacles to build up a map from (ID, direction) to (next ID, direction) (if any) -- that is, for each obstacle, update the map entry for any preceding obstacle that could reach it.
  • This map can be used to compute the path very cheaply.
  • And crucially, you can easily update the map for new obstacles using the same method above.

I think this would give a pretty good speed up, and you might not need to worry about only checking intersections.