InterviewSolution
Saved Bookmarks
| 1. |
Realising he needs money, Tintin reaches inside the bank situated on the island, and sees a row of lockers which start with 0 and go on till infinity. A locker can contain any number of coins. A coin is placed in the locker with index 7 (i.e. the 8th square). The aim is to move this coin to the locker with index 1. (i.e. the 2nd square) and all other squares empty. There are two rules to this: 1) Fission Rule: A coin may be replaced by a pair of coins by placing one in each of the immediately adjacent squares. Eg.Coin #3 can be replaced by Coin#2 and Coin#4 where Coin#(number) rep- resents coin in position with index number. 2) Fusion Rule: A pair of coins separated by exactly one intervening square can be replaced by a single coin in that middle square. Eg.Coin#2 and Coin#4 can be replaced by Coin#3. Minimum number of moves required to achieve our aim ? |
|
Answer» 18 000000+1 (start) 00001 +11 0001 +1 10 0 +11 +1000 +11 +10000 +1000000 (end) This gives you the four critical moves that must be in any solution. However, applying themdirectly is illegal. [But you can] just [keep] SPLITTING the left penny (7 times), then [do the] “critical4 moves” and you come up with the mirror image position, so you now combine to the finalposition. Ergo, 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 2 1 1 1 1 1lt+1 1 +1 1 1 1 1 2 1 1 1 1lt+1 1 +1 1 1 1 1 1 2 0 1 1 1 1 1 1 1 1 1 0 1lt1 +1 1 1 1 1 1 1 1 0 1 0lt1 +1 1 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 |
|