From: Reinder Verlinde <reinder@...>
Date: 2006-01-02T08:42:56+09:00
Subject: Re: [SOLUTION] Numeric Maze (#60)

In article 
<60768b90601011339l5a8bd2ecq514eb3c2fa59d52c@mail.gmail.com>,
 Justin Bishop <jubishop@gmail.com> wrote:

> i had toyed around with other optimizations but none seemed elegant
> and time-saving enough to be worth it. what i was hoping for was a
> nice way to identify when certain paths are careening insanely
> off-path and clearly won't be the correct answer...i have yet to see
> the solution that can do things like solve(222,9999) in
> milliseconds...i am anxiously awaiting one...or did i miss it?

I think one should look at the mathematical side of the problem first. 
Here are some starting ideas:

- write both the starting and the target number in binary
- notice that the three operators do the following:
  - add a zero to the right = left shift the number one position
  - remove a zero from the right = right shift the number one position
  - flip a bit in the one-but-rightmost position, possibly changing
    consecutive ones to zeroes to the left of this bit

Only the first operation can possibly increase the number of zeroes in 
the number (always by one).

Only the second one can change the parity of the number.

Only the last one can possibly change the number of ones in the number 
(either increasing it by one, or decreasing it by possibly arbitrary 
amounts)

Looking at the example (222,9999), I see the following:
 222 = 0x00DE =           1101 1110   (2 zeroes, 6 ones)
9999 = 0x270F =   10 0111 0000 1111   (5 zeroes, 8 ones)

From this, we can see that we must do at least 3 left shifts (to obtain 
the five zeroes), at least one right shift (to change parity), and at 
least one '+2' (to change the number of ones)

Looking at it in a different way: we must get a '1' in position 14 from 
the right. That '1' can only come from position 13, using either the 
'*2' or the '+2' (with sufficient overflows) operations.

There is no '1' in position 13. To get one there, we need one at 
position 12, etc.

In the end to get a '1' in position 14 is by moving the one in position 
8 there, using a combination of at least six '*2' or '+2' operations.
If we do that using '*2' only, the '1' in position 7 would move to 
position 13. We do not want a '1' there, so we should use '+2' at least 
once.

I think logic like this will lead to a better understanding of the 
problem, and possibly to more efficient solutions.

For instance: I would guess that many of the optimal solutions are 
rather dull, ending in a series of ('*2') or ('+2', '*2') operations to 
shift in zero and one bits, followed by a single '/2' if the target 
value is odd (WARNING: this is just a hunch; I may be completely wrong 
here)

Reinder