On Sun, 01 Jan 2006 04:59:32 +0100, Wilson Bilkovich <wilsonb / gmail.com>  
wrote:

> On 12/31/05, Stephen Waits <steve / waits.net> wrote:
>>
>> On Dec 31, 2005, at 4:24 PM, Peter Burns wrote:
>>
>> > I think I've improved upon this test code a bit.  I found this one to
>> > be a bit brittle, as it will fail solutions with unanticipated paths
>> > of the same or smaller length.  I lost some of the metadata in the
>> > switch, as Steve has the different solutions ordered by type (i.e.
>> > primes, powers of two, etc).
>>
>> Looks great Peter.  I posted a note about and link to your improved
>> version on my [original post][1].
>>
>> > I'm just pounding away at this test case code because my mathematician
>> > buddy is busy at the moment.  This is quite the nontrivial problem...
>>
>> Exactly why I created my own test cases.  :)
>>
>> --Steve
>>
>> [1]: http://swaits.com/articles/2005/12/31/ruby-quiz-60-test-cases
>>
>
> I'd just like to chime in to say that this quiz is killing me.  The
> difference between 'code to solve the problem' and 'code that finishes
> running, you know, sometime today' is big.

$ time ruby num_maze.rb 22222 99999
[22222, 22224, 11112, 5556, 2778, 2780, 1390, 1392, 696, 348, 174, 87, 89,  
91, 93, 95, 97, 194, 388, 390, 780, 1560, 1562, 3124, 6248, 12496, 12498,  
24996, 24998, 49996, 49998, 99996, 199992, 199994, 99997, 99999]

real    0m1.768s
user    0m1.725s
sys     0m0.022s

;-)


===== SPOILER WARNING =====

The following might be considered a spoiler, if you want to solve the quiz  
completely on your own don't read it!

Some tips:

Try to abstract the problem: You are in a numeric maze, you have two or  
three ways to go next, you want to find the _shortest path_ to the target.  
You don't want to visit the same number twice on your path.

It is not necessary to find some specific strategy/algorithm for this  
special case, so don't concentrate to much on the "mathematical problem".

There were similar quizzes in the past, check out their solutions.