Towers of Hanoi
From Rosetta Code
Puzzle
This is a programming puzzle. It lays out a problem which Rosetta Code users are encouraged to solve, using languages and techniques they know. Multiple approaches are not discouraged, so long as the puzzle guidelines are followed.
Code examples should be formatted along the lines of one of the existing prototypes.
For other Puzzles, see Category:PuzzlesContents |
[edit] 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;
[edit] ALGOL 68
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)
)
[edit] 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
[edit] 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;
}
[edit] C++
Works with: g++
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);
}
}
[edit] Common 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))))
[edit] 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") ;
}
The following is iterative approach.
ref : The shortest and "mysterious" TH algorithm
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") ;
}
[edit] 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 {})
[edit] Forth
With locals:
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 ;
Without locals, executable pegs:
: 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 ;
[edit] 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:
hanoi :: Integer -> a -> a -> a -> [(a, a)] hanoi = hanoi' [] where hanoi' k 0 _ _ _ = k hanoi' k n a b c = hanoi' ((a,b):(hanoi' k (n-1) c b a)) (n-1) a c b
Here hanoi' uses an accumulator argument for the "following" moves.
One can use this function to produce output, just like the other programs:
hanoiIO n = mapM_ f $ hanoi n 1 2 3 where f (x,y) = putStrLn $ "Move " ++ show x ++ " to " ++ show y
Or, instead one can of course also program imperatively, using the IO monad directly:
hanoiM :: Integer -> IO ()
hanoiM n = hanoiM' n 1 2 3 where
hanoiM' 0 a b c = 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
[edit] J
H =: i.@(,&2) ` (({&0 2 1,0 2,{&1 0 2)@$:@<:) @. *
H1=: 3 : 'if. *y do. ({&0 2 1 , 0 2 , {&1 0 2) H1 y-1 else. i.0 2 end.'
H employs anonymous recursion; H1 is an "explicit" statement of the same computation. For example:
H 3 0 2 0 1 2 1 0 2 1 2 1 0 2 0
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 .
[edit] 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);
}
}
[edit] 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")
[edit] 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
[edit] 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])
[edit] 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
[edit] 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.
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.
A little longer, but clearer for my taste
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.
[edit] Perl
sub move {
my ($n, $from, $to, $via) = @_;
if ($n == 1) {
print "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);
};
};
[edit] PHP
Translation of: Java
<?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);
}
}
?>
[edit] 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");
[edit] 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)
[edit] Ruby
def hanoi n,a='left',b='middle',c='right'
return if n==0
hanoi (n-1),a,c,b
puts "Move from #{a} to #{b}"
hanoi (n-1),c,b,a
end
[edit] 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;
[edit] 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
Categories: Less Than 20 Examples | Programming Tasks | Puzzles | Recursion | Ada | ALGOL 68 | AppleScript | C | C++ | Common Lisp | D | E | Forth | Haskell | J | Java | JavaScript | Logo | Mathematica | OCaml | Pascal | Perl | PHP | Pop11 | Python | Ruby | Seed7 | Toka
