Essays/Tower of Hanoi

From J Wiki
Jump to: navigation, search

Introduction

The Tower of Hanoi problem is to move a set of n different-sized disks from one peg to another, moving one disk at a time, using an intermediate peg if necessary. At all times no larger disk may sit on top of a smaller disk.

For example, moving 3 disks from peg 0 to peg 1 can be done as follows:

  • move disk 0 from peg 0 to peg 1
  • move disk 1 from peg 0 to peg 2
  • move disk 0 from peg 1 to peg 2
  • move disk 2 from peg 0 to peg 1
  • move disk 0 from peg 2 to peg 0
  • move disk 1 from peg 2 to peg 1
  • move disk 0 from peg 0 to peg 1

The description of the moves can be shortened if we observed that in moving a disk from peg A to peg B, it is always the top disk on peg A that is moved. Thus the 3-disk problem can be solved as follows:

0 1
0 2
1 2
0 1
2 0
2 1
0 1

Legend has it that a group of priests has been solving the 64-disk problem since the beginning of time, and when they finish, the world will come to an end.

An Initial Solution

There is a simple recursive solution to the n-disk problem: First, move disks 0 to n-2 from peg 0 to peg 2 , then move disk n-1 from peg 0 to peg 1 , then move disks 0 to n-2 from peg 2 to peg 1 . If there is just one disk, the one disk can be moved from peg 0 to peg 1 straightaway.

This can be implemented as a dyadic verb: the right argument is the number of disks; the left argument are 3 integers of the pegs (from, to, via).

H=: 4 : 0
 if. 1>:y do.
  (y,2)$x
 else.
  ((0 2 1{x) H y-1), (2{.x), ((2 1 0{x) H y-1)
 end.
)

   0 1 2 H 3
0 1
0 2
1 2
0 1
2 0
2 1
0 1

From the definition of H , it is easy to see that the n-disk problem requires <:2^n moves. If n=1 , there is one move (1=<:2^1). If n=k-1 required <:2^k-1 moves, then n=k requires the following numbers of moves:

 <:2^k-1    ((0 2 1{x) H y-1)
 1          (2{.x)
 <:2^k-1    ((2 1 0{x) H y-1)

for a total of <:2^k moves. A similar argument shows that the n-disk problem requires <:2^n calls of the verb H .

   0 1 2 #@H"1 0 i.10
0 1 3 7 15 31 63 127 255 511
   <: 2 ^ i.10
0 1 3 7 15 31 63 127 255 511

Singly Recursive Solutions

The two recursive steps in H differ only in the labelling of the pegs. Therefore we can replace them with a single recursive call, and do two relabellings of the pegs to get the effect of two recursions. That is verb H1 below.

Moreover, in verb H1 the left argument is unchanged in the recursion; that is, the left argument is always 0 1 2 , and can be elided.

We saw previously that on the n-disk problem the doubly recursive H required <:2^n calls. In the singly recursive H1 and H2 , the n-disk problem requires n calls. Benchmarks on the 10-disk problem demonstrate the difference this makes.

H1=: 4 : 0
 if. 1>:y do.
  (y,2)$0 1{x
 else.
  ({&0 2 1 , 0 1"_ , {&2 1 0) x H1 y-1
 end.
)

H2=: 3 : 0
 if. 1>:y do.
  i.y,2
 else.
  ({&0 2 1 , 0 1"_ , {&2 1 0) H2 y-1
 end.
)

   0 1 2 (H -: H1)"1 0 i.10
1 1 1 1 1 1 1 1 1 1
   (0 1 2&H -: H2)"0 i.10
1 1 1 1 1 1 1 1 1 1

   ts=: 6!:2 , 7!:2@]   NB. time and space
   ts '0 1 2 H 10'
0.0151321 54208
   ts '0 1 2 H1 10'
0.000236622 44288
   ts 'H2 10'
0.000224889 43840

Non-Recursive Solutions

We now proceed to derive non-recursive solutions to the problem.

The results of verbs H , H1 , and H2 are rows of the 6-row matrix A (the 6 different ways of moving from peg i to peg j where i and j can be 0 , 1 , or 2). Thus a more efficient representation for the solutions is to encode the moves as row indices of A , the integers from 0 to 5 .

   A=: 6 2 $ 0 1 0 2 1 0 1 2 2 0 2 1
   A
0 1
0 2
1 0
1 2
2 0
2 1

   A i. H2 1
0
   A i. H2 2
1 0 5
   A i. H2 3
0 1 3 0 4 5 0
   A i. H2 4
1 0 5 1 2 3 1 0 5 4 2 5 1 0 5
   A i. H2 5
0 1 3 0 4 5 0 1 3 2 4 3 0 1 3 0 4 5 0 4 3 2 4 5 0 1 3 0 4 5 0

Judicious alignment of the indices reveals a pattern:

1:   0
2: 1 0 5

2:   1   0   5
3: 0 1 3 0 4 5 0

3:   0   1   3   0   4   5   0
4: 1 0 5 1 2 3 1 0 5 4 2 5 1 0 5

4:   1   0   5   1   2   3   1   0   5   4   2   5   1   0   5
5: 0 1 3 0 4 5 0 1 3 2 4 3 0 1 3 0 4 5 0 4 3 2 4 5 0 1 3 0 4 5 0

To get from  A i. H2 n-1 to  A i. H2 n , merge (intersperse) the result for n with 1 5 2 if n is even and wit 0 3 4 if n is odd. Thus:

H3=: 3 : 0
 if. 1>:y do.
  y$0
 else.
  }: , ((2^y-1)$(2|y){1 5 2,:0 3 4) ,. 0,~H3 y-1
 end.
)

   H3 3
0 1 3 0 4 5 0
   (A i. H2 3) -: H3 3
1
   (A&i.@H2 -: H3)"0 i.10
1 1 1 1 1 1 1 1 1 1

H3 n works by appending an atom to the result of H3 n-1 ; then stitching a list, repetitions of 1 5 2 or 0 3 4 ; then ravelling; then dropping the last (previously appended) atom.

The list of numbers to be stitched (repetitions of 0 3 4 or 1 5 2) depends only on n , and on H3 n-1 not at all. This suggests a different method of directing the computation: Compute the lists xi of numbers to be stitched for 1 , 2 , 3 , ..., up to n , and then apply an appropriate verb f between them:

xn f ... f x3 f x2 f x1
> f&.> / xn ; ... ; x3 ; x2 ; x1

Moreover, we can avoid incorporating into f the appending and dropping of atoms, if we start out with an "extra" atom and drop it only at the end:

> f&.> / xn ; ... ; x3 ; x2 ; x1
}: > g&.> / xn ; ... ; x3 ; x2 ; x1 ; atom

In H4 below, the verb g is ,@,. (ravel stitch).

   H4 =: }: @ > @ (,@,.&.>/) @ (< ,~ 2&^@i. $&.>&|. $&(0 3 4;1 5 2))

   (H3 -: H4)"0 i.10
1 1 1 1 1 1 1 1 1 1

   arg=: < ,~ 2&^@i. $&.>&|. $&(0 3 4;1 5 2)
   arg 1
┌─┬─┐
│0│1│
└─┴─┘
   arg 2
┌───┬─┬─┐
│1 5│0│2│
└───┴─┴─┘
   arg 3
┌───────┬───┬─┬─┐
│0 3 4 0│1 5│0│3│
└───────┴───┴─┴─┘
   arg 4
┌───────────────┬───────┬───┬─┬─┐
│1 5 2 1 5 2 1 5│0 3 4 0│1 5│0│4│
└───────────────┴───────┴───┴─┴─┘
   arg 5
┌───────────────────────────────┬───────────────┬───────┬───┬─┬─┐
│0 3 4 0 3 4 0 3 4 0 3 4 0 3 4 0│1 5 2 1 5 2 1 5│0 3 4 0│1 5│0│5│
└───────────────────────────────┴───────────────┴───────┴───┴─┴─┘

There is another possibility. The pattern in H4 is:

}: > g&.> / xn ; ... ; x3 ; x2 ; x1 ; atom

In an intermediate stage, when g is being applied,

xi g yi

g "knows" from yi alone what xi has to be: the length of yi determines the length of xi , and the leading atom of yi (0 or 1) determines whether 1 5 2 or 0 3 4 should be ravel-stitched. This suggests another solution: a monad is applied n times to the atom 1 .

   H5=: [: }: (,@,.~ # $ {. { (1 5 2,:0 3 4)"_)^:(]`1:)

   (H4 -: H5)"0 i.10
1 1 1 1 1 1 1 1 1 1

   rsa=: ,@,.~ # $ {. { (1 5 2,:0 3 4)"_
   rsa 1
0 1
   rsa rsa 1
1 0 5 1
   rsa rsa rsa 1
0 1 3 0 4 5 0 1
   rsa^:(3) 1
0 1 3 0 4 5 0 1
   H5 3
0 1 3 0 4 5 0

Conclusion

The Tower of Hanoi problem can be solved in a variety of ways, with a wide variation in efficiency.

  • H double recursion
  • H1 single recursion
  • H2 single recursion monad
  • H3 single recursion, atomic representation
  • H4 non-recursive, insert
  • H5 non-recursive, power
   (,. 0j8 0 ": ts"1) ];._1 '/0 1 2 H  10   /0 1 2 H1 10/H2 10/H3 10/H4 10/H5 10'
0 1 2 H  10   0.01312960 54336
0 1 2 H1 10   0.00022573 44288
H2 10         0.00021343 43840
H3            0.00026288 40640
H4            0.00010504 30080
H5            0.00010169 25536



Contributed by Roger Hui. Substantially the same text appears in Vector, Volume 21, Number 1, Autumn 2004, and also as "The Tower of Hanoi" lab with the J distribution.