Here is my solution to Ruby Quiz 60: Numeric Maze. The challenge is to find the shortest path from one number to another by applying three operations (double, halve, add_two).
My approach uses recursion to perform a breadth-first search. At first, I
used pruning cyclic paths to speed up longer solutions: running
solve(22, 999) dropped from over seven minutes to under 20
seconds (667 MHz PPC, Mac OS X). Next, I tried avoiding calling double after
half, and vice versa. That saved even more time and actually removed the need
for the cyclic path check, since give that optimization cycles can't
happen.
I also tried pruning longer lists (those where the last number appeared
earlier in another path), but doing that didn't save time, probably because my
algorithm was O(n2).
I use send(symbol, n) to call the operations. I
tried using Proc objects and Proc.call, but it ended
up being between 33% and 50% slower.
Back to my Ruby Quiz solutions page.