[Oops.] Error in RULERHANOI Algorithm in Exercise 1.1(d)

[skydiving94]

Please verify that the error is present in the most recent revision before reporting.

Chapter number or note title: Ex 1.1(d)

Page number: 45

Error description:
The RULERHANOI(n = 1) algorithm produces the move 1: 0→1 as its first step.

• i = 1
• \rho(1) = 1 as 1/2 is not integer.
• 1 \leq n
• n - 1 = 1 - 1 = 0 is even
• moves disk from 0 to 1.

This contradicts the correct first move of 1: 0→2.

• R(1, 0, 2, 1) skips the first and second recursive calls and moves disk from 0 to 2 directly.

Since the algorithm fails on this simple case, it is not a correct general solution for the Tower of Hanoi problem.

Suggested fix (if any):

• Unverified, but perhaps switch the forward/backward? i.e. n - i being even means moving backward?

[erbenpeter]

• Unverified, but perhaps switch the forward/backward? i.e. n - i being even means moving backward?

I think two changes are necessary. Only changing forward and backward does not fix it for all inputs. We also need to change n - i to n - disk (or n - rho(i)). Tested with the below Python snippet:

def ro(m):
    k = 0
    d = 1
    while m % d == 0:
        k += 1
        d *= 2
    return k


def hanoiruler(n):
    pos = {i: 0 for i in range(1, n + 1)}
    i = 1
    while ro(i) <= n:
        disk = ro(i)
        p = pos[disk]
        if (n - disk) % 2 == 1:
            pp = (p + 1) % 3
        else:
            pp = (p - 1 + 3) % 3
        print(disk, ":", p, "-->", pp)
        pos[disk] = pp
        i += 1