Towers of Hanoi: Difference between revisions
+Icon+Unicon |
|||
Line 445: | Line 445: | ||
procedure hanoi(n, needle1, needle2) #: solve towers of hanoi by moving n disks from needle 1 to needle2 via other |
procedure hanoi(n, needle1, needle2) #: solve towers of hanoi by moving n disks from needle 1 to needle2 via other |
||
local other |
local other |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
if n = 1 then |
if n = 1 then |
||
write("Move disk from ", needle1, " to ", needle2) |
write("Move disk from ", needle1, " to ", needle2) |
||
else { |
else { |
||
other := 6 - needle1 - needle2 # clever but somewhat un-iconish way to find other |
other := 6 - needle1 - needle2 # clever but somewhat un-iconish way to find other |
||
hanoi(n-1, needle1, other) |
hanoi(n-1, needle1, other) |
||
write("Move disk from ", needle1, " to ", needle2) |
write("Move disk from ", needle1, " to ", needle2) |
||
hanoi(n-1, other, needle2) |
hanoi(n-1, other, needle2) |
||
} |
} |
||
return |
return |
||
end</lang> |
end</lang> |
||
==={{header|Unicon}}=== |
==={{header|Unicon}}=== |
||
This Icon solution works in Unicon. |
This Icon solution works in Unicon. |
Revision as of 23:29, 23 April 2010
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>
Agena
<lang agena>move := proc(n::number, src::number, dst::number, via::number) is
if n > 0 then move(n - 1, src, via, dst) print(src & ' to ' & dst) move(n - 1, via, dst, src) fi
end
move(4, 1, 2, 3)</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>
AutoIt
<lang AutoIt>Func move($n, $from, $to, $via) If ($n = 1) Then ConsoleWrite(StringFormat("Move disk from pole "&$from&" To pole "&$to&"\n")) Else move($n - 1, $from, $via, $to) move(1, $from, $to, $via) move($n - 1, $via, $to, $from) EndIf EndFunc
move(4, 1,2,3)</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>
Icon and Unicon
The following is based on a solution in the Unicon book.
Icon
<lang Icon>procedure main(arglist) hanoi(arglist[1]) | stop("Usage: hanoi n\n\rWhere n is the number of disks to move.") end
- procedure hanoi(n:integer, needle1:1, needle2:2) # unicon shorthand for icon code 1,2,3 below
procedure hanoi(n, needle1, needle2) #: solve towers of hanoi by moving n disks from needle 1 to needle2 via other local other
n := integer(0 < n) | runerr(n,101) # 1 ensure integer (this also ensures it's positive too) /needle1 := 1 # 2 default /needle2 := 2 # 3 default
if n = 1 then
write("Move disk from ", needle1, " to ", needle2)
else {
other := 6 - needle1 - needle2 # clever but somewhat un-iconish way to find other hanoi(n-1, needle1, other) write("Move disk from ", needle1, " to ", needle2) hanoi(n-1, other, needle2)
} return end</lang>
Unicon
This Icon solution works in Unicon.
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>
Ioke
<lang ioke> = method(n, f, u, t,
if(n < 2, "#{f} --> #{t}" println,
H(n - 1, f, t, u) "#{f} --> #{t}" println H(n - 1, u, f, t) )
)
hanoi = method(n,
H(n, 1, 2, 3)
)</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>
Lua
<lang Lua> function move(n, src, dst, via)
if n > 0 then move(n - 1, src, via, dst) print(src, 'to', dst) move(n - 1, via, dst, src) end
end
move(4, 1, 2, 3) </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>
Nimrod
<lang Python>proc hanoi(disks: int, fromTower: string, toTower: string, viaTower: string) =
if disks != 0: hanoi(disks - 1, fromTower, viaTower, toTower) echo("Move disk ", disks, " from ", fromTower, " to ", toTower) hanoi(disks - 1, viaTower, toTower, fromTower)
hanoi(4, "1", "2", "3")</lang> Output: <lang>Move disk 1 from 1 to 3 Move disk 2 from 1 to 2 Move disk 1 from 3 to 2 Move disk 3 from 1 to 3 Move disk 1 from 2 to 1 Move disk 2 from 2 to 3 Move disk 1 from 1 to 3 Move disk 4 from 1 to 2 Move disk 1 from 3 to 2 Move disk 2 from 3 to 1 Move disk 1 from 2 to 1 Move disk 3 from 3 to 2 Move disk 1 from 1 to 3 Move disk 2 from 1 to 2 Move disk 1 from 3 to 2</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>
Oz
<lang oz>declare
proc {TowersOfHanoi N From To Via} if N > 0 then {TowersOfHanoi N-1 From Via To} {System.showInfo "Move from "#From#" to "#To} {TowersOfHanoi N-1 Via To From} end end
in
{TowersOfHanoi 4 left middle right}</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>
PicoLisp
<lang PicoLisp>(de move (N A B C) # Use: (move 3 'left 'center 'right)
(unless (=0 N) (move (dec N) A C B) (println 'Move 'disk 'from A 'to B) (move (dec N) C B A) ) )</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>
PL/I
<lang PL/I> /* From Rosetta Fortran */ tower: proc options (main);
call Move (4,1,2,3);
Move: procedure (ndiscs, from, to, via) recursive;
declare (ndiscs, from, to, via) fixed binary;
if ndiscs = 1 then put skip edit ('Move disc from pole ', trim(from), ' to pole ', trim(to) ) (a); else do; call Move (ndiscs-1, from, via, to); call Move (1, from, to, via); call Move (ndiscs-1, via, to, from); end;
end Move;
end tower; </lang>
PureBasic
Algorithm according to http://en.wikipedia.org/wiki/Towers_of_Hanoi <lang PureBasic>Procedure Hanoi(n, A.s, C.s, B.s)
If n Hanoi(n-1, A, B, C) PrintN("Move the plate from "+A+" to "+C) Hanoi(n-1, B, C, A) EndIf
EndProcedure</lang>
Full program <lang PureBasic>Procedure Hanoi(n, A.s, C.s, B.s)
If n Hanoi(n-1, A, B, C) PrintN("Move the plate from "+A+" to "+C) Hanoi(n-1, B, C, A) EndIf
EndProcedure
If OpenConsole()
Define n=3 PrintN("Moving "+Str(n)+" pegs."+#CRLF$) Hanoi(n,"Left Peg","Middle Peg","Right Peg") PrintN(#CRLF$+"Press ENTER to exit."): Input()
EndIf</lang>
Outputs
Moving 3 pegs. Move the plate from Left Peg to Middle Peg Move the plate from Left Peg to Right Peg Move the plate from Middle Peg to Right Peg Move the plate from Left Peg to Middle Peg Move the plate from Right Peg to Left Peg Move the plate from Right Peg to Middle Peg Move the plate from Left Peg to Middle Peg Press ENTER to exit.
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>
REBOL
<lang REBOL>REBOL [ Title: "Towers of Hanoi" Author: oofoe Date: 2009-12-08 URL: http://rosettacode.org/wiki/Towers_of_Hanoi ]
hanoi: func [ {Begin moving the golden disks from one pole to the next. Note: when last disk moved, the world will end.} disks [integer!] "Number of discs on starting pole." /poles "Name poles." from to via ][
if disks = 0 [return]
if not poles [from: 'left to: 'middle via: 'right]
hanoi/poles disks - 1 from via to
print [from "->" to]
hanoi/poles disks - 1 via to from
]
hanoi 4</lang>
Output:
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
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>
Sather
<lang sather>class MAIN is
move(ndisks, from, to, via:INT) is if ndisks = 1 then #OUT + "Move disk from pole " + from + " to pole " + to + "\n"; else move(ndisks-1, from, via, to); move(1, from, to, via); move(ndisks-1, via, to, from); end; end;
main is move(4, 1, 2, 3); end;
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>
This next example is from http://gist.github.com/66925 it is a translation to Scala of a Prolog solution and solves the problem at compile time <lang scala>object TowersOfHanoi {
import scala.reflect.Manifest def simpleName(m:Manifest[_]):String = { val name = m.toString name.substring(name.lastIndexOf('$')+1) } trait Nat final class _0 extends Nat final class Succ[Pre<:Nat] extends Nat type _1 = Succ[_0] type _2 = Succ[_1] type _3 = Succ[_2] type _4 = Succ[_3] case class Move[N<:Nat,A,B,C]() implicit def move0[A,B,C](implicit a:Manifest[A],b:Manifest[B]):Move[_0,A,B,C] = { System.out.println("Move from "+simpleName(a)+" to "+simpleName(b));null } implicit def moveN[P<:Nat,A,B,C](implicit m1:Move[P,A,C,B],m2:Move[_0,A,B,C],m3:Move[P,C,B,A]) :Move[Succ[P],A,B,C] = null def run[N<:Nat,A,B,C](implicit m:Move[N,A,B,C]) = null case class Left() case class Center() case class Right() def main(args:Array[String]){ run[_2,Left,Right,Center] }
}</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
- Agena
- ALGOL 68
- AmigaE
- AppleScript
- AutoHotkey
- AutoIt
- AWK
- BASIC
- C
- C sharp
- C++
- Clojure
- Common Lisp
- D
- Dc
- E
- Erlang
- FALSE
- Forth
- Fortran
- Haskell
- Icon
- Unicon
- Io
- Ioke
- J
- Java
- JavaScript
- Joy
- Logo
- Lua
- Mathematica
- Modula-3
- Nimrod
- Objective-C
- OCaml
- Octave
- Oz
- Pascal
- Perl
- Perl 6
- PHP
- PicoLisp
- Pop11
- PL/I
- PureBasic
- Python
- R
- REBOL
- Ruby
- Sather
- Scala
- Scheme
- Seed7
- Tcl
- Toka
- UNIX Shell
- Ursala
- Vedit macro language
- Visual Basic .NET
- XSLT