Towers of Hanoi
In this task, the goal is to solve the Towers of Hanoi problem with recursion.
Ada
<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;
</ada>
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) )
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
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; }
C++
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); } }
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))))
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") ; }
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 {})
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).
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 ;
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
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
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) ) )
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 .
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); } }
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")
Joy
From here
DEFINE hanoi == [[rolldown] infra] dip [ [ [null] [pop pop] ] [ [dup2 [[rotate] infra] dip pred] [ [dup rest put] dip [[swap] infra] dip pred ] [] ] ] condnestrec.
Using it (5 is the number of disks.)
[source destination temp] 5 hanoi.
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
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])
OCaml
<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</ocaml>
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.
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); }; };
PHP
<?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); } } ?>
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");
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)
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
Scheme
<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)</scheme>
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;
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
UNIX Shell
<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 </bash>
XSLT
<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>
<xsl:call-template name="hanoi"><xsl:with-param name="n" select="4"/></xsl:call-template>