From: Ilmari Heikkinen <ilmari.heikkinen@...>
Date: 2006-01-02T14:55:23+09:00
Subject: Re: Numeric Maze (#60)

On 1/2/06, Christer Nilsson <janchrister.nilsson@gmail.com> wrote:> Ilmari Heikkinen wrote:> > #> > # Problems appear when trying to make 255 into 257:> > # 11111111 -> 100000001> > #> > # The shortest way is by adding 2.> > # But the algorithm below fails at that and goes the long way:> > # 11111111 << 1> > # 111111110 + 2> > # 1000000000 + 2> > # 1000000010 >> 1> > # 100000001> > #>> Ilmari, I tried to replicate your solution, before seeing it, and> strangely run into exactly the same behaviour. The code is not complete,> but the idea is to go downwards to 1 with both numbers. I'm using the> complement of +2, -2 for the target number.>>       t up(255), [255, 510, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]>                   -->  -->  --v>                   <--  <--  <-->     t down(257), [257, 514, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]>> Having these two sequences, I find the largest common number, in this> case 512. This gives me the non optimal solution [255,510,512,514,257],> which is exactly the same as yours. I'm not sure if identifying> shortcuts afterwards, will find the shortest path, though, in all cases.> (Finding 255 + 2 = 257, is easy, but what about finding 255 -> 259 if> 257 is missing.)>
I toyed with writing a optimize-function, which would take themidstate list and find patterns that are known to be suboptimal. Onepattern to look for would be going from odd number to another, wherethe distance is even and less than 32, which is the point where themultiply, add, divide, etc starts being less ops than add 2.
The optimizer iterates from start of path, and then for each number,find from end of path the farthest matching number, replace the opsbetween with optimized version.
E.g. for [255, 510, 512, 514, 257], start from 255, then iterateremaining numbers from end to start, 257 matches, so replace the opsbetween with +2 to get [255, 257].
Other patterns? Hmm, dunno. 12 -> 11 is suboptimal, 14 -> 13 too, bothdemonstrating a faster solution that would be divide to odd, add 2s tomatch. I hypothesize that this only happens with small numbers, wherethe divide-to-odd + add 2s is less ops.
[14, 16, 8, 4, 6, 12, 24, 26, 13] -> [14, 7, 9, 11, 13]
(This is also weird in that Gregory's solver gives a one step shortersolution: [14, 16, 8, 10, 12, 24, 26, 13])
Food for thought,
Ilmari