From: ptkwt@... (Phil Tomson)
Date: 2006-01-02T07:37:56+09:00
Subject: Re: [SOLUTION] Numeric Maze (#60)

In article <C95D3FF1-B62F-468B-B791-431D961E29F6@sms.ed.ac.uk>,
Matthew Smillie  <M.B.Smillie@sms.ed.ac.uk> wrote:
>On Jan 1, 2006, at 15:47, James Edward Gray II wrote:
>
>> On Dec 30, 2005, at 7:37 AM, Ruby Quiz wrote:
>>
>>> Problem: Move from the starting point to the target, minimizing  
>>> the number of
>>> operations.
>>
>> Here's my simple breadth-first search with a single optimization  
>> (described in comments).  It's not at all fast enough for the big  
>> examples people have been throwing around, but it's pretty simple.
>
>OK, so I didn't have time to code it up and see for sure, what with  
>some transatlantic travel and New Year's and all that stuff, but the  
>first thing that struck me when reading the problem was "dynamic  
>programming" - did anyone take this route and hence give me a bit of  
>satisfaction that my instincts were right?

I kept thinking that a recursive solution would be the easiest way to go, but 
I quickly found that even some of the most trival testcases overwhelmed the 
stack :-(  (not too surprising, I guess, given the size of the search space).

If I have time to get it done I'll post my non-recursive version (that is 
unfortuneately becoming quite bloated, I think).

Phil