Problems 18, 67, 81, 82 and 83 in Project Euler are quite similar, but increase in level of difficulty. For all of these except 83 I've used a specialized dynamic-programming solution that worked quite well. Being recursive it was a tiny bit slower than the iterative approaches others have used, but I believe recursive solutions are more elegant. Anyway, project 83 proved too hard for my approach, because it introduces real cycles into the paths. So, this time I had to arm myself with a real path-finding algorithm. Luckily, I've coded a pretty generic implementation of the A* algorithm quite recently for my Creeps PyGame demo. A*, however, requires a heuristic to do its magic, and for problem 83 there's no real heuristic. However, since a constant heuristic is acceptable and effectively "dumbs down" A* to the original Dijkstra algorithm (the heuristic of A* must be non-decreasing, which a constant satisfies), I was able to make use of the code from the Creeps game to find a solution in 0.3 seconds, with only 30 lines of code.

Comments

comments powered by Disqus