by Rene Grothmann
This is just a simple recursive solution of the problem of towers of Hanoi. In case you never heard about it, have a look at
>function move (from:string, to:string, spare:string, n:index) ... if n==1 then from|" -> "|to, else move(from,spare,to,n-1); move(from,to,spare,1); move(spare,to,from,n-1); endif; endfunction
A -> B
A -> C A -> B C -> B
A -> B A -> C B -> C A -> B C -> A C -> B A -> B
A -> C A -> B C -> B A -> C B -> A B -> C A -> C A -> B C -> B C -> A B -> A C -> B A -> C A -> B C -> B
Let us try to animate the Towers. I will develop the animation here instead of in an Euler as it should be done.
First we draw a single tower. We use very basic routines for this in plot coordinates x=0...1, y=0...1 and full window mode. The stones are drawn with plotbar.
The discs are stored in a vector, where the discs have positive numbers corresponding to their sze.
>function drawtower (n:index, v:vector, kmax:index) ... window([0,0,1024,1024]); hold on; setplot(0,1,0,1); h=0.05; d=0.01; x=n/3-1/6; y=1/2-kmax/2*(h+d); w=1/8; barstyle("0#"); barcolor(red); plotbar(x-w,y,2*w,h); barcolor(green); for vd=v; if vd==0 then break; endif; y=y+h+d; wd=w*vd/(kmax+1); plotbar(x-wd,y,2*wd,h); end; hold off; endfunction
Let us test this.
The following function plots three columns stored in a matrix with three rows.
>function drawtowers (v:real, kmax:index) ... clg; loop 1 to 3 drawtower(#,v[#],kmax); end; endfunction
To copy the image to the screen, we use a cropped insimg command.
>v=[5,4,3,1;2;0]; drawtowers(v,7); insimg(crop=[0.3,0.8]);
The next function moves one disc from tower i to tower j. We determine the minimal index k, such that v[i,k] contains a disc.
>function movedisc (v:real, i:index, j:index) ... k=max(nonzeros(v[i])); d=v[i,k]; v[i,k]=0; if v[j,1]==0 then v[j,1]=d; else k=max(nonzeros(v[j])); v[j,k+1]=d; endif; endfunction
Let ust test this.
>v=[5,4,3,1;2;0]; ... movedisc(v,1,3); drawtowers(v,7); insimg(crop=[0.3,0.8]);
The vector is changed, since matrices are passed by reference, and we change only elements of the matrix.
5 4 3 0 2 0 0 0 1 0 0 0
Now, we move another disc.
>movedisc(v,3,2); drawtowers(v,7); insimg(crop=[0.3,0.8]);
To solve the towers we setup the start position, and call a solve routine, which does the job.
>function solvetowers (n:index=5, delay=0.5) ... v=(n:-1:1)_0_0; drawtowers(v,n+2); wait(delay); solvetowersrec(v,n,n+2,delay); endfunction
The solve routine calls a recursive routine as above.
>function solvetowersrec (v,n,kmax,delay) ... movetowersrec(v,n,1,2,3,kmax,delay) endfunction
This is the recursion.
It moves n-1 discs, then one disc (the largest), then the n-1 discs back.
>function movetowersrec (v,n,from,to,over,kmax,delay) ... if n>0 then movetowersrec(v,n-1,from,over,to,kmax,delay); movedisc(v,from,to); drawtowers(v,kmax); wait(delay); movetowersrec(v,n-1,over,to,from,kmax,delay); endif; endfunction
Start the animation.
You can set the delay to 5 seconds, and advance by pressing any key. The wait() function is interrupted by key strokes.