For some reason I decided to implement a full A* p...
# advent-of-code
b
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 ­čśë
k
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.
k
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.
b
Wow yeah you guys are right ­čĄŽ That comes from implementing a complex algorithm from memory without much thinking.