Modified Tower of Hanoi

Question

We all know that the minimum number of moves required to solve the classical towers of hanoi problem is 2ⁿ-1. Now, let us assume that some of the discs have same size. What would be the minimum number of moves to solve the problem in that case.

Example, let us assume that there are three discs. In the classical problem, the minimum number of moves required would be 7. Now, let us assume that the size of disc 2 and disc 3 is same. In that case, the minimum number of moves required would be:

1. Move disc 1 from a to b.
2. Move disc 2 from a to c.
3. Move disc 3 from a to c.
4. Move disc 1 from b to c.

which is 4 moves. Now, given the total number of discs n and the sets of discs which have same size, find the minimum number of moves to solve the problem. This is a challenge by a friend, so pointers towards solution are welcome. Thanks.

Answer 1

Let's consider a tower of size n. The top disk has to be moved 2^n-1 times, the second disk 2^n-2 times, and so on, until the bottom disk has to be moved just once, for a total of 2ⁿ-1 moves. Moving each disk takes exactly one turn.

   1      moved 8 times
  111     moved 4 times
 11111    moved 2 times
1111111   moved 1 time   => 8 + 4 + 2 + 1  ==  15

Now if x disks have the same size, those have to be in consecutive layers, and you would always move them towards the same target stack, so you could just as well collapse those to just one disk, requiring x turns to be moved. You could consider those multi-disks to be x times as 'heavy', or 'thick', if you like.

   1
  111                       1      moved 8 times
  111       collapse       222     moved 4 times, taking 2 turns each
 11111    ----------->    11111    moved 2 times
1111111                  3333333   moved 1 time, taking 3 turns
1111111                            => 8 + 4*2 + 2 + 1*3  ==  21
1111111

Now just sum those up and you have your answer.

Here's some Python code, using the above example: Assuming you already have a list of the 'collapsed' disks, with disks[i] being the weight of the collapsed disk in the ith layer, you can just do this:

disks = [1, 2, 1, 3]           # weight of collapsed disks, top to bottom
print sum(d * 2**i for i, d in enumerate(reversed(disks)))

If instead you have a list of the sizes of the disks, like on the left side, you could use this algorithm:

disks = [1, 3, 3, 5, 7, 7, 7]  # size of disks, top to bottom
last, t, s = disks[-1], 1, 0
for d in reversed(disks):
    if d < last: t, last = t*2, d
    s = s + t
print s 

Output, in both cases, is 21, the required number of turns.