Re: Perl Quiz of the Week #23

> So I worked a bit, and pretty quickly got an algorithm straight.
> However, it's fairly obvious that my algorithm is exponential.
> Obviously, the number of results is also exponential, but I was hoping
> that I could

??

Mine is slow, but has the benefit of being very short.  :-)

It took me about 2 minutes to realize that the very simple algorithm I
had simply wouldn't work.  The new one is simple and not particularly
speedy. 


> For 'n' up to 10, the time is under a second.  However, on a very nice
> machine, I very quickly go bad.  My runtimes seem to be
> 
>                 4**N * 8e-7 seconds.
> 
> When N = 10, this is 0.8 seconds.  When N = 14, this is over three
> minutes.  I've been waiting nine minutes for N = 15, and don't expect
> an answer for another three minutes (at least).  It will be a really
> long wait for N = 16.

Did I mention mine was slow?
10 =>   3.6
12 =>  56.4
14 => 961.8

> I'm wondering if there is a less expensive exponential solution --
> maybe a non-recursive one.  For example, the Towers of Hanoi, which
> seems recursive, has a very simple non-recursive (looping) solution.

My program is exponential, but I don't consider it recursive.  My first
attempt was recursive, but I didn't get it to work.

-- 
Darren Dunham                                           [email protected]
Senior Technical Consultant         TAOS            http://www.taos.com/
Got some Dr Pepper?                           San Francisco, CA bay area
         < This line left intentionally blank to confuse you. >