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

# advent-of-code

[Burkhard]

For 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 😉

[karelpeeters]

Actually 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.

[Kroppeb]

The 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.

[Burkhard]

Wow yeah you guys are right 🤦 That comes from implementing a complex algorithm from memory without much thinking.