For some reason I decided to implement a full A* p...

# advent-of-codeb

Burkhard

12/06/2019, 11:08 AMFor some reason I decided to implement a full A* pathfinding algorithm for the second part. I know A* needs a heuristic to be efficent, but it works as long as it is greater than the real distance. So I used the result of part 1 as the heuristic. Since this is greater than any possible length A* will just work like a flood fill algorithm.
<https://github.com/Wasabi375/AdventOfCode2019/blob/master/src/nativeMain/kotlin/pathfinder/Pathfinder.kt>
<https://github.com/Wasabi375/AdventOfCode2019/blob/master/src/nativeMain/kotlin/day6/star11_12.kt>
I know there are probably a bit more efficent ways to solve this, but my guess is I can use the A* algorithm later in AoC and it was fun implementing A* from memory ðŸ˜‰

k

karelpeeters

12/06/2019, 11:41 AMActually it's the other way around, you heuristic needs to underestimate the actual cost, so just

`h(x) = 0`

is fine and gets you Dijkstra.k

Kroppeb

12/06/2019, 11:52 AMThe reason it doesn't matter here is cause the graph is a tree. As long as you don't pass any node twice it will always give you the shortest path.

b

Burkhard

12/06/2019, 11:54 AMWow yeah you guys are right ðŸ¤¦ That comes from implementing a complex algorithm from memory without much thinking.

72 Views