Project P093
Route planner
A map of towns and two-way roads in whole kilometres: the shortest route by Dijkstra's method with a binary heap, every town's distance in the order the towns were settled, a route through a chosen town against the shortest, and roads closed, opened or changed.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-15
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
A map of towns and two-way roads in whole kilometres. The program finds the shortest route between two towns by Dijkstra's method, lists every town's distance in the order the towns were settled, compares a route through a chosen town with the shortest, and lets roads be closed, opened or changed. It starts with eight towns: six on the textbook example map, and two more off on their own.
main.eml- the menu, the map, the routes and the road changesroutes.eml- the roads, the binary heap, Dijkstra's method and the route read back
How each part works:
- Dijkstra's method: start with the first town at distance 0. Always settle the nearest town not yet settled - with no negative roads, no later route can bring it nearer - then see whether going through it shortens the way to each neighbour. The waiting towns sit in a binary heap, as in the corpus case
binary-heap, nearest on top. A town can be in the heap more than once; old entries are skipped once it is settled. - The route is read back from each town's previous town. As in the corpus case
route-path-builder, each stop is added by making a new list, so no list already handed out changes. - A route through a town is the shortest route to it followed by the shortest route on from it.
- On the starting map, Avon to Eton is 20 km by Cove and Ford - the answer the textbook example gives.
What is checked: menu choices 1 to 7; towns that are on the map; a road between two different towns, of 1 to 999 km; closing only a road that exists. An empty answer cancels.
Sessions: sessions/basic.in gives: - the map; Avon to Eton (20 km); every distance from Avon, with Glen and Hale out of reach; - Avon to Eton through Dale (26 km against 20); Bree to Ford (12 km); - Cove - Ford closed, which makes Avon to Eton 23 km by Ford; - a road Eton - Glen of 4 km, after which Avon reaches Hale in 32 km, and every distance from Hale.
sessions/bad-input.in gives: - menu choices 0 and x; - a town that does not exist; closing a road that does not exist; a road from Avon to Avon; 0, 1000 and x km; - Avon through Glen to Bree, which cannot be done.
Built on the verified corpus cases binary-heap (the nearest town always on top) and route-path-builder (a route extended by making a new one).
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== Route planner ==
Towns and roads: the shortest route by Dijkstra's method.
1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit
choice> 0
Pick a number from 1 to 7.
1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit
choice> x
Pick a number from 1 to 7.
1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit
choice> 2
from> Zed
No town called Zed is on the map.
from>
Cancelled.
1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit
choice> 5
one end> Avon
other end> Eton
There is no road between Avon and Eton.
1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit
choice> 6
one end> Avon
other end> Avon
A road needs two different towns.
1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit
choice> 6
one end> Avon
other end> Bree
kilometres (1 to 999)> 0
Type a whole number from 1 to 999.
kilometres (1 to 999)> 1000
Type a whole number from 1 to 999.
kilometres (1 to 999)> x
Type a whole number from 1 to 999.
kilometres (1 to 999)>
Cancelled.
1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit
choice> 4
from> Avon
through> Glen
to> Bree
There is no way from Avon through Glen to Bree.
1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit
choice> 7
Bye.
What was typed (23 lines)
0
x
2
Zed
5
Avon
Eton
6
Avon
Avon
6
Avon
Bree
0
1000
x
4
Avon
Glen
Bree
7
basic
interpreter: byte-equal== Route planner ==
Towns and roads: the shortest route by Dijkstra's method.
1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit
choice> 1
Avon Bree 7, Cove 9, Ford 14
Bree Avon 7, Cove 10, Dale 15
Cove Avon 9, Bree 10, Dale 11, Ford 2
Dale Bree 15, Cove 11, Eton 6
Eton Dale 6, Ford 9
Ford Avon 14, Cove 2, Eton 9
Glen Hale 5
Hale Glen 5
(kilometres; every road goes both ways)
1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit
choice> 2
from> Avon
to> Eton
Avon - Cove - Ford - Eton
20 km - no route is shorter.
1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit
choice> 3
from> Avon
town km by way of
Avon 0 -
Bree 7 Avon
Cove 9 Avon
Ford 11 Cove
Dale 20 Cove
Eton 20 Ford
cannot be reached: Glen, Hale
Towns are listed in the order they were settled: always the nearest one not yet settled, whose distance can then no longer shrink.
1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit
choice> 4
from> Avon
through> Dale
to> Eton
Avon - Cove - Dale - Eton
26 km through Dale, against 20 km by the shortest route.
1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit
choice> 2
from> Bree
to> Ford
Bree - Cove - Ford
12 km - no route is shorter.
1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit
choice> 5
one end> Cove
other end> Ford
The road Cove - Ford is closed.
1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit
choice> 2
from> Avon
to> Eton
Avon - Ford - Eton
23 km - no route is shorter.
1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit
choice> 6
one end> Eton
other end> Glen
kilometres (1 to 999)> 4
The road Eton - Glen is now 4 km.
1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit
choice> 2
from> Avon
to> Hale
Avon - Ford - Eton - Glen - Hale
32 km - no route is shorter.
1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit
choice> 3
from> Hale
town km by way of
Hale 0 -
Glen 5 Hale
Eton 9 Glen
Dale 15 Eton
Ford 18 Eton
Cove 26 Dale
Bree 30 Dale
Avon 32 Ford
Towns are listed in the order they were settled: always the nearest one not yet settled, whose distance can then no longer shrink.
1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit
choice> 7
Bye.
What was typed (29 lines)
1
2
Avon
Eton
3
Avon
4
Avon
Dale
Eton
2
Bree
Ford
5
Cove
Ford
2
Avon
Eton
6
Eton
Glen
4
2
Avon
Hale
3
Hale
7
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# P093 route planner: a map of towns and roads, the shortest route between
# two towns by Dijkstra's method, every town's distance with the order they
# were settled in, a route through a chosen town, and roads closed or
# opened.
import routes
def plain(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 lpad(s, n):
while len(s) < n:
" " + s => s
return s
def pad(s, n):
while len(s) < n:
s + " " => s
return s
def ask_town(m, prompt):
while True:
plain(input(prompt)) => s
if s == "":
return -1
routes.index_of(m[0], s) => i
if i >= 0:
return i
("No town called " + s + " is on the map.") ^0
def chain(m, path):
"" => s
for i in path:
if s != "":
s + " - " => s
s + m[0][i] => s
return s
def show(m):
for i in [0:len(m[0]) - 1]:
"" => s
for r in m[1][i]:
if s != "":
s + ", " => s
s + m[0][r[0]] + " " + str(r[1]) => s
if s == "":
"no roads" => s
(" " + pad(m[0][i], 6) + s) ^0
"(kilometres; every road goes both ways)" ^0
def shortest(m):
ask_town(m, "from> ") => a
if a == -1:
"Cancelled." ^0
return
ask_town(m, "to> ") => b
if b == -1:
"Cancelled." ^0
return
routes.route(m, a, b) => r
if r[0] == -1:
("No road links " + m[0][a] + " to " + m[0][b] + ".") ^0
return
(" " + chain(m, r[1])) ^0
(str(r[0]) + " km - no route is shorter.") ^0
def distances(m):
ask_town(m, "from> ") => a
if a == -1:
"Cancelled." ^0
return
routes.dijkstra(m, a) => r
" town km by way of" ^0
for i in r[2]:
"-" => via
if r[1][i] >= 0:
m[0][r[1][i]] => via
(" " + pad(m[0][i], 6) + lpad(str(r[0][i]), 3) + " " + via) ^0
[] => far
for i in [0:len(m[0]) - 1]:
if r[0][i] == -1:
far + [m[0][i]] => far
if len(far) > 0:
"" => s
for t in far:
if s != "":
s + ", " => s
s + t => s
(" cannot be reached: " + s) ^0
"Towns are listed in the order they were settled: always the nearest one not yet settled, whose distance can then no longer shrink." ^0
def via(m):
ask_town(m, "from> ") => a
if a == -1:
"Cancelled." ^0
return
ask_town(m, "through> ") => v
if v == -1:
"Cancelled." ^0
return
ask_town(m, "to> ") => b
if b == -1:
"Cancelled." ^0
return
routes.route(m, a, v) => r1
routes.route(m, v, b) => r2
if r1[0] == -1 or r2[0] == -1:
("There is no way from " + m[0][a] + " through " + m[0][v] + " to " + m[0][b] + ".") ^0
return
r1[1] + r2[1][1:len(r2[1])] => path
(" " + chain(m, path)) ^0
routes.route(m, a, b) => direct
(str(r1[0] + r2[0]) + " km through " + m[0][v] + ", against " + str(direct[0]) + " km by the shortest route.") ^0
def close(m):
ask_town(m, "one end> ") => a
if a == -1:
"Cancelled." ^0
return m
ask_town(m, "other end> ") => b
if b == -1:
"Cancelled." ^0
return m
if routes.road(m, a, b) == -1:
("There is no road between " + m[0][a] + " and " + m[0][b] + ".") ^0
return m
("The road " + m[0][a] + " - " + m[0][b] + " is closed.") ^0
return routes.set_road(m, a, b, 0)
def open_road(m):
ask_town(m, "one end> ") => a
if a == -1:
"Cancelled." ^0
return m
ask_town(m, "other end> ") => b
if b == -1:
"Cancelled." ^0
return m
if a == b:
"A road needs two different towns." ^0
return m
while True:
plain(input("kilometres (1 to 999)> ")) => s
if s == "":
"Cancelled." ^0
return m
0 => km
True => ok
if len(s) > 3:
False => ok
for c in s:
if c >= "0" and c <= "9":
km * 10 + int(c) => km
else:
False => ok
if ok and km >= 1:
("The road " + m[0][a] + " - " + m[0][b] + " is now " + str(km) + " km.") ^0
return routes.set_road(m, a, b, km)
"Type a whole number from 1 to 999." ^0
["Avon", "Bree", "Cove", "Dale", "Eton", "Ford", "Glen", "Hale"] => towns
[[], [], [], [], [], [], [], []] => roads
[towns, roads] => m
for r in [[0, 1, 7], [0, 2, 9], [0, 5, 14], [1, 2, 10], [1, 3, 15], [2, 3, 11], [2, 5, 2], [3, 4, 6], [4, 5, 9], [6, 7, 5]]:
routes.set_road(m, r[0], r[1], r[2]) => m
"== Route planner ==" ^0
"Towns and roads: the shortest route by Dijkstra's method." ^0
True => running
while running:
"" ^0
"1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit" ^0
plain(input("choice> ")) => choice
if choice == "1":
show(m)
elif choice == "2":
shortest(m)
elif choice == "3":
distances(m)
elif choice == "4":
via(m)
elif choice == "5":
close(m) => m
elif choice == "6":
open_road(m) => m
elif choice == "7":
False => running
else:
"Pick a number from 1 to 7." ^0
"Bye." ^0
Python projection (main.py)
import routes
def plain(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 lpad(s, n):
while len(s) < n:
s = " " + s
return s
def pad(s, n):
while len(s) < n:
s = s + " "
return s
def ask_town(m, prompt):
while True:
s = plain(input(prompt))
if s == "":
return -1
i = routes.index_of(m[0], s)
if i >= 0:
return i
print("No town called " + s + " is on the map.")
def chain(m, path):
s = ""
for i in path:
if s != "":
s = s + " - "
s = s + m[0][i]
return s
def show(m):
for i in range(0, len(m[0])):
s = ""
for r in m[1][i]:
if s != "":
s = s + ", "
s = s + m[0][r[0]] + " " + str(r[1])
if s == "":
s = "no roads"
print(" " + pad(m[0][i], 6) + s)
print("(kilometres; every road goes both ways)")
def shortest(m):
a = ask_town(m, "from> ")
if a == -1:
print("Cancelled.")
return
b = ask_town(m, "to> ")
if b == -1:
print("Cancelled.")
return
r = routes.route(m, a, b)
if r[0] == -1:
print("No road links " + m[0][a] + " to " + m[0][b] + ".")
return
print(" " + chain(m, r[1]))
print(str(r[0]) + " km - no route is shorter.")
def distances(m):
a = ask_town(m, "from> ")
if a == -1:
print("Cancelled.")
return
r = routes.dijkstra(m, a)
print(" town km by way of")
for i in r[2]:
via = "-"
if r[1][i] >= 0:
via = m[0][r[1][i]]
print(" " + pad(m[0][i], 6) + lpad(str(r[0][i]), 3) + " " + via)
far = []
for i in range(0, len(m[0])):
if r[0][i] == -1:
far = far + [m[0][i]]
if len(far) > 0:
s = ""
for t in far:
if s != "":
s = s + ", "
s = s + t
print(" cannot be reached: " + s)
print("Towns are listed in the order they were settled: always the nearest one not yet settled, whose distance can then no longer shrink.")
def via(m):
a = ask_town(m, "from> ")
if a == -1:
print("Cancelled.")
return
v = ask_town(m, "through> ")
if v == -1:
print("Cancelled.")
return
b = ask_town(m, "to> ")
if b == -1:
print("Cancelled.")
return
r1 = routes.route(m, a, v)
r2 = routes.route(m, v, b)
if r1[0] == -1 or r2[0] == -1:
print("There is no way from " + m[0][a] + " through " + m[0][v] + " to " + m[0][b] + ".")
return
path = r1[1] + r2[1][1:len(r2[1])]
print(" " + chain(m, path))
direct = routes.route(m, a, b)
print(str(r1[0] + r2[0]) + " km through " + m[0][v] + ", against " + str(direct[0]) + " km by the shortest route.")
def close(m):
a = ask_town(m, "one end> ")
if a == -1:
print("Cancelled.")
return m
b = ask_town(m, "other end> ")
if b == -1:
print("Cancelled.")
return m
if routes.road(m, a, b) == -1:
print("There is no road between " + m[0][a] + " and " + m[0][b] + ".")
return m
print("The road " + m[0][a] + " - " + m[0][b] + " is closed.")
return routes.set_road(m, a, b, 0)
def open_road(m):
a = ask_town(m, "one end> ")
if a == -1:
print("Cancelled.")
return m
b = ask_town(m, "other end> ")
if b == -1:
print("Cancelled.")
return m
if a == b:
print("A road needs two different towns.")
return m
while True:
s = plain(input("kilometres (1 to 999)> "))
if s == "":
print("Cancelled.")
return m
km = 0
ok = True
if len(s) > 3:
ok = False
for c in s:
if c >= "0" and c <= "9":
km = km * 10 + int(c)
else:
ok = False
if ok and km >= 1:
print("The road " + m[0][a] + " - " + m[0][b] + " is now " + str(km) + " km.")
return routes.set_road(m, a, b, km)
print("Type a whole number from 1 to 999.")
towns = ["Avon", "Bree", "Cove", "Dale", "Eton", "Ford", "Glen", "Hale"]
roads = [[], [], [], [], [], [], [], []]
m = [towns, roads]
for r in [[0, 1, 7], [0, 2, 9], [0, 5, 14], [1, 2, 10], [1, 3, 15], [2, 3, 11], [2, 5, 2], [3, 4, 6], [4, 5, 9], [6, 7, 5]]:
m = routes.set_road(m, r[0], r[1], r[2])
print("== Route planner ==")
print("Towns and roads: the shortest route by Dijkstra's method.")
running = True
while running:
print("")
print("1) map 2) shortest route 3) distances from a town 4) route through a town 5) close a road 6) open or change a road 7) quit")
choice = plain(input("choice> "))
if choice == "1":
show(m)
elif choice == "2":
shortest(m)
elif choice == "3":
distances(m)
elif choice == "4":
via(m)
elif choice == "5":
m = close(m)
elif choice == "6":
m = open_road(m)
elif choice == "7":
running = False
else:
print("Pick a number from 1 to 7.")
print("Bye.")
routes.eml
eml# P093 route planner - towns and the roads between them (both ways, whole
# kilometres), and the shortest route by Dijkstra's method with a binary
# heap. A map is [towns, roads], roads[i] the list of [town, km] from i.
def index_of(towns, name):
for i in [0:len(towns) - 1]:
if towns[i] == name:
return i
return -1
def road(m, a, b):
# The length of the road a-b, or -1 if there is none.
for r in m[1][a]:
if r[0] == b:
return r[1]
return -1
def set_road(m, a, b, km):
# Add, change (km > 0) or close (km = 0) the road a-b, both ways.
m[1] => roads
for e in [[a, b], [b, a]]:
[] => out
for r in roads[e[0]]:
if r[0] != e[1]:
out + [r] => out
if km > 0:
out + [[e[1], km]] => out
out => roads[e[0]]
return [m[0], roads]
def before(x, y):
# Heap order: shorter distance first, then the lower town number.
return x[0] < y[0] or (x[0] == y[0] and x[1] < y[1])
def push(heap, x):
# The corpus case binary-heap: add at the end and swap up.
heap + [x] => heap
len(heap) - 1 => i
while i > 0:
int((i - 1) / 2) => p
if before(heap[i], heap[p]):
heap[p] => t
heap[i] => heap[p]
t => heap[i]
p => i
else:
0 => i
return heap
def pop(heap):
heap[0] => top
heap[len(heap) - 1] => last
heap[0:len(heap) - 1] => heap
if len(heap) > 0:
last => heap[0]
0 => i
True => going
while going:
2 * i + 1 => l
i => s
if l < len(heap) and before(heap[l], heap[s]):
l => s
if l + 1 < len(heap) and before(heap[l + 1], heap[s]):
l + 1 => s
if s == i:
False => going
else:
heap[s] => t
heap[i] => heap[s]
t => heap[i]
s => i
return [top, heap]
def dijkstra(m, start):
# Shortest distances from start: always settle the nearest town not yet
# settled, then see whether going through it shortens the way to its
# neighbours. Old heap entries for a town already settled are skipped.
# Returns [dist (-1 unreachable), previous town, settling order].
len(m[0]) => n
[-1] * n => dist
[-1] * n => prev
[0] * n => done
[] => order
0 => dist[start]
push([], [0, start]) => heap
while len(heap) > 0:
pop(heap) => r
r[0] => top
r[1] => heap
top[1] => u
if done[u] == 0:
1 => done[u]
order + [u] => order
for e in m[1][u]:
e[0] => v
dist[u] + e[1] => d
if done[v] == 0 and (dist[v] == -1 or d < dist[v] or (d == dist[v] and u < prev[v])):
d => dist[v]
u => prev[v]
push(heap, [d, v]) => heap
return [dist, prev, order]
def route(m, a, b):
# [km, towns along the way] or [-1, []]. The path is built by adding a
# stop to a new list each time, as in the corpus case route-path-builder,
# so no list already handed out changes.
dijkstra(m, a) => r
if r[0][b] == -1:
return [-1, []]
[b] => path
b => x
while x != a:
r[1][x] => x
[x] + path => path
return [r[0][b], path]
Python projection (routes.py)
def index_of(towns, name):
for i in range(0, len(towns)):
if towns[i] == name:
return i
return -1
def road(m, a, b):
for r in m[1][a]:
if r[0] == b:
return r[1]
return -1
def set_road(m, a, b, km):
roads = m[1]
for e in [[a, b], [b, a]]:
out = []
for r in roads[e[0]]:
if r[0] != e[1]:
out = out + [r]
if km > 0:
out = out + [[e[1], km]]
roads[e[0]] = out
return [m[0], roads]
def before(x, y):
return x[0] < y[0] or x[0] == y[0] and x[1] < y[1]
def push(heap, x):
heap = heap + [x]
i = len(heap) - 1
while i > 0:
p = int((i - 1) / 2)
if before(heap[i], heap[p]):
t = heap[p]
heap[p] = heap[i]
heap[i] = t
i = p
else:
i = 0
return heap
def pop(heap):
top = heap[0]
last = heap[len(heap) - 1]
heap = heap[0:len(heap) - 1]
if len(heap) > 0:
heap[0] = last
i = 0
going = True
while going:
l = 2 * i + 1
s = i
if l < len(heap) and before(heap[l], heap[s]):
s = l
if l + 1 < len(heap) and before(heap[l + 1], heap[s]):
s = l + 1
if s == i:
going = False
else:
t = heap[s]
heap[s] = heap[i]
heap[i] = t
i = s
return [top, heap]
def dijkstra(m, start):
n = len(m[0])
dist = [-1] * n
prev = [-1] * n
done = [0] * n
order = []
dist[start] = 0
heap = push([], [0, start])
while len(heap) > 0:
r = pop(heap)
top = r[0]
heap = r[1]
u = top[1]
if done[u] == 0:
done[u] = 1
order = order + [u]
for e in m[1][u]:
v = e[0]
d = dist[u] + e[1]
if done[v] == 0 and (dist[v] == -1 or d < dist[v] or d == dist[v] and u < prev[v]):
dist[v] = d
prev[v] = u
heap = push(heap, [d, v])
return [dist, prev, order]
def route(m, a, b):
r = dijkstra(m, a)
if r[0][b] == -1:
return [-1, []]
path = [b]
x = b
while x != a:
x = r[1][x]
path = [x] + path
return [r[0][b], path]