Towers of Hanoi: Difference between revisions

 

=={{header|ActionScript}}==

{{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)}}

left -> middle

right -> middle

left -> right

left -> middle

 

=={{header|BASIC}}==

{{works with|FreeBASIC}}

{{works with|RapidQ}}

IF n>0 THEN

move n-1, fromPeg, viaPeg, toPeg

END SUB

 

Here's an example of implementing recursion in an old BASIC that only has global variables:

{{works with|Commodore_BASIC}}

<lang freebasic>10 DIM N(1024), F(1024), T(1024), V(1024): REM STACK PER PARAMETER

 

=={{header|Clojure}}==

<lang lisp>(defn towers-of-hanoi [n from to via]

(if (= n 1)

 

=={{header|CoffeeScript}}==

if ndisks

staging_peg = 1 + 2 + 3 - start_peg - end_peg

hanoi(ndisks-1, staging_peg, end_peg)

 

=={{header|Common Lisp}}==

<lang lisp>(defun move (n from to via)

(cond ((= n 1)

hanoi(3, 'L', 'M', 'R');

}</lang>

<pre>Move disk 1 from L to M

Move disk 2 from L to R

Move disk 2 from R to M

Move disk 1 from L to M</pre>

===Iterative===

Fast iterative version. See: [http://hanoitower.mkolar.org/shortestTHalgo.html The shortest and "mysterious" TH algorithm]

}

}</lang>

<pre>| 3 2 1

|

 

hanoi(3,3,1,2);

<pre>move 1 ---> 3

move 1 ---> 2

move 1 ---> 3

</pre>

=={{header|Dc}}==

From [http://se.aminet.net/pub/OpenBSD/src/regress/usr.bin/dc/t20.in Here]

 

=={{header|E}}==

<lang e>def move(out, n, fromPeg, toPeg, viaPeg) {

if (n.aboveZero()) {

 

move(3, "left", "right", "middle")</lang>

<pre>Move disk 1 from the left pole to the right pole

Move disk 2 from the left pole to the middle pole

</pre>

 

<lang fsharp>#light

let rec hanoi num start finish =

=={{header|Forth}}==

With locals:

<lang forth>CREATE peg1 ," left "

CREATE peg2 ," middle "

n 1- via to from RECURSE

THEN ;</lang>

Without locals, executable pegs:

<lang forth>: left ." left" ;

: right ." right" ;

 

END PROGRAM TOWER</lang>

=={{header|GAP}}==

<lang gap>Hanoi := function(n)

 

=={{header|Go}}==

 

import "fmt"

func (t *towers) move1(from, to int) {

fmt.Println("move disk from rod", from, "to rod", to)

 

=={{header|Groovy}}==

moveStack(tail(using, n-1), to, from)

}</lang>

Test program:

<lang groovy>enum Ring {

 

=={{header|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' (n-1) c b a</lang>

 

The following is based on a solution in the Unicon book.

<lang Icon>procedure main(arglist)

hanoi(arglist[1]) | stop("Usage: hanoi n\n\rWhere n is the number of disks to move.")

return

end</lang>

 

=={{header|Inform 7}}==

'''Solutions'''

<lang j>H =: i.@,&2 ` (({&0 2 1,0 2,{&1 0 2)@$:@<:) @. * NB. tacit using anonymous recursion</lang>

<lang j> H 3

0 2

2 0</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> .

Or, using explicit rather than implicit code:

<lang j>H1=: monad define NB. explicit equivalent of H

if. y do.

end.

)</lang>

The usage here is the same:

<pre> H1 2

0 1

0 2

1 2</pre>

If a textual display is desired, similar to some of the other solutions here (counting from 1 instead of 0, tracking which disk is on the top of the stack, and of course formatting the result for a human reader instead of providing a numeric result):

<lang J>hanoi=: monad define

moves=. H y

('move disk ';' from peg ';' to peg ');@,."1 ":&.>disks,.1+moves

)</lang>

<lang J> hanoi 3

move disk 1 from peg 1 to peg 3

 

=={{header|Java}}==

<lang java>public void move(int n, int from, int to, int via) {

if (n == 1) {

2:1->2

1:3->2</lang>

The disk to move in the i'th step is the same as the position of the leftmost 1 in the binary representation of 1..2^n.

<lang K> s:();{[n;a;b;c]if[n>0;_f[n-1;a;c;b];s,:n;_f[n-1;c;b;a]]}[4;1;2;3];s

=={{header|Liberty BASIC}}==

This looks much better with a GUI interface.

via$ ="B"

target$ ="C"

end sub

 

 

=={{header|Logo}}==

 

=={{header|Lua}}==

if n > 0 then

move(n - 1, src, via, dst)

end

 

 

=={{header|Mathematica}}==

 

=={{header|MATLAB}}==

This is a direct translation from the Python example given in the Wikipedia entry for the Tower of Hanoi puzzle.

<lang MATLAB>function towerOfHanoi(n,A,C,B)

end

end</lang>

<lang MATLAB>towerOfHanoi(3,1,3,2)

Move plate 1 from tower 1 to tower 3

hanoi(4, "1", "2", "3")</lang>

<pre>Move disk 1 from 1 to 3

Move disk 2 from 1 to 2

Move disk 2 from 1 to 2

Move disk 1 from 3 to 2</pre>

=={{header|NewLISP}}==

(if (> n 0)

(move (- n 1) from via to

(print "move disk from pole " from " to pole " to "\n")

(move (- n 1) via to from))))

 

(move 4 1 2 3)</lang>

From [http://sites.google.com/site/vinodkshukla/code-snippets/objectivec-towersofhanoi here]

 

 

The Interface - TowersOfHanoi.h:

-(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

 

@end</lang>

Test code: TowersTest.m:

<lang objc>#import <stdio.h>

#import "TowersOfHanoi.h"

 

=={{header|OCaml}}==

<lang ocaml>let rec hanoi n a b c =

if n <> 0 then begin

 

=={{header|Octave}}==

<lang octave>function hanoimove(ndisks, from, to, via)

if ( ndisks == 1 )

 

=={{header|Pascal}}==

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

MoveStack(4,tpLeft,tpCenter,tpRight);

end.</lang>

A little longer, but clearer for my taste

<lang pascal>program Hanoi;

=={{header|Perl 6}}==

{{works with|Rakudo|#22 "Thousand Oaks"}}

<lang perl6>subset Peg of Int where * == 1|2|3;

 

 

=={{header|Pop11}}==

<lang pop11>define hanoi(n, src, dst, via);

if n > 0 then

 

=={{header|PL/I}}==

 

call Move (4,1,2,3);

end Move;

 

 

=={{header|PostScript}}==

=={{header|Prolog}}==

From Programming in Prolog by W.F. Clocksin & C.S. Mellish

 

move(0,_,_,_) :- !.

move(M,C,B,A).

 

 

=={{header|PureBasic}}==

Algorithm according to http://en.wikipedia.org/wiki/Towers_of_Hanoi

<lang PureBasic>Procedure Hanoi(n, A.s, C.s, B.s)

EndIf

EndProcedure</lang>

Full program

<lang PureBasic>Procedure Hanoi(n, A.s, C.s, B.s)

PrintN(#CRLF$+"Press ENTER to exit."): Input()

EndIf</lang>

Moving 3 pegs.

 

=={{header|Python}}==

<lang python>def hanoi(ndisks, startPeg=1, endPeg=3):

if ndisks:

 

hanoi 4</lang>

<pre>left -> right

left -> middle

 

=={{header|Retro}}==

 

: vars !c !b !a !n ;

] ifTrue ;

 

 

=={{header|REXX}}==

===version 1===

 

arg z .

dsk: move=move+1

say 'step' right(move,length(moves))": move disk " arg(1) '-->' arg(2)

step 1: move disk 1 --> 3

step 2: move disk 1 --> 2

The minimum number of moves to solve a 3 ring Tower of Hanoi is 7.

</pre>

<pre style="height:30ex;overflow:scroll">

step 1: move disk 1 --> 2

The minimum number of moves to solve a 4 ring Tower of Hanoi is 15.

</pre>

===version 2===

This version pictorially shows the moves for solving the Town of Hanoi.

 

arg z .

call showtowers

return

 

 

if _p\='' then say _p

end

<pre style="height:50ex;overflow:scroll">

░░

 

The minimum number of moves for a 3 ring Tower of Hanoi is 7

</pre>

 

=={{header|Ruby}}==

<lang ruby>def move(num_disks, starting_stick, target_stick, using_stick)

if num_disks == 1

 

=={{header|Scala}}==

<lang scala>def move(n: int, from: int, to: int, via: int) = {

if (n == 1) {

}

}</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 {

 

=={{header|Scheme}}==

<lang scheme>(define (hanoi n a b c)

(if (> n 0)

 

=={{header|Seed7}}==

<lang seed7>const proc: hanoi (in integer: disk, in string: source, in string: dest, in string: via) is func

begin

 

=={{header|SNOBOL4}}==

<lang SNOBOL4>* # Note: count is global

 

hanoi(4,'A','C','B')

end</lang>

<pre>1: Move disc from A to B

2: Move disc from A to C

 

hanoi 4</lang>

<pre>1: move from A to B

2: move from A to C

 

=={{header|Toka}}==

<lang toka>value| sa sb sc n |

[ to sc to sb to sa to n ] is vars!

] ifTrue

] is hanoi</lang>

 

=={{header|TSE SAL}}==

PROC PROCProgramRunTowersofhanoiRecursiveSub( INTEGER totalDiskI, STRING fromS, STRING toS, STRING viaS, INTEGER bufferI )

IF ( totalDiskI == 0 )

IF ( NOT ( Ask( "program: run: towersofhanoi: recursive: totalDiskI = ", s1, _EDIT_HISTORY_ ) ) AND ( Length( s1 ) > 0 ) ) RETURN() ENDIF

PROCProgramRunTowersofhanoiRecursive( Val( s1 ), "source", "target", "via" )

 

=={{header|UNIX Shell}}==

{{works with|bash}}

<lang bash>#!/bin/bash

 

 

main = ^|T(~&,' -> '--)* move/4 <'start','end','middle'></lang>

<pre>start -> middle

start -> end

 

=={{header|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)

 

=={{header|XQuery}}==

$to as xs:integer, $via as xs:integer) as element()*

{

local:hanoi(4, 1, 2, 3)

}

<hanoi>

<move disk="1">

<to>2</to>

</move>