Project P042
Tower of Hanoi
Move a tower of 1 to 8 disks from peg A to peg C, one disk at a time, never a larger disk on a smaller one. Every move is checked; a hint names the best next move, and the program can finish from any position in the fewest moves left - 2^n - 1 from the start.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-10
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
Move a tower of 1 to 8 disks from peg A to peg C, one disk at a time, never a larger disk on a smaller one. Every move is checked and the pegs are drawn after it. A hint names the best next move, and the program can finish from wherever you are, always in the fewest moves left - 2^n - 1 from the start.
main.eml- the menu, moves and their checks, hints, finishing, and the game statehanoi.eml- the pegs, the rule, the fewest moves from any position, and the picture
How each part works:
- The corpus case
tower-of-hanoisolves the tower from the start by recursion: move n - 1 disks out of the way, move the largest, move the n - 1 back on top. Here the same recursion starts from any legal position: to put disks 1 to k on a peg, if disk k is there already only the smaller ones need moving; otherwise the smaller ones go to the third peg, disk k moves, and the smaller ones come back on top of it. That this is the fewest was checked against a breadth-first search over every position of up to 7 disks (3,279 positions in all). - A hint is the first move of that sequence, with how many follow.
- Only the top disk of a peg moves; a disk may go on an empty peg or on a larger disk.
What is checked: a move as two pegs, from and to (AC, a c, A-C or A->C), different, from a peg with a disk, not onto a smaller disk; 1 to 8 disks. An empty answer cancels.
Sessions: sessions/basic.in plays three disks, follows two hints and lets the program finish - 7 moves, the fewest possible; then four disks, where the first move goes to the wrong peg and the program finishes in 15 more, 16 in all. sessions/bad-input.in gives menu choices 0 and x, moves AA, BC from the empty peg B, AX, A and ABC, a larger disk onto a smaller one, disk counts 0, 9 and x, and a one-disk tower solved in one move, after which moving, hints and finishing say it is done.
Built on the verified corpus case tower-of-hanoi (the recursive solution: two recursive calls, each returning its own list of moves).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== Tower of Hanoi ==
Move the tower from A to C, one disk at a time, never a larger disk on a smaller one.
[=] | |
[===] | |
[=====] | |
---------------------------
A B C
0 moves made.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 0
Pick a number from 1 to 6.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> x
Pick a number from 1 to 6.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 1
move (from and to, like AC)> AA
A disk has to move to another peg.
move (from and to, like AC)> BC
Peg B is empty.
move (from and to, like AC)> AX
Type two pegs, from and to, like AC or B C.
move (from and to, like AC)> A
Type two pegs, from and to, like AC or B C.
move (from and to, like AC)> ABC
Type two pegs, from and to, like AC or B C.
move (from and to, like AC)>
Cancelled.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 1
move (from and to, like AC)> AC
| | |
[===] | |
[=====] | [=]
---------------------------
A B C
1 move made.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 1
move (from and to, like AC)> AC
Disk 2 cannot go on disk 1.
move (from and to, like AC)> AB
| | |
| | |
[=====] [===] [=]
---------------------------
A B C
2 moves made.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 4
disks (1 to 8)> 0
Type a number from 1 to 8.
disks (1 to 8)> 9
Type a number from 1 to 8.
disks (1 to 8)> x
Type a number from 1 to 8.
disks (1 to 8)>
Cancelled.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 4
disks (1 to 8)> 1
A tower of 1 on A; the fewest moves to C are 1.
[=] | |
---------------
A B C
0 moves made.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 2
Hint: A->C - then 0 more, at the fewest.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 1
move (from and to, like AC)> AC
| | [=]
---------------
A B C
1 move made.
Solved in 1 move - the fewest possible, 2^1 - 1.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 1
The tower is already on C - start a new game to play again.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 2
The tower is already on C.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 3
The tower is already on C.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 5
| | [=]
---------------
A B C
1 move made.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 6
Bye.
What was typed (29 lines)
0
x
1
AA
BC
AX
A
ABC
1
AC
1
AC
AB
4
0
9
x
4
1
2
1
AC
1
2
3
5
6
basic
interpreter: byte-equal== Tower of Hanoi ==
Move the tower from A to C, one disk at a time, never a larger disk on a smaller one.
[=] | |
[===] | |
[=====] | |
---------------------------
A B C
0 moves made.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 1
move (from and to, like AC)> AC
| | |
[===] | |
[=====] | [=]
---------------------------
A B C
1 move made.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 1
move (from and to, like AC)> AB
| | |
| | |
[=====] [===] [=]
---------------------------
A B C
2 moves made.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 2
Hint: C->B - then 4 more, at the fewest.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 1
move (from and to, like AC)> c b
| | |
| [=] |
[=====] [===] |
---------------------------
A B C
3 moves made.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 1
move (from and to, like AC)> A-C
| | |
| [=] |
| [===] [=====]
---------------------------
A B C
4 moves made.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 2
Hint: B->A - then 2 more, at the fewest.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 3
The fewest moves from here: 3.
B->A B->C A->C
| | [=]
| | [===]
| | [=====]
---------------------------
A B C
7 moves made.
Solved in 7 moves - the fewest possible, 2^3 - 1.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 4
disks (1 to 8)> 4
A tower of 4 on A; the fewest moves to C are 15.
[=] | |
[===] | |
[=====] | |
[=======] | |
---------------------------------
A B C
0 moves made.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 1
move (from and to, like AC)> AC
| | |
[===] | |
[=====] | |
[=======] | [=]
---------------------------------
A B C
1 move made.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 2
Hint: C->B - then 14 more, at the fewest.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 3
The fewest moves from here: 15.
C->B A->C B->C A->B C->A C->B A->B A->C B->C B->A
C->A B->C A->B A->C B->C
| | [=]
| | [===]
| | [=====]
| | [=======]
---------------------------------
A B C
16 moves made.
Solved in 16 moves; the fewest possible is 15, 2^4 - 1.
1) move 2) hint 3) finish for me 4) new game 5) show 6) quit
choice> 6
Bye.
What was typed (18 lines)
1
AC
1
AB
2
1
c b
1
A-C
2
3
4
4
1
AC
2
3
6
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
eml# P042 Tower of Hanoi: move the whole tower from peg A to peg C, one disk at
# a time, never a larger disk on a smaller one. Ask for a hint, or let the
# program finish from wherever you are - always in the fewest moves left.
import hanoi
8 => most_disks
def trim(s):
0 => i
len(s) => j
while i < j and s[i] == " ":
i + 1 => i
while j > i and s[j - 1] == " ":
j - 1 => j
return s[i:j]
def peg_of(c):
"ABCabc" => all
for i in [0:5]:
if all[i] == c:
return i % 3
return -1
def moves_text(n):
if n == 1:
return "1 move"
return str(n) + " moves"
def fewest(n):
# 2^n - 1, the fewest moves for a whole tower of n disks.
1 => p
for k in [1:n]:
p * 2 => p
return p - 1
def show(state):
for line in hanoi.picture(state[0], state[1]):
line ^0
(moves_text(state[2]) + " made.") ^0
def solved(state):
return len(state[0][2]) == state[1]
def move_text(m):
return hanoi.letters[m[0]] + "->" + hanoi.letters[m[1]]
def ask_move(state):
if solved(state):
"The tower is already on C - start a new game to play again." ^0
return state
while True:
trim(input("move (from and to, like AC)> ")) => answer
if answer == "":
"Cancelled." ^0
return state
"" => letters
for c in answer:
if c != " " and c != "-" and c != ">":
letters + c => letters
if len(letters) != 2 or peg_of(letters[0]) == -1 or peg_of(letters[1]) == -1:
"Type two pegs, from and to, like AC or B C." ^0
else:
peg_of(letters[0]) => f
peg_of(letters[1]) => t
hanoi.why_not(state[0], f, t) => why
if why != "":
why ^0
else:
[hanoi.moved(state[0], f, t), state[1], state[2] + 1] => state
show(state)
if solved(state):
done(state)
return state
def done(state):
fewest(state[1]) => best
if state[2] == best:
("Solved in " + moves_text(state[2]) + " - the fewest possible, 2^" + str(state[1]) + " - 1.") ^0
else:
("Solved in " + moves_text(state[2]) + "; the fewest possible is " + str(best) + ", 2^" + str(state[1]) + " - 1.") ^0
def finish(state):
if solved(state):
"The tower is already on C." ^0
return state
hanoi.solution(state[0], state[1]) => moves
("The fewest moves from here: " + str(len(moves)) + ".") ^0
"" => line
0 => count
for m in moves:
if line != "":
line + " " => line
line + move_text(m) => line
count + 1 => count
if count % 10 == 0:
(" " + line) ^0
"" => line
if line != "":
(" " + line) ^0
state[0] => pegs
for m in moves:
hanoi.moved(pegs, m[0], m[1]) => pegs
[pegs, state[1], state[2] + len(moves)] => state
show(state)
done(state)
return state
def new_game(state):
while True:
trim(input("disks (1 to " + str(most_disks) + ")> ")) => answer
if answer == "":
"Cancelled." ^0
return state
-1 => n
if len(answer) == 1 and answer[0] in "0123456789":
int(answer) => n
if n >= 1 and n <= most_disks:
[hanoi.start(n), n, 0] => state
("A tower of " + str(n) + " on A; the fewest moves to C are " + str(fewest(n)) + ".") ^0
show(state)
return state
("Type a number from 1 to " + str(most_disks) + ".") ^0
"== Tower of Hanoi ==" ^0
"Move the tower from A to C, one disk at a time, never a larger disk on a smaller one." ^0
[hanoi.start(3), 3, 0] => state
show(state)
True => running
while running:
"" ^0
"1) move 2) hint 3) finish for me 4) new game 5) show 6) quit" ^0
trim(input("choice> ")) => choice
if choice == "1":
ask_move(state) => state
elif choice == "2":
if solved(state):
"The tower is already on C." ^0
else:
hanoi.solution(state[0], state[1]) => moves
("Hint: " + move_text(moves[0]) + " - then " + str(len(moves) - 1) + " more, at the fewest.") ^0
elif choice == "3":
finish(state) => state
elif choice == "4":
new_game(state) => state
elif choice == "5":
show(state)
elif choice == "6":
False => running
else:
"Pick a number from 1 to 6." ^0
"Bye." ^0
Python projection (main.py)
import hanoi
most_disks = 8
def trim(s):
i = 0
j = len(s)
while i < j and s[i] == " ":
i = i + 1
while j > i and s[j - 1] == " ":
j = j - 1
return s[i:j]
def peg_of(c):
all = "ABCabc"
for i in range(0, 6):
if all[i] == c:
return i % 3
return -1
def moves_text(n):
if n == 1:
return "1 move"
return str(n) + " moves"
def fewest(n):
p = 1
for k in range(1, n+1):
p = p * 2
return p - 1
def show(state):
for line in hanoi.picture(state[0], state[1]):
print(line)
print(moves_text(state[2]) + " made.")
def solved(state):
return len(state[0][2]) == state[1]
def move_text(m):
return hanoi.letters[m[0]] + "->" + hanoi.letters[m[1]]
def ask_move(state):
if solved(state):
print("The tower is already on C - start a new game to play again.")
return state
while True:
answer = trim(input("move (from and to, like AC)> "))
if answer == "":
print("Cancelled.")
return state
letters = ""
for c in answer:
if c != " " and c != "-" and c != ">":
letters = letters + c
if len(letters) != 2 or peg_of(letters[0]) == -1 or peg_of(letters[1]) == -1:
print("Type two pegs, from and to, like AC or B C.")
else:
f = peg_of(letters[0])
t = peg_of(letters[1])
why = hanoi.why_not(state[0], f, t)
if why != "":
print(why)
else:
state = [hanoi.moved(state[0], f, t), state[1], state[2] + 1]
show(state)
if solved(state):
done(state)
return state
def done(state):
best = fewest(state[1])
if state[2] == best:
print("Solved in " + moves_text(state[2]) + " - the fewest possible, 2^" + str(state[1]) + " - 1.")
else:
print("Solved in " + moves_text(state[2]) + "; the fewest possible is " + str(best) + ", 2^" + str(state[1]) + " - 1.")
def finish(state):
if solved(state):
print("The tower is already on C.")
return state
moves = hanoi.solution(state[0], state[1])
print("The fewest moves from here: " + str(len(moves)) + ".")
line = ""
count = 0
for m in moves:
if line != "":
line = line + " "
line = line + move_text(m)
count = count + 1
if count % 10 == 0:
print(" " + line)
line = ""
if line != "":
print(" " + line)
pegs = state[0]
for m in moves:
pegs = hanoi.moved(pegs, m[0], m[1])
state = [pegs, state[1], state[2] + len(moves)]
show(state)
done(state)
return state
def new_game(state):
while True:
answer = trim(input("disks (1 to " + str(most_disks) + ")> "))
if answer == "":
print("Cancelled.")
return state
n = -1
if len(answer) == 1 and answer[0] in "0123456789":
n = int(answer)
if n >= 1 and n <= most_disks:
state = [hanoi.start(n), n, 0]
print("A tower of " + str(n) + " on A; the fewest moves to C are " + str(fewest(n)) + ".")
show(state)
return state
print("Type a number from 1 to " + str(most_disks) + ".")
print("== Tower of Hanoi ==")
print("Move the tower from A to C, one disk at a time, never a larger disk on a smaller one.")
state = [hanoi.start(3), 3, 0]
show(state)
running = True
while running:
print("")
print("1) move 2) hint 3) finish for me 4) new game 5) show 6) quit")
choice = trim(input("choice> "))
if choice == "1":
state = ask_move(state)
elif choice == "2":
if solved(state):
print("The tower is already on C.")
else:
moves = hanoi.solution(state[0], state[1])
print("Hint: " + move_text(moves[0]) + " - then " + str(len(moves) - 1) + " more, at the fewest.")
elif choice == "3":
state = finish(state)
elif choice == "4":
state = new_game(state)
elif choice == "5":
show(state)
elif choice == "6":
running = False
else:
print("Pick a number from 1 to 6.")
print("Bye.")
hanoi.eml
eml# P042 Tower of Hanoi - the pegs, the rule and the fewest moves. Pegs are
# 0, 1, 2 (shown as A, B, C); each is a list of disk sizes from the bottom
# up, so its last disk is the top one.
"ABC" => letters
def start(n):
[] => a
for k in [0:n - 1]:
a + [n - k] => a
return [a, [], []]
def why_not(pegs, f, t):
# "" if the top disk of peg f may move to peg t, otherwise the reason.
if f == t:
return "A disk has to move to another peg."
if len(pegs[f]) == 0:
return "Peg " + letters[f] + " is empty."
pegs[f][len(pegs[f]) - 1] => disk
if len(pegs[t]) > 0 and pegs[t][len(pegs[t]) - 1] < disk:
return "Disk " + str(disk) + " cannot go on disk " + str(pegs[t][len(pegs[t]) - 1]) + "."
return ""
def moved(pegs, f, t):
# The pegs after moving the top disk of f to t (the move is legal).
pegs[f][len(pegs[f]) - 1] => disk
[] => out
for p in [0:2]:
if p == f:
out + [pegs[p][0:len(pegs[p]) - 1]] => out
elif p == t:
out + [pegs[p] + [disk]] => out
else:
out + [pegs[p]] => out
return out
def where(pegs, n):
# where[k] is the peg disk k is on (index 0 unused).
[0] * (n + 1) => at
for p in [0:2]:
for disk in pegs[p]:
p => at[disk]
return at
def gather(at, k, target):
# The fewest moves that put disks 1 to k on the target peg, from any
# legal position: if disk k is there already, only the smaller ones need
# moving; otherwise the smaller ones go to the third peg, disk k moves,
# and the smaller ones come back on top of it. at is changed to match.
if k == 0:
return []
if at[k] == target:
return gather(at, k - 1, target)
3 - at[k] - target => other
gather(at, k - 1, other) => before
[[at[k], target]] => middle
target => at[k]
gather(at, k - 1, target) => after
return before + middle + after
def solution(pegs, n):
# The fewest moves from here to every disk on peg C.
return gather(where(pegs, n), n, 2)
def picture(pegs, n):
2 * n + 1 => width
[] => lines
n - 1 => level
while level >= 0:
"" => line
for p in [0:2]:
"|" => s
if level < len(pegs[p]):
pegs[p][level] => disk
"[" + "=" * (2 * disk - 1) + "]" => s
" " * int((width - len(s)) / 2) => side
line + " " + side + s + side + " " => line
len(line) => j
while j > 0 and line[j - 1] == " ":
j - 1 => j
lines + [line[0:j]] => lines
level - 1 => level
"" => base
"" => names
for p in [0:2]:
base + "-" + "-" * width + "-" => base
names + " " + " " * n + letters[p] + " " * n + " " => names
lines + [base] => lines
len(names) => j
while j > 0 and names[j - 1] == " ":
j - 1 => j
lines + [names[0:j]] => lines
return lines
Python projection (hanoi.py)
letters = "ABC"
def start(n):
a = []
for k in range(0, n):
a = a + [n - k]
return [a, [], []]
def why_not(pegs, f, t):
if f == t:
return "A disk has to move to another peg."
if len(pegs[f]) == 0:
return "Peg " + letters[f] + " is empty."
disk = pegs[f][len(pegs[f]) - 1]
if len(pegs[t]) > 0 and pegs[t][len(pegs[t]) - 1] < disk:
return "Disk " + str(disk) + " cannot go on disk " + str(pegs[t][len(pegs[t]) - 1]) + "."
return ""
def moved(pegs, f, t):
disk = pegs[f][len(pegs[f]) - 1]
out = []
for p in range(0, 3):
if p == f:
out = out + [pegs[p][0:len(pegs[p]) - 1]]
elif p == t:
out = out + [pegs[p] + [disk]]
else:
out = out + [pegs[p]]
return out
def where(pegs, n):
at = [0] * (n + 1)
for p in range(0, 3):
for disk in pegs[p]:
at[disk] = p
return at
def gather(at, k, target):
if k == 0:
return []
if at[k] == target:
return gather(at, k - 1, target)
other = 3 - at[k] - target
before = gather(at, k - 1, other)
middle = [[at[k], target]]
at[k] = target
after = gather(at, k - 1, target)
return before + middle + after
def solution(pegs, n):
return gather(where(pegs, n), n, 2)
def picture(pegs, n):
width = 2 * n + 1
lines = []
level = n - 1
while level >= 0:
line = ""
for p in range(0, 3):
s = "|"
if level < len(pegs[p]):
disk = pegs[p][level]
s = "[" + "=" * (2 * disk - 1) + "]"
side = " " * int((width - len(s)) / 2)
line = line + " " + side + s + side + " "
j = len(line)
while j > 0 and line[j - 1] == " ":
j = j - 1
lines = lines + [line[0:j]]
level = level - 1
base = ""
names = ""
for p in range(0, 3):
base = base + "-" + "-" * width + "-"
names = names + " " + " " * n + letters[p] + " " * n + " "
lines = lines + [base]
j = len(names)
while j > 0 and names[j - 1] == " ":
j = j - 1
lines = lines + [names[0:j]]
return lines