Towers of Hanoi: Difference between revisions

<lang rexx>/*REXX program to show the moves to solve the Tower of Hanoi (3 disks). */

arg z . /*get possible specification of Z*/

if z=='' then z=3 /*Not given? Use default 3 towers*/

move=0 /*number of ring moves so far. */

call mov 1,3,z /*move top ring, then recurse... */

say 'The minimum number of moves to solve a' z "ring Tower of Hanoi is" 2**z-1

/*─────────────────────────────MOV subroutine───────────────────────────*/

mov: procedure expose move; arg #1, #2, #3

if #3==1 then call dsk #1, #2

else do

call mov #1, 6-#1-#2, #3-1

call mov #1, #2, 1

call mov 6-#1-#2, #2, #3-1

end

return

dsk: move=move+1

say 'step' right(move,length(moves))": move disk " arg(1) '──►' arg(2)

{{out}}

step 1: move disk 1 ──► 3

step 2: move disk 1 ──► 2

step 3: move disk 3 ──► 2

step 4: move disk 1 ──► 3

step 5: move disk 2 ──► 1

step 6: move disk 2 ──► 3

step 7: move disk 1 ──► 3

The minimum number of moves to solve a 3 ring Tower of Hanoi is 7.

{{out}}when the following was entered (to solve with four disks): <tt>4</tt>

<pre style="height:25ex">

step 1: move disk 1 ──► 2

step 2: move disk 1 ──► 3

step 3: move disk 2 ──► 3

step 4: move disk 1 ──► 2

step 5: move disk 3 ──► 1

step 6: move disk 3 ──► 2

step 7: move disk 1 ──► 2

step 8: move disk 1 ──► 3

step 9: move disk 2 ──► 3

step 10: move disk 2 ──► 1

step 11: move disk 3 ──► 1

step 12: move disk 2 ──► 3

step 13: move disk 1 ──► 2

step 14: move disk 1 ──► 3

step 15: move disk 2 ──► 3

The minimum number of moves to solve a 4 ring Tower of Hanoi is 15.

Quite a bit of code has been dedicated to showing a picture of the towers with the disks on them, and the movement of the disk (the move). Coloring of the rings is attempted with dithering.

In addition, it shows each move in a countdown manner (the last move is move #1).

No attempt is mode to explain this version of the REXX program 'cause of the complexity and somewhat obtuse features of the REXX language, the smallest of which is support for ASCII and EBCDIC "graphic" characters. It may not be obvious, but whenever a ring is moved from one tower to another, it is always the top ring that is moved.

<lang rexx>/*REXX program shows pictorial moves to solve Tower of Hanoi (3 disks). */

arg z .; if z=='' then z=3

sw=80; wp=sw%3-1; blanks=centre('',wp)

move=0; totmoves=2**z-1; movek=totmoves; lentot=length(totmoves)

@abc='abcdefghijklmnopqrstuvwxyz'

ebcdic= 'f0'x==0

$.=0; $.1=z; k=z; kk=k+k

do j=1 for z

@.1.j=centre(copies(box,kk),wp)

if z<=length(boxchars) then @.1.j=,

translate(@.1.j,substr(boxchars,kk%2,1),box)

call showtowers; call mov 1,3,z

say "The minimum number of moves for a" z 'ring Tower of Hanoi is' totmoves

mov: if arg(3)==1 then call rng arg(1) arg(2)

else do

call mov arg(1),6-arg(1)-arg(2),arg(3)-1

call mov arg(1),arg(2),1

call mov 6-arg(1)-arg(2),arg(2),arg(3)-1

end

rng: parse arg from dest; move=move+1; pp=

if from==1 then do

pp=overlay(bl,pp,c.1)

pp=overlay(bar,pp,c.1+1,c.dest-c.1-1,bar)

pp=pp || tr

end

if from==3 then do

pp=overlay(br,pp,c.3)

pp=overlay(bar,pp,c.dest+1,c.3-c.dest-1,bar)

pp=overlay(tl,pp,c.dest)

end

if from==2 then do

lpost=min(2,dest)

hpost=max(2,dest)

if dest==1 then do

pp=overlay(tl,pp,c.1)

pp=overlay(bar,pp,c.1+1,c.2-c.1-1,bar)

pp=pp || br

end

if dest==3 then do

pp=overlay(bl,pp,c.2)

pp=overlay(bar,pp,c.2+1,c.3-c.2-1,bar)

pp=pp || tr

end

end

say translate(pp,verts,Bcorners||Tcorners||bar); say overlay(movek,pp,1)

$.from=$.from-1; $.dest=$.dest+1; _f=$.from+1; _t=$.dest

showtowers: do j=z to 1 by -1

_p=@.1.j @.2.j @.3.j; if _p\='' then say _p

{{out}}

<pre style="height:50ex">

│

│

│

│

│

│

│

The minimum number of moves for a 3 ring Tower of Hanoi is 7