One of the problems asks us to work through the classic Tower of Hanoi problem with 3 pegs and then with 4 pegs. I was very pleased with myself for coming up with the Frame-Stewart algorithm on my own, but I failed to think of the way to determine the optimal k value. Instead, I first naively tried k = n - 2 and k = n `div` 2. These did not achieve the number of steps (129) that the assignment page said was possible. So after a lot of toiling, I started to look up what the solution might be.

I came across this blog post which is actually cited in the above Wikipedia section on the Frame-Stewart algorithm. It's a cryptic post that doesn't offer any justification for the proposed optimal k value. I took that k value and placed it into my 4-peg Hanoi implementation as below. This code is available on GitHub.

type Peg = String

type Move = (Peg, Peg)

hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]

hanoi 0 _ _ _ = []

hanoi 1 a b c = [(a, b)]

hanoi n a b c = moveTopToC ++ moveBottom ++ moveTopToB

where moveTopToC = hanoi (n-1) a c b

moveBottom = hanoi 1 a b c

moveTopToB = hanoi (n-1) c b a

hanoi4 :: Integer -> Peg -> Peg -> Peg -> Peg -> [Move]

hanoi4 n a b c d

| n <= 2 = hanoi n a b c

| otherwise = moveTopToD ++ moveBottom2 ++ moveTopToB

where moveTopToD = hanoi4 (n-2) a d b c

moveBottom2 = hanoi4 2 a b c d

moveTopToB = hanoi4 (n-2) d b a c

hanoi4' :: Integer -> Peg -> Peg -> Peg -> Peg -> [Move]

hanoi4' n a b c d

| n <= 2 = hanoi n a b c

| otherwise = moveTopKToD ++ moveBottom ++ moveTopKToB

where k = n `div` 2

moveTopKToD = hanoi4' k a d b c

moveBottom = hanoi (n - k) a b c

moveTopKToB = hanoi4' k d b a c

-- "optimal" choice of k

hanoi4'' :: Integer -> Peg -> Peg -> Peg -> Peg -> [Move]

hanoi4'' n a b c d

| n <= 2 = hanoi n a b c

| otherwise = moveTopKToD ++ moveBottom ++ moveTopKToB

where k = ((round . sqrt . fromIntegral) (2*n + 1)) - 1

moveTopKToD = hanoi4'' k a d b c

moveBottom = hanoi (n - k) a b c

moveTopKToB = hanoi4'' k d b a c

(Note that in this formulation, the goal is to move the disks from peg "a" to peg "b" with pegs "c" and "d" as the extra pegs available as storage space. This is just a different labeling than the classical formulation, in which the goal is to move from peg "a" to peg "c" with "b" as the storage space.)

Imagine my surprise when this actually resulted in

*more*steps than either of my naive approaches:

ely@eschaton:~/programming/learnmeahaskell/penn_cis194/assignments/a1$\$$ ghci

GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help

Loading package ghc-prim ... linking ... done.

Loading package integer-gmp ... linking ... done.

Loading package base ... linking ... done.

Prelude> :load Assignment1.hs

[1 of 1] Compiling Assignment1 ( Assignment1.hs, interpreted )

Ok, modules loaded: Assignment1.

*Assignment1> length $\$$ hanoi4 15 "a" "b" "c" "d"

509

*Assignment1> length $\$$ hanoi4' 15 "a" "b" "c" "d"

305

*Assignment1> length $\$$ hanoi4'' 15 "a" "b" "c" "d"

1049

I started to think about it more. For this way of calculating k, it will be far smaller than the value n. In fact, k should be somewhere on the order of sqrt(n). So there will be n - k disks left over, which will be the majority of them. For example, if there were 25 disks, k would be somewhere around 5 and the leftovers would be about 20.

This immediately doesn't make sense. You don't want to perform the slower recursive call to the 3-peg case on the larger subset of disks. Clearly even a 50/50 split of the disks would be better than that. So my hunch was that you should calculate k' as it is described above, but then you should calculate the true k as k = n - k' -- so that the larger subset of disks is given the more efficient 4-peg treatment and only a much smaller set is moved with the 3-peg method.

When I made that change below and ran it in ghci, I got the expected minimal number of steps for the 15-disk, 4-peg case. So then I edited Wikipedia to fix the mistake. So there you go: practicing a simple Haskell problem leads you to be a Wikipedia contributor.

-- Final method uses optimal choice of k.

hanoi4'' :: Integer -> Peg -> Peg -> Peg -> Peg -> [Move]

hanoi4'' n a b c d

| n <= 2 = hanoi n a b c

| otherwise = moveTopKToD ++ moveBottom ++ moveTopKToB

where k = n - ((round . sqrt . fromIntegral) (2*n + 1)) + 1

moveTopKToD = hanoi4'' k a d b c

moveBottom = hanoi (n - k) a b c

moveTopKToB = hanoi4'' k d b a c

*Assignment1> :load Assignment1.hs

[1 of 1] Compiling Assignment1 ( Assignment1.hs, interpreted )

Ok, modules loaded: Assignment1.

*Assignment1> length $\$$ hanoi4'' 15 "a" "b" "c" "d"

129