Towers of Hanoi: Difference between revisions
Underscore (talk | contribs) (Perl 5: Changed to permit calling with one argument. Perl 6: Added.) |
m (Fixed lang tags.) |
||
Line 2: | Line 2: | ||
=={{header|ActionScript}}== |
=={{header|ActionScript}}== |
||
<lang actionscript> |
<lang actionscript>public function move(n:int, from:int, to:int, via:int):void |
||
public function move(n:int, from:int, to:int, via:int):void |
|||
{ |
{ |
||
if (n > 0) |
if (n > 0) |
||
Line 11: | Line 10: | ||
move(n - 1, via, to, from); |
move(n - 1, via, to, from); |
||
} |
} |
||
}</lang> |
|||
} |
|||
</lang> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
<lang ada> |
<lang ada>with Ada.Text_Io; use Ada.Text_Io; |
||
with Ada.Text_Io; use Ada.Text_Io; |
|||
procedure Towers is |
|||
type Pegs is (Left, Center, Right); |
|||
procedure Towers is |
|||
procedure Hanoi (Ndisks : Natural; Start_Peg : Pegs := Left; End_Peg : Pegs := Right; Via_Peg : Pegs := Center) is |
|||
type Pegs is (Left, Center, Right); |
|||
begin |
|||
procedure Hanoi (Ndisks : Natural; Start_Peg : Pegs := Left; End_Peg : Pegs := Right; Via_Peg : Pegs := Center) is |
|||
if Ndisks > 0 then |
|||
begin |
|||
Hanoi(Ndisks - 1, Start_Peg, Via_Peg, End_Peg); |
|||
Put_Line("Move disk" & Natural'Image(Ndisks) & " from " & Pegs'Image(Start_Peg) & " to " & |
|||
Pegs'Image(End_Peg)); |
|||
Hanoi(Ndisks - 1, Via_Peg, End_Peg, Start_Peg); |
|||
end if; |
|||
Hanoi(Ndisks - 1, Via_Peg, End_Peg, Start_Peg); |
|||
end Hanoi; |
|||
begin |
|||
end Hanoi; |
|||
Hanoi(4); |
|||
begin |
|||
end Towers;</lang> |
|||
Hanoi(4); |
|||
end Towers; |
|||
</lang> |
|||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
<lang algol68>PROC move = (INT n, from, to, via) VOID: |
|||
IF n > 0 THEN |
|||
move(n - 1, from, via, to); |
|||
printf(($"Move disk from pole "g" to pole "gl$, from, to)); |
|||
move(n - 1, via, to, from) |
|||
FI |
|||
; |
|||
main: ( |
|||
move(4, 1,2,3) |
|||
)</lang> |
|||
) |
|||
=={{header|AmigaE}}== |
=={{header|AmigaE}}== |
||
Line 61: | Line 57: | ||
=={{header|AppleScript}}== |
=={{header|AppleScript}}== |
||
<lang applescript> |
<lang applescript>global moves --this is so the handler 'hanoi' can see the 'moves' variable |
||
set moves to "" |
|||
hanoi(4, "peg A", "peg C", "peg B") |
|||
on hanoi(ndisks, fromPeg, toPeg, withPeg) |
|||
if ndisks is greater than 0 then |
|||
hanoi(ndisks - 1, fromPeg, withPeg, toPeg) |
|||
set moves to moves & "Move disk " & ndisks & " from " & fromPeg & " to " & toPeg & return |
|||
hanoi(ndisks - 1, withPeg, toPeg, fromPeg) |
|||
end if |
|||
return moves |
|||
end hanoi</lang> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
<lang AutoHotkey>move(n, from, to, via) ;n = # of disks, from = start pole, to = end pole, via = remaining pole |
|||
<lang AutoHotkey> |
|||
{ |
|||
move(n, from, to, via) ;n = # of disks, from = start pole, to = end pole, via = remaining pole |
|||
if (n = 1) |
|||
{ |
|||
{ |
|||
if (n = 1) |
|||
msgbox , Move disk from pole %from% to pole %to% |
|||
{ |
|||
} |
|||
msgbox , Move disk from pole %from% to pole %to% |
|||
else |
|||
{ |
|||
move(n-1, from, via, to) |
|||
{ |
|||
move(1, from, to, via) |
|||
move(n-1, via, to, from) |
|||
} |
|||
move(n-1, via, to, from) |
|||
}</lang> |
|||
} |
|||
} |
|||
</lang> |
|||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
{{trans|Logo}} |
{{trans|Logo}} |
||
<lang AWK>$ awk 'func hanoi(n,f,t,v){if(n>0){hanoi(n-1,f,v,t);print(f,"->",t);hanoi(n-1,v,t,f)}} |
|||
<lang AWK> |
|||
$ awk 'func hanoi(n,f,t,v){if(n>0){hanoi(n-1,f,v,t);print(f,"->",t);hanoi(n-1,v,t,f)}} |
|||
BEGIN{hanoi(4,"left","middle","right")}' |
BEGIN{hanoi(4,"left","middle","right")}' |
||
left -> right |
left -> right |
||
Line 110: | Line 103: | ||
left -> right |
left -> right |
||
left -> middle |
left -> middle |
||
right -> middle |
right -> middle</lang> |
||
</lang> |
|||
=={{header|BASIC}}== |
=={{header|BASIC}}== |
||
Line 129: | Line 121: | ||
=={{header|C}}== |
=={{header|C}}== |
||
<lang c> |
<lang c>#include <stdio.h> |
||
#include <stdio.h> |
|||
void move(int n, int from, int to, int via) |
|||
{ |
|||
void move(int n, int from, int to, int via) |
|||
if (n > 0) { |
|||
{ |
|||
move(n - 1, from, via, to); |
|||
printf("Move disk from pole %d to pole %d\n", from, to); |
|||
move(n - 1, via, to, from); |
|||
} |
|||
move(n - 1, via, to, from); |
|||
} |
|||
int main() |
|||
} |
|||
{ |
|||
int main() |
|||
move(4, 1,2,3); |
|||
{ |
|||
return 0; |
|||
move(4, 1,2,3); |
|||
}</lang> |
|||
return 0; |
|||
} |
|||
</lang> |
|||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
Line 160: | Line 150: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{works with|g++}} |
{{works with|g++}} |
||
<lang cpp> |
<lang cpp>void move(int n, int from, int to, int via) { |
||
if (n == 1) { |
|||
std::cout << "Move disk from pole " << from << " to pole " << to << std::endl; |
|||
} else { |
|||
move(n - 1, from, via, to); |
|||
move(1, from, to, via); |
|||
move(n - 1, via, to, from); |
|||
} |
|||
}</lang> |
|||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
<lang lisp>(defn towers-of-hanoi [n from to via] |
|||
(if (= n 1) |
|||
(println (format "Move from %s to %s" from to)) |
|||
(do |
|||
(towers-of-hanoi (dec n) from via to) |
|||
(println (format "Move from %s to %s" from to)) |
|||
(recur (dec n) via to from))))</lang> |
|||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
<lang lisp> |
<lang lisp>(defun move (n from to via) |
||
(cond ((= n 1) |
|||
(format t "Move from ~A to ~A.~%" from to)) |
|||
(t |
|||
(move (- n 1) from via to) |
|||
(format t "Move from ~A to ~A.~%" from to) |
|||
(move (- n 1) via to from))))</lang> |
|||
=={{header|D}}== |
=={{header|D}}== |
||
Line 258: | Line 248: | ||
]sM |
]sM |
||
[ # code block |
[ # code block<lang dc> |
||
ln # push n |
ln # push n |
||
lf # push from |
lf # push from |
||
Line 317: | Line 307: | ||
=={{header|E}}== |
=={{header|E}}== |
||
<lang e> |
<lang e>def move(out, n, fromPeg, toPeg, viaPeg) { |
||
if (n.aboveZero()) { |
|||
move(out, n.previous(), fromPeg, viaPeg, toPeg) |
|||
out.println(`Move disk $n from $fromPeg to $toPeg.`) |
|||
move(out, n.previous(), viaPeg, toPeg, fromPeg) |
|||
} |
|||
} |
|||
move(stdout, 4, def left {}, def right {}, def middle {})</lang> |
|||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
<lang erlang>move(1, F, T, _V) -> |
|||
io:format("Move from ~p to ~p~n", [F, T]); |
|||
move(N, F, T, V) -> |
|||
move(N-1, F, V, T), |
|||
move(1 , F, T, V), |
|||
move(N-1, V, T, F).</lang> |
|||
=={{header|FALSE}}== |
=={{header|FALSE}}== |
||
<lang false>["Move disk from "$!\" to "$!\" |
|||
"]p: { to from } |
|||
[n;0>[n;1-n: @\ h;! @\ p;! \@ h;! \@ n;1+n:]?]h: { via to from } |
|||
4n:["right"]["middle"]["left"]h;!%%%</lang> |
|||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
With locals: |
With locals: |
||
<lang forth>CREATE peg1 ," left " |
|||
CREATE peg2 ," middle " |
|||
CREATE peg3 ," right " |
|||
: .$ COUNT TYPE ; |
|||
: MOVE-DISK |
|||
LOCALS| via to from n | |
|||
n 1 = |
|||
IF CR ." Move disk from " from .$ ." to " to .$ |
|||
ELSE n 1- from via to RECURSE |
|||
1 from to via RECURSE |
|||
n 1- via to from RECURSE |
|||
THEN ;</lang> |
|||
Without locals, executable pegs: |
Without locals, executable pegs: |
||
<lang forth>: left ." left" ; |
|||
: right ." right" ; |
|||
: middle ." middle" ; |
|||
: move-disk ( v t f n -- v t f ) |
|||
dup 0= if drop exit then |
|||
1- >R |
|||
rot swap R@ ( t v f n-1 ) recurse |
|||
rot swap |
|||
2dup cr ." Move disk from " execute ." to " execute |
|||
swap rot R> ( f t v n-1 ) recurse |
|||
swap rot ; |
|||
: hanoi ( n -- ) |
|||
1 max >R ['] right ['] middle ['] left R> move-disk drop drop drop ;</lang> |
|||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
{{works with|Fortran|90 and later}} |
{{works with|Fortran|90 and later}} |
||
<lang fortran> |
<lang fortran>PROGRAM TOWER |
||
CALL Move(4, 1, 2, 3) |
|||
CONTAINS |
|||
RECURSIVE SUBROUTINE Move(ndisks, from, to, via) |
|||
INTEGER, INTENT (IN) :: ndisks, from, to, via |
|||
IF (ndisks == 1) THEN |
|||
WRITE(*, "(A,I1,A,I1)") "Move disk from pole ", from, " to pole ", to |
|||
ELSE |
|||
CALL Move(ndisks-1, from, via, to) |
|||
CALL Move(1, from, to, via) |
|||
CALL Move(ndisks-1, via, to, from) |
|||
END IF |
|||
END SUBROUTINE Move |
|||
END PROGRAM TOWER</lang> |
|||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
Line 401: | Line 391: | ||
Most of the programs on this page use an imperative approach (i.e., print out movements as side effects during program execution). Haskell favors a purely functional approach, where you would for example return a (lazy) list of movements from a to b via c: |
Most of the programs on this page use an imperative approach (i.e., print out movements as side effects during program execution). Haskell favors a purely functional approach, where you would for example return a (lazy) list of movements from a to b via c: |
||
<lang haskell> |
<lang haskell>hanoi :: Integer -> a -> a -> a -> [(a, a)] |
||
hanoi 0 _ _ _ = [] |
|||
hanoi n a b c = hanoi (n-1) a c b ++ [(a,b)] ++ hanoi (n-1) c b a</lang> |
|||
One can use this function to produce output, just like the other programs: |
One can use this function to produce output, just like the other programs: |
||
<lang haskell> |
<lang haskell>hanoiIO n = mapM_ f $ hanoi n 1 2 3 where |
||
f (x,y) = putStrLn $ "Move " ++ show x ++ " to " ++ show y</lang> |
|||
Or, instead one can of course also program imperatively, using the IO monad directly: |
Or, instead one can of course also program imperatively, using the IO monad directly: |
||
<lang haskell> |
<lang haskell>hanoiM :: Integer -> IO () |
||
hanoiM n = hanoiM' n 1 2 3 where |
|||
hanoiM' 0 _ _ _ = return () |
|||
hanoiM' n a b c = do |
|||
hanoiM' (n-1) a c b |
|||
putStrLn $ "Move " ++ show a ++ " to " ++ show b |
|||
hanoiM' (n-1) c b a</lang> |
|||
=={{header|Io}}== |
=={{header|Io}}== |
||
<lang io>hanoi := method(n, from, to, via, |
|||
if (n == 1) then ( |
|||
writeln("Move from ", from, " to ", to) |
|||
) else ( |
|||
hanoi(n - 1, from, via, to ) |
|||
hanoi(1 , from, to , via ) |
|||
hanoi(n - 1, via , to , from) |
|||
) |
|||
)</lang> |
|||
) |
|||
=={{header|J}}== |
=={{header|J}}== |
||
<lang j>H =: i.@(,&2) ` (({&0 2 1,0 2,{&1 0 2)@$:@<:) @. * |
|||
<lang j> |
|||
H =: i.@(,&2) ` (({&0 2 1,0 2,{&1 0 2)@$:@<:) @. * |
|||
H1=: monad define |
H1=: monad define |
||
Line 441: | Line 430: | ||
i.0 2 |
i.0 2 |
||
end. |
end. |
||
)</lang> |
|||
) |
|||
</lang> |
|||
<tt>H</tt> employs anonymous recursion; <tt>H1</tt> is an "explicit" statement of the same computation. For example: |
<tt>H</tt> employs anonymous recursion; <tt>H1</tt> is an "explicit" statement of the same computation. For example: |
||
<lang j> |
<lang j> H 3 |
||
H 3 |
|||
0 2 |
0 2 |
||
0 1 |
0 1 |
||
Line 452: | Line 439: | ||
1 2 |
1 2 |
||
1 0 |
1 0 |
||
2 0 |
2 0</lang> |
||
</lang> |
|||
The result is a 2-column table; a row <tt>i,j</tt> is interpreted as: move a disk (the top disk) from peg <tt>i</tt> to peg<tt> j</tt> . |
The result is a 2-column table; a row <tt>i,j</tt> is interpreted as: move a disk (the top disk) from peg <tt>i</tt> to peg<tt> j</tt> . |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
<lang java> |
<lang java>public void move(int n, int from, int to, int via) { |
||
if (n == 1) { |
|||
System.out.println("Move disk from pole " + from + " to pole " + to); |
|||
} else { |
|||
move(n - 1, from, via, to); |
|||
move(1, from, to, via); |
|||
move(n - 1, via, to, from); |
|||
} |
|||
}</lang> |
|||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
<lang javascript> |
<lang javascript>function move(n, from, to, via) { |
||
if (n > 0) { |
|||
move(n-1, from, via, to) |
|||
print("Move disk from " + from + " to " + to) |
|||
move(n-1, via, to, from) |
|||
} |
|||
} |
|||
move(4, "left", "middle", "right")</lang> |
|||
=={{header|Joy}}== |
=={{header|Joy}}== |
||
From [http://www.latrobe.edu.au/philosophy/phimvt/joy/jp-nestrec.html here] |
From [http://www.latrobe.edu.au/philosophy/phimvt/joy/jp-nestrec.html here] |
||
<lang joy> |
<lang joy>DEFINE hanoi == [[rolldown] infra] dip |
||
DEFINE hanoi == [[rolldown] infra] dip |
|||
[ [ [null] [pop pop] ] |
[ [ [null] [pop pop] ] |
||
[ [dup2 [[rotate] infra] dip pred] |
[ [dup2 [[rotate] infra] dip pred] |
||
Line 487: | Line 472: | ||
[[swap] infra] dip pred ] |
[[swap] infra] dip pred ] |
||
[] ] ] |
[] ] ] |
||
condnestrec. |
condnestrec.</lang> |
||
</lang> |
|||
Using it (5 is the number of disks.) |
Using it (5 is the number of disks.) |
||
<lang joy>[source destination temp] 5 hanoi.</lang> |
|||
<lang joy> |
|||
[source destination temp] 5 hanoi. |
|||
</lang> |
|||
=={{header|Logo}}== |
=={{header|Logo}}== |
||
<lang logo>to move :n :from :to :via |
|||
if :n = 0 [stop] |
|||
move :n-1 :from :via :to |
|||
(print [Move disk from] :from [to] :to) |
|||
move :n-1 :via :to :from |
|||
end |
|||
move 4 "left "middle "right</lang> |
|||
=={{header|Mathematica}}== |
=={{header|Mathematica}}== |
||
<lang mathematica>Hanoi[0, from_, to_, via_] := Null |
|||
Hanoi[n_Integer, from_, to_, via_] := |
|||
(Hanoi[n-1, from, via, to]; |
|||
Print["Move dist from pole ", from, " to ", to, "."]; |
|||
Hanoi[n-1, via, from, to])</lang> |
|||
=={{header|Modula-3}}== |
=={{header|Modula-3}}== |
||
Line 536: | Line 518: | ||
The Interface - TowersOfHanoi.h: |
The Interface - TowersOfHanoi.h: |
||
<lang objc> |
<lang objc>#import <Foundation/NSObject.h> |
||
#import <Foundation/NSObject.h> |
|||
@interface TowersOfHanoi: NSObject { |
@interface TowersOfHanoi: NSObject { |
||
Line 548: | Line 529: | ||
-(void) setPegFrom: (int) from andSetPegTo: (int) to andSetPegVia: (int) via andSetNumDisks: (int) disks; |
-(void) setPegFrom: (int) from andSetPegTo: (int) to andSetPegVia: (int) via andSetNumDisks: (int) disks; |
||
-(void) movePegFrom: (int) from andMovePegTo: (int) to andMovePegVia: (int) via andWithNumDisks: (int) disks; |
-(void) movePegFrom: (int) from andMovePegTo: (int) to andMovePegVia: (int) via andWithNumDisks: (int) disks; |
||
@end |
@end</lang> |
||
</lang> |
|||
The Implementation - TowersOfHanoi.m: |
The Implementation - TowersOfHanoi.m: |
||
<lang objc> |
<lang objc>#import "TowersOfHanoi.h" |
||
#import "TowersOfHanoi.h" |
|||
@implementation TowersOfHanoi |
@implementation TowersOfHanoi |
||
Line 574: | Line 553: | ||
} |
} |
||
@end |
@end</lang> |
||
</lang> |
|||
Test code: TowersTest.m: |
Test code: TowersTest.m: |
||
<lang objc> |
<lang objc>#import <stdio.h> |
||
#import <stdio.h> |
|||
#import "TowersOfHanoi.h" |
#import "TowersOfHanoi.h" |
||
Line 598: | Line 575: | ||
return 0; |
return 0; |
||
}</lang> |
|||
} |
|||
</lang> |
|||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
Line 633: | Line 609: | ||
I think it is standard pascal, except for the constant array "strPole". I am not sure if constant arrays are part of the standard. However, as far as I know, they are a "de facto" standard in every compiler. |
I think it is standard pascal, except for the constant array "strPole". I am not sure if constant arrays are part of the standard. However, as far as I know, they are a "de facto" standard in every compiler. |
||
<lang pascal> |
<lang pascal>program Hanoi; |
||
type |
|||
TPole = (tpLeft, tpCenter, tpRight); |
|||
const |
|||
strPole:array[TPole] of string[6]=('left','center','right'); |
|||
procedure MoveStack (const Ndisks : integer; const Origin,Destination,Auxiliary:TPole); |
|||
begin |
|||
if Ndisks >0 then begin |
|||
MoveStack(Ndisks - 1, Origin,Auxiliary, Destination ); |
|||
Writeln('Move disk ',Ndisks ,' from ',strPole[Origin],' to ',strPole[Destination]); |
|||
MoveStack(Ndisks - 1, Auxiliary, Destination, origin); |
|||
end; |
|||
end; |
|||
begin |
|||
MoveStack(4,tpLeft,tpCenter,tpRight); |
|||
end.</lang> |
|||
A little longer, but clearer for my taste |
A little longer, but clearer for my taste |
||
<lang pascal> |
<lang pascal>program Hanoi; |
||
type |
|||
TPole = (tpLeft, tpCenter, tpRight); |
|||
const |
|||
strPole:array[TPole] of string[6]=('left','center','right'); |
|||
procedure MoveOneDisk(const DiskNum:integer; const Origin,Destination:TPole); |
|||
begin |
|||
Writeln('Move disk ',DiskNum,' from ',strPole[Origin],' to ',strPole[Destination]); |
|||
end; |
|||
procedure MoveStack (const Ndisks : integer; const Origin,Destination,Auxiliary:TPole); |
|||
begin |
|||
if Ndisks =1 then |
|||
MoveOneDisk(1,origin,Destination) |
|||
else begin |
|||
MoveStack(Ndisks - 1, Origin,Auxiliary, Destination ); |
|||
MoveOneDisk(Ndisks,origin,Destination); |
|||
MoveStack(Ndisks - 1, Auxiliary, Destination, origin); |
|||
end; |
|||
end; |
|||
begin |
|||
MoveStack(4,tpLeft,tpCenter,tpRight); |
|||
end.</lang> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
Line 706: | Line 682: | ||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
<lang php> |
<lang php>function move($n,$from,$to,$via) { |
||
function move($n,$from,$to,$via) { |
|||
if ($n === 1) { |
if ($n === 1) { |
||
print("Move disk from pole $from to pole $to"); |
print("Move disk from pole $from to pole $to"); |
||
Line 715: | Line 690: | ||
move(n-1,$via,$to,From); |
move(n-1,$via,$to,From); |
||
} |
} |
||
}</lang> |
|||
} |
|||
</lang> |
|||
=={{header|Pop11}}== |
=={{header|Pop11}}== |
||
<lang pop11>define hanoi(n, src, dst, via); |
|||
if n > 0 then |
|||
hanoi(n - 1, src, via, dst); |
|||
'Move disk ' >< n >< ' from ' >< src >< ' to ' >< dst >< '.' => |
|||
hanoi(n - 1, via, dst, src); |
|||
endif; |
|||
enddefine; |
|||
hanoi(4, "left", "middle", "right");</lang> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||
Line 792: | Line 766: | ||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
||
<lang seed7>const proc: hanoi (in integer: disk, in string: source, in string: dest, in string: via) is func |
|||
begin |
|||
if disk > 0 then |
|||
hanoi(pred(disk), source, via, dest); |
|||
writeln("Move disk " <& disk <& " from " <& source <& " to " <& dest); |
|||
hanoi(pred(disk), via, dest, source); |
|||
end if; |
|||
end func;</lang> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
Line 837: | Line 811: | ||
=={{header|Toka}}== |
=={{header|Toka}}== |
||
<lang toka>value| sa sb sc n | |
|||
[ to sc to sb to sa to n ] is vars! |
|||
[ ( num from to via -- ) |
|||
vars! |
|||
n 0 <> |
|||
[ |
|||
n sa sb sc |
|||
n 1- sa sc sb recurse |
|||
vars! |
|||
." Move a ring from " sa . ." to " sb . cr |
|||
n 1- sc sb sa recurse |
|||
] ifTrue |
|||
] is hanoi</lang> |
|||
=={{header|UNIX Shell}}== |
=={{header|UNIX Shell}}== |
||
Line 855: | Line 829: | ||
{{works with|bash}} |
{{works with|bash}} |
||
<lang bash> |
<lang bash>#!/bin/bash |
||
#!/bin/bash |
|||
move() |
move() |
||
Line 875: | Line 848: | ||
} |
} |
||
move $1 $2 $3 $4 |
move $1 $2 $3 $4</lang> |
||
</lang> |
|||
=={{header|Ursala}}== |
=={{header|Ursala}}== |
||
<lang Ursala> |
<lang Ursala>#import nat |
||
#import nat |
|||
move = ~&al^& ^rlPlrrPCT/~&arhthPX ^|W/~& ^|G/predecessor ^/~&htxPC ~&zyxPC |
move = ~&al^& ^rlPlrrPCT/~&arhthPX ^|W/~& ^|G/predecessor ^/~&htxPC ~&zyxPC |
||
Line 886: | Line 857: | ||
#show+ |
#show+ |
||
main = ^|T(~&,' -> '--)* move/4 <'start','end','middle'> |
main = ^|T(~&,' -> '--)* move/4 <'start','end','middle'></lang> |
||
</lang> |
|||
output: |
output: |
||
<pre>start -> middle |
<pre>start -> middle |
||
Line 907: | Line 877: | ||
=={{header|Vedit macro language}}== |
=={{header|Vedit macro language}}== |
||
This implementation outputs the results in current edit buffer. |
This implementation outputs the results in current edit buffer. |
||
<lang vedit>#1=1; #2=2; #3=3; #4=4 // move 4 disks from 1 to 2 |
|||
<lang vedit> |
|||
#1=1; #2=2; #3=3; #4=4 // move 4 disks from 1 to 2 |
|||
Call("MOVE_DISKS") |
Call("MOVE_DISKS") |
||
Return |
Return |
||
Line 932: | Line 901: | ||
Num_Pop(1,4) |
Num_Pop(1,4) |
||
} |
} |
||
Return |
Return</lang> |
||
</lang> |
|||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
Line 949: | Line 917: | ||
MoveTowerDisks(4, 1, 2, 3) |
MoveTowerDisks(4, 1, 2, 3) |
||
End Sub |
End Sub |
||
End Module |
End Module</lang> |
||
</lang> |
|||
=={{header|XSLT}}== |
=={{header|XSLT}}== |
||
<lang xml><xsl:template name="hanoi"> |
|||
<xsl:param name="n"/> |
|||
<xsl:param name="from">left</xsl:param> |
|||
<xsl:param name="to">middle</xsl:param> |
|||
<xsl:param name="via">right</xsl:param> |
|||
<xsl:if test="$n > 0"> |
|||
<xsl:call-template name="hanoi"> |
|||
<xsl:with-param name="n" select="$n - 1"/> |
|||
<xsl:with-param name="from" select="$from"/> |
|||
<xsl:with-param name="to" select="$via"/> |
|||
<xsl:with-param name="via" select="$to"/> |
|||
</xsl:call-template> |
|||
<fo:block> |
|||
<xsl:text>Move disk from </xsl:text> |
|||
<xsl:value-of select="$from"/> |
|||
<xsl:text> to </xsl:text> |
|||
<xsl:value-of select="$to"/> |
|||
</fo:block> |
|||
<xsl:call-template name="hanoi"> |
|||
<xsl:with-param name="n" select="$n - 1"/> |
|||
<xsl:with-param name="from" select="$via"/> |
|||
<xsl:with-param name="to" select="$to"/> |
|||
<xsl:with-param name="via" select="$from"/> |
|||
</xsl:call-template> |
|||
</xsl:if> |
|||
</xsl:template></lang> |
|||
<xsl:call-template name="hanoi"><xsl:with-param name="n" select="4"/></xsl:call-template> |
<xsl:call-template name="hanoi"><xsl:with-param name="n" select="4"/></xsl:call-template> |
Revision as of 15:12, 22 November 2009
In this task, the goal is to solve the Towers of Hanoi problem with recursion.
ActionScript
<lang actionscript>public function move(n:int, from:int, to:int, via:int):void {
if (n > 0) { move(n - 1, from, via, to); trace("Move disk from pole " + from + " to pole " + to); move(n - 1, via, to, from); }
}</lang>
Ada
<lang ada>with Ada.Text_Io; use Ada.Text_Io;
procedure Towers is
type Pegs is (Left, Center, Right); procedure Hanoi (Ndisks : Natural; Start_Peg : Pegs := Left; End_Peg : Pegs := Right; Via_Peg : Pegs := Center) is begin if Ndisks > 0 then Hanoi(Ndisks - 1, Start_Peg, Via_Peg, End_Peg); Put_Line("Move disk" & Natural'Image(Ndisks) & " from " & Pegs'Image(Start_Peg) & " to " & Pegs'Image(End_Peg)); Hanoi(Ndisks - 1, Via_Peg, End_Peg, Start_Peg); end if; end Hanoi;
begin
Hanoi(4);
end Towers;</lang>
ALGOL 68
<lang algol68>PROC move = (INT n, from, to, via) VOID:
IF n > 0 THEN move(n - 1, from, via, to); printf(($"Move disk from pole "g" to pole "gl$, from, to)); move(n - 1, via, to, from) FI
main: (
move(4, 1,2,3)
)</lang>
AmigaE
<lang amigae>PROC move(n, from, to, via)
IF n > 0 move(n-1, from, via, to) WriteF('Move disk from pole \d to pole \d\n', from, to) move(n-1, via, to, from) ENDIF
ENDPROC
PROC main()
move(4, 1,2,3)
ENDPROC</lang>
AppleScript
<lang applescript>global moves --this is so the handler 'hanoi' can see the 'moves' variable set moves to "" hanoi(4, "peg A", "peg C", "peg B")
on hanoi(ndisks, fromPeg, toPeg, withPeg)
if ndisks is greater than 0 then hanoi(ndisks - 1, fromPeg, withPeg, toPeg) set moves to moves & "Move disk " & ndisks & " from " & fromPeg & " to " & toPeg & return hanoi(ndisks - 1, withPeg, toPeg, fromPeg) end if return moves
end hanoi</lang>
AutoHotkey
<lang AutoHotkey>move(n, from, to, via) ;n = # of disks, from = start pole, to = end pole, via = remaining pole {
if (n = 1) { msgbox , Move disk from pole %from% to pole %to% } else { move(n-1, from, via, to) move(1, from, to, via) move(n-1, via, to, from) }
}</lang>
AWK
<lang AWK>$ awk 'func hanoi(n,f,t,v){if(n>0){hanoi(n-1,f,v,t);print(f,"->",t);hanoi(n-1,v,t,f)}} BEGIN{hanoi(4,"left","middle","right")}' left -> right left -> middle right -> middle left -> right middle -> left middle -> right left -> right left -> middle right -> middle right -> left middle -> left right -> middle left -> right left -> middle right -> middle</lang>
BASIC
<lang freebasic> SUB move (n AS Integer, fromPeg AS Integer, toPeg AS Integer, viaPeg AS Integer)
IF n>0 THEN move n-1, fromPeg, viaPeg, toPeg PRINT "Move disk from "; fromPeg; " to "; toPeg move n-1, viaPeg, toPeg, fromPeg END IF
END SUB
move 4,1,2,3 </lang>
C
<lang c>#include <stdio.h>
void move(int n, int from, int to, int via) {
if (n > 0) { move(n - 1, from, via, to); printf("Move disk from pole %d to pole %d\n", from, to); move(n - 1, via, to, from); }
} int main() {
move(4, 1,2,3); return 0;
}</lang>
C#
<lang csharp>public void move(int n, int from, int to, int via) {
if (n == 1) { System.Console.WriteLine("Move disk from pole " + from + " to pole " + to); } else { move(n - 1, from, via, to); move(1, from, to, via); move(n - 1, via, to, from); } }</lang>
C++
<lang cpp>void move(int n, int from, int to, int via) {
if (n == 1) { std::cout << "Move disk from pole " << from << " to pole " << to << std::endl; } else { move(n - 1, from, via, to); move(1, from, to, via); move(n - 1, via, to, from); }
}</lang>
Clojure
<lang lisp>(defn towers-of-hanoi [n from to via]
(if (= n 1) (println (format "Move from %s to %s" from to)) (do (towers-of-hanoi (dec n) from via to) (println (format "Move from %s to %s" from to)) (recur (dec n) via to from))))</lang>
Common Lisp
<lang lisp>(defun move (n from to via)
(cond ((= n 1) (format t "Move from ~A to ~A.~%" from to)) (t (move (- n 1) from via to) (format t "Move from ~A to ~A.~%" from to) (move (- n 1) via to from))))</lang>
D
Recursive
<lang d>module hanoi; import std.stdio;
struct Hanoi { static Hanoi opCall(int n, string src, string dst, string via) { return (n > 0) ? Hanoi(n - 1, src, via, dst)(n, src, dst)(n - 1, via, dst, src) : Hanoi.init ; } static Hanoi opCall(int n, string src, string dst) { writefln("Move disk %s from %s to %s", n, src, dst) ; return Hanoi.init ; } }
void main() { Hanoi(3, "L","M","R") ; }</lang>
Iterative
ref : The shortest and "mysterious" TH algorithm <lang d>module hanoi; import std.stdio; import std.conv ;
void Hanoi(int n , string L /* from */, string M /* to */, string R /* via */) {
string[3] Pegs = [L,R,M] ; int nn = (1 << n) ; int x, fr, to, i, j ; for(x = 1 ; x < nn ; x++){ i = x & x - 1 ; fr = (i + i/3) & 3 ; i = (x | x - 1) + 1 ; to = (i + i/3) & 3 ; for(i = x, j = 1; !(i&1) ; i >>=1, j++) writefln("Move Disc %d from %s to %s", j, Pegs[fr], Pegs[to]) ; }
}
void main(string[] args) {
int n = (args.length > 1) ? to!(int)(args[1]) : 3 ; Hanoi(n, "L","M","R") ;
}</lang>
Dc
From Here
[ # move(from, to) n # print from [ --> ]n # print " --> " p # print to\n sw # p doesn't pop, so get rid of the value ]sm [ # init(n) sw # tuck n away temporarily 9 # sentinel as bottom of stack lw # bring n back 1 # "from" tower's label 3 # "to" tower's label 0 # processed marker ]si [ # Move() lt # push to lf # push from lmx # call move(from, to) ]sM [ # code block<lang dc> ln # push n lf # push from lt # push to 1 # push processed marker 1 ln # push n 1 # push 1 - # n - 1 lf # push from ll # push left 0 # push processed marker 0 ]sd [ # code block <e> ln # push n 1 # push 1 - # n - 1 ll # push left lt # push to 0 # push processed marker 0 ]se [ # code block <x> ln 1 =M ln 1 !=d ]sx [ # code block <y> lMx lex ]sy [ # quit() q # exit the program ]sq [ # run() d 9 =q # if stack empty, quit() sp # processed st # to sf # from sn # n 6 # lf # - # lt # - # 6 - from - to sl # lp 0 =x # lp 0 !=y # lrx # loop ]sr 5lix # init(n) lrx # run()
E
<lang e>def move(out, n, fromPeg, toPeg, viaPeg) {
if (n.aboveZero()) { move(out, n.previous(), fromPeg, viaPeg, toPeg) out.println(`Move disk $n from $fromPeg to $toPeg.`) move(out, n.previous(), viaPeg, toPeg, fromPeg) }
}
move(stdout, 4, def left {}, def right {}, def middle {})</lang>
Erlang
<lang erlang>move(1, F, T, _V) ->
io:format("Move from ~p to ~p~n", [F, T]);
move(N, F, T, V) ->
move(N-1, F, V, T), move(1 , F, T, V), move(N-1, V, T, F).</lang>
FALSE
<lang false>["Move disk from "$!\" to "$!\" "]p: { to from } [n;0>[n;1-n: @\ h;! @\ p;! \@ h;! \@ n;1+n:]?]h: { via to from } 4n:["right"]["middle"]["left"]h;!%%%</lang>
Forth
With locals:
<lang forth>CREATE peg1 ," left " CREATE peg2 ," middle " CREATE peg3 ," right "
- .$ COUNT TYPE ;
- MOVE-DISK
LOCALS| via to from n | n 1 = IF CR ." Move disk from " from .$ ." to " to .$ ELSE n 1- from via to RECURSE 1 from to via RECURSE n 1- via to from RECURSE THEN ;</lang>
Without locals, executable pegs:
<lang forth>: left ." left" ;
- right ." right" ;
- middle ." middle" ;
- move-disk ( v t f n -- v t f )
dup 0= if drop exit then 1- >R rot swap R@ ( t v f n-1 ) recurse rot swap 2dup cr ." Move disk from " execute ." to " execute swap rot R> ( f t v n-1 ) recurse swap rot ;
- hanoi ( n -- )
1 max >R ['] right ['] middle ['] left R> move-disk drop drop drop ;</lang>
Fortran
<lang fortran>PROGRAM TOWER
CALL Move(4, 1, 2, 3)
CONTAINS
RECURSIVE SUBROUTINE Move(ndisks, from, to, via) INTEGER, INTENT (IN) :: ndisks, from, to, via IF (ndisks == 1) THEN WRITE(*, "(A,I1,A,I1)") "Move disk from pole ", from, " to pole ", to ELSE CALL Move(ndisks-1, from, via, to) CALL Move(1, from, to, via) CALL Move(ndisks-1, via, to, from) END IF END SUBROUTINE Move
END PROGRAM TOWER</lang>
Haskell
Most of the programs on this page use an imperative approach (i.e., print out movements as side effects during program execution). Haskell favors a purely functional approach, where you would for example return a (lazy) list of movements from a to b via c:
<lang haskell>hanoi :: Integer -> a -> a -> a -> [(a, a)] hanoi 0 _ _ _ = [] hanoi n a b c = hanoi (n-1) a c b ++ [(a,b)] ++ hanoi (n-1) c b a</lang>
One can use this function to produce output, just like the other programs:
<lang haskell>hanoiIO n = mapM_ f $ hanoi n 1 2 3 where
f (x,y) = putStrLn $ "Move " ++ show x ++ " to " ++ show y</lang>
Or, instead one can of course also program imperatively, using the IO monad directly:
<lang haskell>hanoiM :: Integer -> IO () hanoiM n = hanoiM' n 1 2 3 where
hanoiM' 0 _ _ _ = return () hanoiM' n a b c = do hanoiM' (n-1) a c b putStrLn $ "Move " ++ show a ++ " to " ++ show b hanoiM' (n-1) c b a</lang>
Io
<lang io>hanoi := method(n, from, to, via,
if (n == 1) then ( writeln("Move from ", from, " to ", to) ) else ( hanoi(n - 1, from, via, to ) hanoi(1 , from, to , via ) hanoi(n - 1, via , to , from) )
)</lang>
J
<lang j>H =: i.@(,&2) ` (({&0 2 1,0 2,{&1 0 2)@$:@<:) @. *
H1=: monad define
if. *y do. ({&0 2 1 , 0 2 , {&1 0 2) H1 y-1 else. i.0 2 end.
)</lang> H employs anonymous recursion; H1 is an "explicit" statement of the same computation. For example: <lang j> H 3 0 2 0 1 2 1 0 2 1 2 1 0 2 0</lang> The result is a 2-column table; a row i,j is interpreted as: move a disk (the top disk) from peg i to peg j .
Java
<lang java>public void move(int n, int from, int to, int via) {
if (n == 1) { System.out.println("Move disk from pole " + from + " to pole " + to); } else { move(n - 1, from, via, to); move(1, from, to, via); move(n - 1, via, to, from); }
}</lang>
JavaScript
<lang javascript>function move(n, from, to, via) {
if (n > 0) { move(n-1, from, via, to) print("Move disk from " + from + " to " + to) move(n-1, via, to, from) }
} move(4, "left", "middle", "right")</lang>
Joy
From here <lang joy>DEFINE hanoi == [[rolldown] infra] dip
[ [ [null] [pop pop] ] [ [dup2 [[rotate] infra] dip pred] [ [dup rest put] dip [[swap] infra] dip pred ] [] ] ] condnestrec.</lang>
Using it (5 is the number of disks.) <lang joy>[source destination temp] 5 hanoi.</lang>
Logo
<lang logo>to move :n :from :to :via
if :n = 0 [stop] move :n-1 :from :via :to (print [Move disk from] :from [to] :to) move :n-1 :via :to :from
end move 4 "left "middle "right</lang>
Mathematica
<lang mathematica>Hanoi[0, from_, to_, via_] := Null Hanoi[n_Integer, from_, to_, via_] :=
(Hanoi[n-1, from, via, to]; Print["Move dist from pole ", from, " to ", to, "."]; Hanoi[n-1, via, from, to])</lang>
Modula-3
<lang modula3>MODULE Hanoi EXPORTS Main;
FROM IO IMPORT Put; FROM Fmt IMPORT Int;
PROCEDURE doHanoi(n, from, to, using: INTEGER) =
BEGIN IF n > 0 THEN doHanoi(n - 1, from, using, to); Put("move " & Int(from) & " --> " & Int(to) & "\n"); doHanoi(n - 1, using, to, from); END; END doHanoi;
BEGIN
doHanoi(4, 1, 2, 3);
END Hanoi.</lang>
Objective-C
From here
This has been tested on GNUstep compiler. But it should be compatible with XCode/Cocoa on MacOS too.
The Interface - TowersOfHanoi.h: <lang objc>#import <Foundation/NSObject.h>
@interface TowersOfHanoi: NSObject { int pegFrom; int pegTo; int pegVia; int numDisks; }
-(void) setPegFrom: (int) from andSetPegTo: (int) to andSetPegVia: (int) via andSetNumDisks: (int) disks; -(void) movePegFrom: (int) from andMovePegTo: (int) to andMovePegVia: (int) via andWithNumDisks: (int) disks; @end</lang>
The Implementation - TowersOfHanoi.m:
<lang objc>#import "TowersOfHanoi.h" @implementation TowersOfHanoi
-(void) setPegFrom: (int) from andSetPegTo: (int) to andSetPegVia: (int) via andSetNumDisks: (int) disks { pegFrom = from; pegTo = to; pegVia = via; numDisks = disks; }
-(void) movePegFrom: (int) from andMovePegTo: (int) to andMovePegVia: (int) via andWithNumDisks: (int) disks { if (disks == 1) {
printf("Move disk from pole %i to pole %i\n", from, to); } else { [self movePegFrom: from andMovePegTo: via andMovePegVia: to andWithNumDisks: disks-1];
[self movePegFrom: from andMovePegTo: to andMovePegVia: via andWithNumDisks: 1]; [self movePegFrom: via andMovePegTo: to andMovePegVia: from andWithNumDisks: disks-1];
}
}
@end</lang>
Test code: TowersTest.m:
<lang objc>#import <stdio.h>
- import "TowersOfHanoi.h"
int main( int argc, const char *argv[] ) { TowersOfHanoi *tower = [[TowersOfHanoi alloc] init];
int from = 1; int to = 3; int via = 2; int disks = 3;
[tower setPegFrom: from andSetPegTo: to andSetPegVia: via andSetNumDisks: disks];
[tower movePegFrom: from andMovePegTo: to andMovePegVia: via andWithNumDisks: disks];
[tower release];
return 0; }</lang>
OCaml
<lang ocaml>let rec hanoi n a b c =
if n <> 0 then begin hanoi (pred n) a c b; Printf.printf "Move disk from pole %d to pole %d\n" a b; hanoi (pred n) c b a end
let () =
hanoi 4 1 2 3</lang>
Octave
<lang octave>function hanoimove(ndisks, from, to, via)
if ( ndisks == 1 ) printf("Move disk from pole %d to pole %d\n", from, to); else hanoimove(ndisks-1, from, via, to); hanoimove(1, from, to, via); hanoimove(ndisks-1, via, to, from); endif
endfunction
hanoimove(4, 1, 2, 3);</lang>
Pascal
Compiler: Free Pascal (2.0.4)
I think it is standard pascal, except for the constant array "strPole". I am not sure if constant arrays are part of the standard. However, as far as I know, they are a "de facto" standard in every compiler.
<lang pascal>program Hanoi; type
TPole = (tpLeft, tpCenter, tpRight);
const
strPole:array[TPole] of string[6]=('left','center','right');
procedure MoveStack (const Ndisks : integer; const Origin,Destination,Auxiliary:TPole); begin if Ndisks >0 then begin MoveStack(Ndisks - 1, Origin,Auxiliary, Destination ); Writeln('Move disk ',Ndisks ,' from ',strPole[Origin],' to ',strPole[Destination]); MoveStack(Ndisks - 1, Auxiliary, Destination, origin); end; end;
begin
MoveStack(4,tpLeft,tpCenter,tpRight);
end.</lang>
A little longer, but clearer for my taste <lang pascal>program Hanoi; type
TPole = (tpLeft, tpCenter, tpRight);
const
strPole:array[TPole] of string[6]=('left','center','right');
procedure MoveOneDisk(const DiskNum:integer; const Origin,Destination:TPole); begin Writeln('Move disk ',DiskNum,' from ',strPole[Origin],' to ',strPole[Destination]); end;
procedure MoveStack (const Ndisks : integer; const Origin,Destination,Auxiliary:TPole); begin if Ndisks =1 then MoveOneDisk(1,origin,Destination) else begin MoveStack(Ndisks - 1, Origin,Auxiliary, Destination ); MoveOneDisk(Ndisks,origin,Destination); MoveStack(Ndisks - 1, Auxiliary, Destination, origin); end; end;
begin
MoveStack(4,tpLeft,tpCenter,tpRight);
end.</lang>
Perl
<lang perl>sub hanoi {
my ($n, $from, $to, $via) = (@_, 1, 2, 3);
if ($n == 1) { print "Move disk from pole $from to pole $to.\n"; } else { hanoi($n - 1, $from, $via, $to); hanoi(1, $from, $to, $via); hanoi($n - 1, $via, $to, $from); };
};</lang>
Perl 6
<lang perl6>subset Peg of Int where * == 1|2|3;
multi hanoi (0, Peg $a, Peg $b, Peg $c) { } multi hanoi (Int $n, Peg $a = 1, Peg $b = 2, Peg $c = 3) {
hanoi $n - 1, $a, $c, $b; say "Move $a to $b."; hanoi $n - 1, $c, $b, $a;
}</lang>
PHP
<lang php>function move($n,$from,$to,$via) {
if ($n === 1) { print("Move disk from pole $from to pole $to"); } else { move($n-1,$from,$via,$to); move(1,$from,$to,$via); move(n-1,$via,$to,From); }
}</lang>
Pop11
<lang pop11>define hanoi(n, src, dst, via); if n > 0 then
hanoi(n - 1, src, via, dst); 'Move disk ' >< n >< ' from ' >< src >< ' to ' >< dst >< '.' => hanoi(n - 1, via, dst, src);
endif; enddefine;
hanoi(4, "left", "middle", "right");</lang>
Python
<lang python>def hanoi(ndisks, startPeg=1, endPeg=3):
if ndisks: hanoi(ndisks-1, startPeg, 6-startPeg-endPeg) print "Move disk %d from peg %d to peg %d" % (ndisks, startPeg, endPeg) hanoi(ndisks-1, 6-startPeg-endPeg, endPeg)
hanoi(ndisks=4)</lang>
R
<lang R>hanoimove <- function(ndisks, from, to, via) {
if ( ndisks == 1 ) cat("move disk from", from, "to", to, "\n") else { hanoimove(ndisks-1, from, via, to) hanoimove(1, from, to, via) hanoimove(ndisks-1, via, to, from) }
}
hanoimove(4,1,2,3)</lang>
Ruby
<lang ruby>def hanoi n,from='left',to='middle',via='right'
return if n==0 hanoi (n-1), from, via, to puts "Move from #{from} to #{to}" hanoi (n-1), via, to, from
end</lang>
Scala
<lang scala>def move(n: int, from: int, to: int, via: int) = {
if (n == 1) { Console.println("Move disk from pole " + from + " to pole " + to) } else { move(n - 1, from, via, to) move(1, from, to, via) move(n - 1, via, to, from) } }</lang>
Scheme
<lang scheme>(define (hanoi n a b c)
(if (> n 0) (begin (hanoi (- n 1) a c b) (display "Move disk from pole ") (display a) (display " to pole ") (display b) (newline) (hanoi (- n 1) c b a))))
(hanoi 4 1 2 3)</lang>
Seed7
<lang seed7>const proc: hanoi (in integer: disk, in string: source, in string: dest, in string: via) is func
begin if disk > 0 then hanoi(pred(disk), source, via, dest); writeln("Move disk " <& disk <& " from " <& source <& " to " <& dest); hanoi(pred(disk), via, dest, source); end if; end func;</lang>
Tcl
The use of interp alias
shown is a sort of closure: keep track of the number of moves required
<lang tcl>interp alias {} hanoi {} do_hanoi 0
proc do_hanoi {count n {from A} {to C} {via B}} {
if {$n == 1} { interp alias {} hanoi {} do_hanoi [incr count] puts "$count: move from $from to $to" } else { incr n -1 hanoi $n $from $via $to hanoi 1 $from $to $via hanoi $n $via $to $from }
}
hanoi 4</lang> produces
1: move from A to B 2: move from A to C 3: move from B to C 4: move from A to B 5: move from C to A 6: move from C to B 7: move from A to B 8: move from A to C 9: move from B to C 10: move from B to A 11: move from C to A 12: move from B to C 13: move from A to B 14: move from A to C 15: move from B to C
Toka
<lang toka>value| sa sb sc n | [ to sc to sb to sa to n ] is vars! [ ( num from to via -- )
vars! n 0 <> [ n sa sb sc n 1- sa sc sb recurse vars! ." Move a ring from " sa . ." to " sb . cr n 1- sc sb sa recurse ] ifTrue
] is hanoi</lang>
UNIX Shell
<lang bash>#!/bin/bash
move() {
local n="$1" local from="$2" local to="$3" local via="$4"
if "$n" == "1" then echo "Move disk from pole $from to pole $to" else move $(($n - 1)) $from $via $to move 1 $from $to $via move $(($n - 1)) $via $to $from fi
}
move $1 $2 $3 $4</lang>
Ursala
<lang Ursala>#import nat
move = ~&al^& ^rlPlrrPCT/~&arhthPX ^|W/~& ^|G/predecessor ^/~&htxPC ~&zyxPC
- show+
main = ^|T(~&,' -> '--)* move/4 <'start','end','middle'></lang> output:
start -> middle start -> end middle -> end start -> middle end -> start end -> middle start -> middle start -> end middle -> end middle -> start end -> start middle -> end start -> middle start -> end middle -> end
Vedit macro language
This implementation outputs the results in current edit buffer. <lang vedit>#1=1; #2=2; #3=3; #4=4 // move 4 disks from 1 to 2 Call("MOVE_DISKS") Return
// Move disks // #1 = from, #2 = to, #3 = via, #4 = number of disks //
- MOVE_DISKS:
if (#4 > 0) {
Num_Push(1,4) #9=#2; #2=#3; #3=#9; #4-- // #1 to #3 via #2 Call("MOVE_DISKS") Num_Pop(1,4)
Ins_Text("Move a disk from ") // move one disk Num_Ins(#1, LEFT+NOCR) Ins_Text(" to ") Num_Ins(#2, LEFT)
Num_Push(1,4) #9=#1; #1=#3; #3 = #9; #4-- // #3 to #2 via #1 Call("MOVE_DISKS") Num_Pop(1,4)
} Return</lang>
Visual Basic .NET
<lang vbnet>Module TowersOfHanoi
Sub MoveTowerDisks(ByVal disks As Integer, ByVal fromTower As Integer, ByVal toTower As Integer, ByVal viaTower As Integer) If disks > 0 Then MoveTowerDisks(disks - 1, fromTower, viaTower, toTower) System.Console.WriteLine("Move disk {0} from {1} to {2}", disks, fromTower, toTower) MoveTowerDisks(disks - 1, viaTower, toTower, fromTower) End If End Sub
Sub Main() MoveTowerDisks(4, 1, 2, 3) End Sub
End Module</lang>
XSLT
<lang xml><xsl:template name="hanoi"> <xsl:param name="n"/> <xsl:param name="from">left</xsl:param> <xsl:param name="to">middle</xsl:param> <xsl:param name="via">right</xsl:param>
<xsl:if test="$n > 0"> <xsl:call-template name="hanoi"> <xsl:with-param name="n" select="$n - 1"/> <xsl:with-param name="from" select="$from"/> <xsl:with-param name="to" select="$via"/> <xsl:with-param name="via" select="$to"/> </xsl:call-template> <fo:block> <xsl:text>Move disk from </xsl:text> <xsl:value-of select="$from"/> <xsl:text> to </xsl:text> <xsl:value-of select="$to"/> </fo:block> <xsl:call-template name="hanoi"> <xsl:with-param name="n" select="$n - 1"/> <xsl:with-param name="from" select="$via"/> <xsl:with-param name="to" select="$to"/> <xsl:with-param name="via" select="$from"/> </xsl:call-template> </xsl:if>
</xsl:template></lang>
<xsl:call-template name="hanoi"><xsl:with-param name="n" select="4"/></xsl:call-template>
- Programming Tasks
- Puzzles
- Recursion
- Games
- Classic CS problems and programs
- ActionScript
- Ada
- ALGOL 68
- AmigaE
- AppleScript
- AutoHotkey
- AWK
- BASIC
- C
- C sharp
- C++
- Clojure
- Common Lisp
- D
- Dc
- E
- Erlang
- FALSE
- Forth
- Fortran
- Haskell
- Io
- J
- Java
- JavaScript
- Joy
- Logo
- Mathematica
- Modula-3
- Objective-C
- OCaml
- Octave
- Pascal
- Perl
- Perl 6
- PHP
- Pop11
- Python
- R
- Ruby
- Scala
- Scheme
- Seed7
- Tcl
- Toka
- UNIX Shell
- Ursala
- Vedit macro language
- Visual Basic .NET
- XSLT