Ancestors

Toot

Written by Walker Boh🛡 on 2024-12-16 at 18:17

Day 16 #adventofcode in the books.

Finding a minimum path through a large maze.

Part 1 was finding the cost of the minimum cost path. My first approach of BFS worked fine on the smaller test mazes, but never finished on the full size one.

I had tried to avoid it because I hate it, but it was time to use Dijkstras algorithm. That worked.

Part 2 was adding up all of the unique tiles visited for all of the paths that were minimum cost. This bent my brain for a while, trying to reverse it from the DP matrix was an exercise in futility.

Came back to it with a fresh approach this morning and recorded each of the unique parent tiles and costs as I went, then used that at the end to reverse the paths out. That worked.

[#]typescript handled all of this just fine.

Ouch again - I still hate dijkstras...

=> View attached media

=> More informations about this toot | More toots from walkerb@infosec.exchange

Descendants