Towers of Hanoi: Difference between revisions
Added Uiua solution
(Towers of Hanoi in XBasic) |
(Added Uiua solution) |
||
(18 intermediate revisions by 11 users not shown) | |||
Line 419:
</syntaxhighlight>
=={{header|ABC}}==
<syntaxhighlight lang="ABC">HOW TO MOVE n DISKS FROM src VIA via TO dest:
IF n>0:
MOVE n-1 DISKS FROM src VIA dest TO via
WRITE "Move disk from pole", src, "to pole", dest/
MOVE n-1 DISKS FROM via VIA dest TO src
MOVE 4 DISKS FROM 1 VIA 2 TO 3</syntaxhighlight>
{{out}}
<pre>Move disk from pole 1 to pole 2
Move disk from pole 1 to pole 3
Move disk from pole 2 to pole 1
Move disk from pole 1 to pole 2
Move disk from pole 3 to pole 2
Move disk from pole 3 to pole 1
Move disk from pole 2 to pole 3
Move disk from pole 1 to pole 3
Move disk from pole 2 to pole 1
Move disk from pole 2 to pole 3
Move disk from pole 1 to pole 2
Move disk from pole 2 to pole 1
Move disk from pole 3 to pole 1
Move disk from pole 3 to pole 2
Move disk from pole 1 to pole 3</pre>
=={{header|Action!}}==
Line 1,084 ⟶ 1,109:
Here's an example of implementing recursion in an old BASIC that only has global variables:
{{works with|Applesoft BASIC}}
{{works with|Chipmunk Basic}}
{{works with|Commodore BASIC}}
{{works with|GW-BASIC}}
{{works with|MSX_BASIC}}
<syntaxhighlight lang="gwbasic">10 DEPTH=4: REM SHOULD EQUAL NUMBER OF DISKS
20 DIM N(DEPTH), F(DEPTH), T(DEPTH), V(DEPTH): REM STACK PER PARAMETER
Line 1,115 ⟶ 1,142:
===Using binary method===
{{works with|Chipmunk Basic}}
{{works with|Commodore BASIC}}
Very fast version in BASIC V2 on Commodore C-64
{{works with|MSX_BASIC}}
<syntaxhighlight lang="gwbasic"> 10 DEF FNM3(X)=X-INT(X/3)*3:REM MODULO 3
20 N=4:GOSUB 100
Line 1,142 ⟶ 1,171:
15: 3 TO 2 </pre>
==={{header|BASIC256}}===
<syntaxhighlight lang="basic256">call move(4,1,2,3)
print "Towers of Hanoi puzzle completed!"
Line 1,174 ⟶ 1,203:
Towers of Hanoi puzzle completed!
</pre>
==={{header|IS-BASIC}}===
<syntaxhighlight lang="is-basic">100 PROGRAM "Hanoi.bas"
110 CALL HANOI(4,1,3,2)
120 DEF HANOI(DISK,FRO,TO,WITH)
130 IF DISK>0 THEN
140 CALL HANOI(DISK-1,FRO,WITH,TO)
150 PRINT "Move disk";DISK;"from";FRO;"to";TO
160 CALL HANOI(DISK-1,WITH,TO,FRO)
170 END IF
180 END DEF</syntaxhighlight>
=={{header|Batch File}}==
Line 1,289 ⟶ 1,329:
=={{header|Befunge}}==
This is loosely based on the [[Towers_of_Hanoi#Python|Python]] sample. The number of disks is specified by the first integer on the stack (the initial character <tt>4</tt> in the example below). If you want the program to prompt the user for that value, you can replace the <tt>4</tt> with a <tt>&</tt> (the read integer command).
Line 1,631 ⟶ 1,670:
}
}</syntaxhighlight>
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
{{trans|FreeBASIC}}
<syntaxhighlight lang="qbasic">100 cls
110 print "Three disks" : print
120 hanoi(3,1,2,3)
130 print chr$(10)"Four disks" chr$(10)
140 hanoi(4,1,2,3)
150 print : print "Towers of Hanoi puzzle completed!"
160 end
170 sub hanoi(n,desde,hasta,via)
180 if n > 0 then
190 hanoi(n-1,desde,via,hasta)
200 print "Move disk " n "from pole " desde "to pole " hasta
210 hanoi(n-1,via,hasta,desde)
220 endif
230 end sub</syntaxhighlight>
=={{header|Clojure}}==
Line 2,165 ⟶ 2,222:
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
proc hanoi n src dst aux . .
hanoi n - 1 aux dst src
.
.
</syntaxhighlight>
=={{header|EDSAC order code}}==
Line 2,447 ⟶ 2,506:
(message "Move from %S to %S" from to)
(move (- n 1) via to from)))</syntaxhighlight>
=={{header|EMal}}==
{{trans|C#}}
<syntaxhighlight lang="emal">
fun move = void by int n, int from, int to, int via
if n == 1
writeLine("Move disk from pole " + from + " to pole " + to)
return
end
move(n - 1, from, via, to)
move(1, from, to, via)
move(n - 1, via, to, from)
end
move(3, 1, 2, 3)
</syntaxhighlight>
{{out}}
<pre>
Move disk from pole 1 to pole 2
Move disk from pole 1 to pole 3
Move disk from pole 2 to pole 3
Move disk from pole 1 to pole 2
Move disk from pole 3 to pole 1
Move disk from pole 3 to pole 2
Move disk from pole 1 to pole 2
</pre>
=={{header|Erlang}}==
Line 2,950 ⟶ 3,034:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Tower_of_Hanoi}}
'''Solution'''
[[File:Fōrmulæ - Tower of Hanoi 01.png]]
'''Test case'''
[[File:Fōrmulæ - Tower of Hanoi 02.png]]
[[File:Fōrmulæ - Tower of Hanoi 03.png]]
=={{header|Gambas}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="vbnet">Public Sub Main()
Print "Three disks\n"
move_(3, 1, 2, 3)
Print
Print "Four disks\n"
move_(4, 1, 2, 3)
End
Public Sub move_(n As Integer, from As Integer, to As Integer, via As Integer)
If n > 0 Then
move_(n - 1, from, via, to)
Print "Move disk "; n; " from pole "; from; " to pole "; to
move_(n - 1, via, to, from)
End If
End Sub </syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
=={{header|GAP}}==
Line 3,332 ⟶ 3,446:
H(n, 1, 2, 3)
)</syntaxhighlight>
=={{header|J}}==
Line 4,020 ⟶ 4,123:
{{out}}
same as in FreeBasic
=={{header|MACRO-11}}==
<syntaxhighlight lang="macro11"> .TITLE HANOI
.MCALL .PRINT,.EXIT
HANOI:: MOV #4,R2
MOV #61,R3
MOV #62,R4
MOV #63,R5
JSR PC,MOVE
.EXIT
MOVE: DEC R2
BLT 1$
MOV R2,-(SP)
MOV R3,-(SP)
MOV R4,-(SP)
MOV R5,-(SP)
MOV R5,R0
MOV R4,R5
MOV R0,R4
JSR PC,MOVE
MOV (SP)+,R5
MOV (SP)+,R4
MOV (SP)+,R3
MOV (SP)+,R2
MOVB R3,3$
MOVB R4,4$
.PRINT #2$
MOV R3,R0
MOV R4,R3
MOV R5,R4
MOV R0,R5
BR MOVE
1$: RTS PC
2$: .ASCII /MOVE DISK FROM PEG /
3$: .ASCII /* TO PEG /
4$: .ASCIZ /*/
.EVEN
.END HANOI</syntaxhighlight>
{{out}}
<pre>MOVE DISK FROM PEG 1 TO PEG 3
MOVE DISK FROM PEG 1 TO PEG 2
MOVE DISK FROM PEG 2 TO PEG 3
MOVE DISK FROM PEG 1 TO PEG 3
MOVE DISK FROM PEG 3 TO PEG 1
MOVE DISK FROM PEG 3 TO PEG 2
MOVE DISK FROM PEG 2 TO PEG 1
MOVE DISK FROM PEG 1 TO PEG 2
MOVE DISK FROM PEG 2 TO PEG 3
MOVE DISK FROM PEG 2 TO PEG 1
MOVE DISK FROM PEG 1 TO PEG 3
MOVE DISK FROM PEG 2 TO PEG 3
MOVE DISK FROM PEG 3 TO PEG 2
MOVE DISK FROM PEG 3 TO PEG 1
MOVE DISK FROM PEG 1 TO PEG 2</pre>
=={{header|MAD}}==
Line 4,079 ⟶ 4,236:
MOVE DISK FROM POLE 1 TO POLE 3
MOVE DISK FROM POLE 2 TO POLE 3</pre>
=={{header|Maple}}==
Line 4,148 ⟶ 4,304:
Move disc 2 from pole 2 to pole 3
Move disc 1 from pole 1 to pole 3</pre>
=={{header|Miranda}}==
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [Stdout (lay (map showmove (move 4 1 2 3)))]
showmove :: (num,num)->[char]
showmove (src,dest)
= "Move disk from pole " ++ show src ++ " to pole " ++ show dest
move :: num->*->*->*->[(*,*)]
move n src via dest
= [], if n=0
= left ++ [(src,dest)] ++ right, otherwise
where left = move (n-1) src dest via
right = move (n-1) via src dest</syntaxhighlight>
{{out}}
<pre>Move disk from pole 1 to pole 2
Move disk from pole 1 to pole 3
Move disk from pole 2 to pole 3
Move disk from pole 1 to pole 2
Move disk from pole 3 to pole 1
Move disk from pole 3 to pole 2
Move disk from pole 1 to pole 2
Move disk from pole 1 to pole 3
Move disk from pole 2 to pole 3
Move disk from pole 2 to pole 1
Move disk from pole 3 to pole 1
Move disk from pole 2 to pole 3
Move disk from pole 1 to pole 2
Move disk from pole 1 to pole 3
Move disk from pole 2 to pole 3</pre>
=={{header|MIPS Assembly}}==
Line 5,896 ⟶ 6,083:
left -> middle
right -> middle</pre>
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
= <Move 4 1 2 3>;
};
Move {
0 e.X = ;
s.N s.Src s.Via s.Dest, <- s.N 1>: s.Next =
<Move s.Next s.Src s.Dest s.Via>
<Prout "Move disk from pole" s.Src "to pole" s.Dest>
<Move s.Next s.Via s.Src s.Dest>;
};</syntaxhighlight>
{{out}}
<pre>Move disk from pole 1 to pole 2
Move disk from pole 1 to pole 3
Move disk from pole 2 to pole 3
Move disk from pole 1 to pole 2
Move disk from pole 3 to pole 1
Move disk from pole 3 to pole 2
Move disk from pole 1 to pole 2
Move disk from pole 1 to pole 3
Move disk from pole 2 to pole 3
Move disk from pole 2 to pole 1
Move disk from pole 3 to pole 1
Move disk from pole 2 to pole 3
Move disk from pole 1 to pole 2
Move disk from pole 1 to pole 3
Move disk from pole 2 to pole 3</pre>
=={{header|Retro}}==
Line 6,098 ⟶ 6,314:
move(n - 1, via, dst, src) ok
</syntaxhighlight>
=={{header|RPL}}==
{{trans|Python}}
{{works with|Halcyon Calc|4.2.7}}
≪ → ndisks start end
≪ '''IF''' ndisks '''THEN'''
ndisks 1 - start 6 start - end - '''HANOI'''
start →STR " → " + end →STR +
ndisks 1 - 6 start - end - end '''HANOI'''
'''END'''
≫ ≫ ''''HANOI'''' STO
3 1 3 '''HANOI'''
{{out}}
<pre>
7: "1 → 3"
6: "1 → 2"
5: "3 → 2"
4: "1 → 3"
3: "2 → 1"
2: "2 → 3"
1: "1 → 3"
</pre>
=={{header|Ruby}}==
Line 6,369 ⟶ 6,608:
end if;
end func;</syntaxhighlight>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program hanoi;
loop for [src, dest] in move(4, 1, 2, 3) do
print("Move disk from pole " + src + " to pole " + dest);
end loop;
proc move(n, src, via, dest);
if n=0 then return []; end if;
return move(n-1, src, dest, via)
+ [[src, dest]]
+ move(n-1, via, src, dest);
end proc;
end program;</syntaxhighlight>
{{out}}
<pre>Move disk from pole 1 to pole 2
Move disk from pole 1 to pole 3
Move disk from pole 2 to pole 3
Move disk from pole 1 to pole 2
Move disk from pole 3 to pole 1
Move disk from pole 3 to pole 2
Move disk from pole 1 to pole 2
Move disk from pole 1 to pole 3
Move disk from pole 2 to pole 3
Move disk from pole 2 to pole 1
Move disk from pole 3 to pole 1
Move disk from pole 2 to pole 3
Move disk from pole 1 to pole 2
Move disk from pole 1 to pole 3
Move disk from pole 2 to pole 3</pre>
=={{header|Sidef}}==
Line 6,766 ⟶ 7,035:
EndIf
Return</syntaxhighlight>
=={{header|Uiua}}==
{{works with|Uiua|0.10.0}}
<syntaxhighlight lang="bash">
F ← |1.0 (
⟨
&p ⊏[1 2] &pf "Move disc [from to]: "
| F⍜(⊡0|-1)⍜(⊏[2 3]|⇌).
F⍜(⊡0|1◌).
F⍜(⊡0|-1)⍜(⊏[1 3]|⇌)
⟩≠1⊢.
)
F [4 1 2 3]
</syntaxhighlight>
{{out}}
<pre>
Move disc [from to]: [1 3]
Move disc [from to]: [1 2]
Move disc [from to]: [3 2]
Move disc [from to]: [1 3]
Move disc [from to]: [2 1]
Move disc [from to]: [2 3]
Move disc [from to]: [1 3]
Move disc [from to]: [1 2]
Move disc [from to]: [3 2]
Move disc [from to]: [3 1]
Move disc [from to]: [2 1]
Move disc [from to]: [3 2]
Move disc [from to]: [1 3]
Move disc [from to]: [1 2]
Move disc [from to]: [3 2]
</pre>
=={{header|UNIX Shell}}==
Line 6,840 ⟶ 7,141:
start -> end
middle -> end</pre>
=={{header|Uxntal}}==
<syntaxhighlight lang="Uxntal">|10 @Console &vector $2 &read $1 &pad $4 &type $1 &write $1 &error $1
|0100 ( -> )
#0102 [ LIT2 03 &count 04 ] hanoi
POP2 POP2 BRK
@hanoi ( from spare to count -: from spare to count )
( moving 0 disks is no-op )
DUP ?{ JMP2r }
( move disks 1..count-1 to the spare peg )
#01 SUB ROT SWP hanoi
( from to spare count-1 )
( print the current move )
;dict/move print-str
INCk #30 ORA .Console/write DEO
STH2
;dict/from print-str
OVR #30 ORA .Console/write DEO
;dict/to print-str
DUP #30 ORA .Console/write DEO
[ LIT2 0a -Console/write ] DEO
STH2r
( move disks 1..count-1 from the spare peg to the goal peg )
STH ROT ROT STHr hanoi
( restore original parameters for convenient recursion )
STH2 SWP STH2r INC
JMP2r
@print-str
&loop
LDAk .Console/write DEO
INC2 LDAk ?&loop
POP2 JMP2r
@dict
&move "Move 20 "disk 2000
&from 20 "from 20 "pole 2000
&to 20 "to 20 "pole 2000</syntaxhighlight>
=={{header|VBScript}}==
Line 6,945 ⟶ 7,291:
End Sub
End Module</syntaxhighlight>
=={{header|V (Vlang)}}==
<syntaxhighlight lang="Zig">
fn main() {
hanoi(4, "A", "B", "C")
}
fn hanoi(n u64, a string, b string, c string) {
if n > 0 {
hanoi(n - 1, a, c, b)
println("Move disk from ${a} to ${c}")
hanoi(n - 1, b, a, c)
}
}
</syntaxhighlight>
{{out}}
<pre>
Move disk from A to B
Move disk from A to C
Move disk from B to C
Move disk from A to B
Move disk from C to A
Move disk from C to B
Move disk from A to B
Move disk from A to C
Move disk from B to C
Move disk from B to A
Move disk from C to A
Move disk from B to C
Move disk from A to B
Move disk from A to C
Move disk from B to C
</pre>
=={{header|VTL-2}}==
Line 7,020 ⟶ 7,400:
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="
construct new(disks) {
_moves = 0
Line 7,273 ⟶ 7,653:
hanoi2(22, 1, 3, 2)
print peek("millisrunning") - t2, " ms"</syntaxhighlight>
=={{header|Z80 Assembly}}==
{{works with|CP/M 3.1|YAZE-AG-2.51.2 Z80 emulator}}
{{works with|ZSM4 macro assembler|YAZE-AG-2.51.2 Z80 emulator}}
Use the /S8 switch on the ZSM4 assembler for 8 significant characters for labels and names<br><br>
<syntaxhighlight lang="z80">
;
; Towers of Hanoi using Z80 assembly language
;
; Runs under CP/M 3.1 on YAZE-AG-2.51.2 Z80 emulator
; Assembled with zsm4 on same emulator/OS, uses macro capabilities of said assembler
; Created with vim under Windows
;
; 2023-05-29 Xorph
;
;
; Useful definitions
;
bdos equ 05h ; Call to CP/M BDOS function
strdel equ 6eh ; Set string delimiter
wrtstr equ 09h ; Write string to console
nul equ 00h ; ASCII control characters
cr equ 0dh
lf equ 0ah
cnull equ '0' ; ASCII character constants
ca equ 'A'
cb equ 'B'
cc equ 'C'
disks equ 4 ; Number of disks to move
;
; Macros for BDOS calls
;
setdel macro char ; Set string delimiter to char
ld c,strdel
ld e,char
call bdos
endm
print macro msg ; Output string to console
ld c,wrtstr
ld de,msg
call bdos
endm
pushall macro ; Save required registers to stack
push af
push bc
push de
endm
popall macro ; Recall required registers from stack
pop de
pop bc
pop af
endm
;
; =====================
; Start of main program
; =====================
;
cseg
setdel nul ; Set string delimiter to 00h
ld a,disks ; Initialization:
ld b,ca ; Tower A is source
ld c,cb ; Tower B is target
ld d,cc ; Tower C is intermediate
hanoi:
;
; Parameters in registers:
; Move a disks from b (source) to c (target) via d (intermediate)
;
or a ; If 0 disks to move, return
ret z
dec a ; Move all but lowest disk from source to intermediate via target
pushall ; Save registers
ld e,c ; Exchange c and d (target and intermediate)
ld c,d
ld d,e
call hanoi ; First recursion
popall ; Restore registers
ld hl,source ; Print move of lowest disk from source to target, save registers during BDOS call
ld (hl),b ; Source is still in b
ld hl,target
ld (hl),c ; Target is back in c due to popall
pushall
print movement
popall
ld e,b ; Now move stack from intermediate to target via source
ld b,d ; Source is still in b, target in c and intermediate in d
ld d,e
jr hanoi ; Optimize tail recursion
;
; ================
; Data definitions
; ================
;
dseg
movement:
defb 'Move disk from tower '
source:
defs 1
defb ' to tower '
target:
defs 1
crlf:
defb cr,lf,nul
</syntaxhighlight>
{{out}}
<pre>
E>hanoi
Move disk from tower A to tower C
Move disk from tower A to tower B
Move disk from tower C to tower B
Move disk from tower A to tower C
Move disk from tower B to tower A
Move disk from tower B to tower C
Move disk from tower A to tower C
Move disk from tower A to tower B
Move disk from tower C to tower B
Move disk from tower C to tower A
Move disk from tower B to tower A
Move disk from tower C to tower B
Move disk from tower A to tower C
Move disk from tower A to tower B
Move disk from tower C to tower B
E>
</pre>
=={{header|Zig}}==
|