Project P041
Maze
A random maze from a seed - the same seed always makes the same maze - built by a random depth-first walk with a few extra walls knocked down so that there is more than one way. Walk it from S to G, or show a shortest way found by breadth-first search beside the way the corpus case's backtracking finds.
3 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
A random maze of 3 to 10 rows and 3 to 15 columns, made from a seed - the same seed always makes the same maze. Walk it from S (top left) to G (bottom right), or show a shortest way through it beside the way the corpus case's backtracking finds, which need not be as short.
main.eml- the menu, the questions and their checks, walking, and the maze on screenmaze.eml- making a maze, the two ways through it, and drawing itrng.eml- the random generator of P008 (number guessing)
How each part works:
- A maze is made by a random depth-first walk: from the current cell, step to a random neighbour not yet visited and knock down the wall between; when there is none, step back. That knocks down the walls of a spanning tree, so every cell can be reached along exactly one way. Then about one wall in eight of those left inside is knocked down as well, so that some places can be reached in more than one way - otherwise every way through would be the same way.
- The shortest way comes from a breadth-first search from S: it reaches cells in order of distance, so the first time it reaches G, the way there is a shortest one.
- The backtracking way is the corpus case
maze-solver-backtracking: try down, right, up and left in that order, mark the cell, and unmark it when the branch dead-ends. It finds a way, not the shortest: on the maze from seed 335 in the basic session it takes 36 moves where 16 are enough. - Moves are typed as letters - u, d, l, r - several at a time; a move into a wall, or a letter that is not a move, stops there.
- The random numbers come from the generator written in EML for P008, not from Python's random module, so a session gives the same maze in CPython and in the EML interpreter.
What is checked: 3 to 10 rows and 3 to 15 columns; a seed of up to 9 digits; moves as u, d, l and r in either case. An empty answer cancels.
Sessions: sessions/basic.in walks the starting maze (seed 2026) with a detour of two moves and a stop at a wall, reaches G in 18 moves where the shortest way takes 16, and shows that way; then makes a 6 x 10 maze from seed 335, where the backtracking way takes 36 moves and the shortest 16. sessions/bad-input.in gives menu choices 0 and x, 2, 11 and x rows, 16 and 2 columns, seeds abc and 1234567890, then a 3 x 3 maze from seed 7: a move z, a move into the outer wall, an empty walk, the goal in 4 moves, a walk from the goal, and both ways (6 moves against 4).
Built on the verified corpus cases maze-solver-backtracking (a way through a maze by marking and unmarking cells, not necessarily the shortest) and graph-bfs-traversal (breadth-first traversal with a queue).
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== Maze ==
Walk from S to G. The same seed always makes the same maze.
A maze of 6 x 10 cells from seed 2026.
###############################
#@ # #
# #### # #### #### # # #
# # # # # # #
# # #### # # ########## #
# # # # # #
# #### #### # # # #######
# # # # # #
# # # # # #### # #### #
# # # # # #
####### # #### ####### # #
# # #G #
###############################
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 0
Pick a number from 1 to 6.
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> x
Pick a number from 1 to 6.
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 1
rows (3 to 10)> 2
Type a number from 3 to 10.
rows (3 to 10)> 11
Type a number from 3 to 10.
rows (3 to 10)> x
Type a number from 3 to 10.
rows (3 to 10)>
Cancelled.
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 1
rows (3 to 10)> 3
columns (3 to 15)> 16
Type a number from 3 to 15.
columns (3 to 15)> 2
Type a number from 3 to 15.
columns (3 to 15)>
Cancelled.
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 1
rows (3 to 10)> 3
columns (3 to 15)> 3
seed (a whole number)> abc
A seed is a whole number of up to 9 digits.
seed (a whole number)> 1234567890
A seed is a whole number of up to 9 digits.
seed (a whole number)>
Cancelled.
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 1
rows (3 to 10)> 3
columns (3 to 15)> 3
seed (a whole number)> 7
A maze of 3 x 3 cells from seed 7.
##########
#@ #
#### # #
# # #
# #### #
# G #
##########
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 2
moves (u, d, l, r - like rrdd)> z
Stopped at z: moves are u, d, l and r.
##########
#@ #
#### # #
# # #
# #### #
# G #
##########
0 moves so far.
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 2
moves (u, d, l, r - like rrdd)> u
Stopped: a wall up from here.
##########
#@ #
#### # #
# # #
# #### #
# G #
##########
0 moves so far.
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 2
moves (u, d, l, r - like rrdd)>
Cancelled.
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 2
moves (u, d, l, r - like rrdd)> rrdd
##########
#S #
#### # #
# # #
# #### #
# @ #
##########
You reached the goal in 4 moves; the shortest way takes 4 moves.
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 2
You have reached the goal already - choose a new maze to walk again.
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 4
##########
#S ... #
####..# #
#.....# #
#..#### #
#......@ #
##########
The backtracking way: 6 moves, trying down, right, up, left in that order; the shortest takes 4 moves.
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 3
##########
#S ......#
#### #..#
# #..#
# ####..#
# @ #
##########
A shortest way: 4 moves, found by breadth-first search.
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 5
##########
#S #
#### # #
# # #
# #### #
# @ #
##########
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 6
Bye.
What was typed (35 lines)
0
x
1
2
11
x
1
3
16
2
1
3
3
abc
1234567890
1
3
3
7
2
z
2
u
2
2
rrdd
2
4
3
5
6
basic
interpreter: byte-equal== Maze ==
Walk from S to G. The same seed always makes the same maze.
A maze of 6 x 10 cells from seed 2026.
###############################
#@ # #
# #### # #### #### # # #
# # # # # # #
# # #### # # ########## #
# # # # # #
# #### #### # # # #######
# # # # # #
# # # # # #### # #### #
# # # # # #
####### # #### ####### # #
# # #G #
###############################
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 2
moves (u, d, l, r - like rrdd)> rl
###############################
#@ # #
# #### # #### #### # # #
# # # # # # #
# # #### # # ########## #
# # # # # #
# #### #### # # # #######
# # # # # #
# # # # # #### # #### #
# # # # # #
####### # #### ####### # #
# # #G #
###############################
2 moves so far.
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 2
moves (u, d, l, r - like rrdd)> ddddrrrr
Stopped: a wall right from here.
###############################
#S # #
# #### # #### #### # # #
# # # # # # #
# # #### # # ########## #
# # # # # #
# #### #### # # # #######
# # # # # #
# # # # # #### # #### #
# @ # # # # #
####### # #### ####### # #
# # #G #
###############################
9 moves so far.
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 2
moves (u, d, l, r - like rrdd)> drrrrrurd
###############################
#S # #
# #### # #### #### # # #
# # # # # # #
# # #### # # ########## #
# # # # # #
# #### #### # # # #######
# # # # # #
# # # # # #### # #### #
# # # # # #
####### # #### ####### # #
# # #@ #
###############################
You reached the goal in 18 moves; the shortest way takes 16 moves.
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 3
###############################
#S # #
#..#### # #### #### # # #
#..# # # # # #
#..# #### # # ########## #
#.. # # # # #
#..#### #### # # # #######
#..# # # # #
#..# # # # #### # #### #
#...........# # # #.....#
####### #..#### #######..#..#
# #.................#@ #
###############################
A shortest way: 16 moves, found by breadth-first search.
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 1
rows (3 to 10)> 6
columns (3 to 15)> 10
seed (a whole number)> 335
A maze of 6 x 10 cells from seed 335.
###############################
#@ #
# ####### ####### #### # #
# # # # # #
####### #### # #### #### #
# # # #
# # # # ####### # #######
# # # # # #
# ########## # # ####### #
# # # # # # #
# # #### #### #### # # #
# # G #
###############################
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 4
###############################
#@ ........ #
#..####### #######..####..# #
#........# #.....#.....# #
#######..#### #..####..#### #
#.....#.. .....#.. #
#..#..#..# #######..#..#######
#..#.....# #..#........#
#..########## # #..#######..#
#..# # #.....# #..#
#..# #### #### ####..# #..#
#.......................# G #
###############################
The backtracking way: 36 moves, trying down, right, up, left in that order; the shortest takes 16 moves.
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 3
###############################
#@ ........................ #
# ####### ####### ####..# #
# # # #.....# #
####### #### # ####..#### #
# # #.. #
# # # # ####### #..#######
# # # # #........#
# ########## # # #######..#
# # # # # #..#
# # #### #### #### # #..#
# # G #
###############################
A shortest way: 16 moves, found by breadth-first search.
1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit
choice> 6
Bye.
What was typed (14 lines)
2
rl
2
ddddrrrr
2
drrrrrurd
3
1
6
10
335
4
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# P041 maze: a random maze from a seed - the same seed always makes the same
# maze. Walk it from S to G, or show a shortest way (breadth-first search)
# and the way the corpus case's backtracking finds, which need not be as
# short.
import maze
import rng
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 number(s):
# The value of 1 to 9 digits, otherwise -1.
if s == "" or len(s) > 9:
return -1
0 => n
for c in s:
if not (c in "0123456789"):
return -1
n * 10 + int(c) => n
return n
def moves_text(n):
if n == 1:
return "1 move"
return str(n) + " moves"
def show(state, way):
for line in maze.drawn(state[0], way, state[2]):
line ^0
def make(rows, cols, seed):
maze.generate(rows, cols, rng.Rng(seed)) => m
("A maze of " + str(rows) + " x " + str(cols) + " cells from seed " + str(seed) + ".") ^0
return [m, seed, [0, 0], 0]
def ask(prompt, low, high):
while True:
trim(input(prompt + " (" + str(low) + " to " + str(high) + ")> ")) => answer
if answer == "":
return -1
number(answer) => n
if n >= low and n <= high:
return n
("Type a number from " + str(low) + " to " + str(high) + ".") ^0
def new_maze(state):
ask("rows", 3, 10) => rows
if rows == -1:
"Cancelled." ^0
return state
ask("columns", 3, 15) => cols
if cols == -1:
"Cancelled." ^0
return state
while True:
trim(input("seed (a whole number)> ")) => answer
if answer == "":
"Cancelled." ^0
return state
number(answer) => seed
if seed >= 0:
make(rows, cols, seed) => state
show(state, [])
return state
"A seed is a whole number of up to 9 digits." ^0
def walk(state):
state[0] => m
if state[2][0] == m[0] - 1 and state[2][1] == m[1] - 1:
"You have reached the goal already - choose a new maze to walk again." ^0
return state
trim(input("moves (u, d, l, r - like rrdd)> ")) => answer
if answer == "":
"Cancelled." ^0
return state
state[2][0] => r
state[2][1] => c
state[3] => made
for ch in answer:
-1 => d
if ch == "u" or ch == "U":
0 => d
elif ch == "r" or ch == "R":
1 => d
elif ch == "d" or ch == "D":
2 => d
elif ch == "l" or ch == "L":
3 => d
if d == -1:
("Stopped at " + ch + ": moves are u, d, l and r.") ^0
return finish(state, r, c, made)
if not maze.open_between(m, r, c, d):
("Stopped: a wall " + maze.names[d] + " from here.") ^0
return finish(state, r, c, made)
r + maze.dr[d] => r
c + maze.dc[d] => c
made + 1 => made
if r == m[0] - 1 and c == m[1] - 1:
return finish(state, r, c, made)
return finish(state, r, c, made)
def finish(state, r, c, made):
[state[0], state[1], [r, c], made] => state
show(state, [])
state[0] => m
if r == m[0] - 1 and c == m[1] - 1:
len(maze.shortest(m)) - 1 => best
("You reached the goal in " + moves_text(made) + "; the shortest way takes " + moves_text(best) + ".") ^0
else:
(moves_text(made) + " so far.") ^0
return state
"== Maze ==" ^0
"Walk from S to G. The same seed always makes the same maze." ^0
make(6, 10, 2026) => state
show(state, [])
True => running
while running:
"" ^0
"1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit" ^0
trim(input("choice> ")) => choice
if choice == "1":
new_maze(state) => state
elif choice == "2":
walk(state) => state
elif choice == "3":
maze.shortest(state[0]) => way
show(state, way)
("A shortest way: " + moves_text(len(way) - 1) + ", found by breadth-first search.") ^0
elif choice == "4":
maze.backtracking(state[0]) => way
show(state, way)
len(maze.shortest(state[0])) - 1 => best
("The backtracking way: " + moves_text(len(way) - 1) + ", trying down, right, up, left in that order; the shortest takes " + moves_text(best) + ".") ^0
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 maze
import rng
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 number(s):
if s == "" or len(s) > 9:
return -1
n = 0
for c in s:
if not c in "0123456789":
return -1
n = n * 10 + int(c)
return n
def moves_text(n):
if n == 1:
return "1 move"
return str(n) + " moves"
def show(state, way):
for line in maze.drawn(state[0], way, state[2]):
print(line)
def make(rows, cols, seed):
m = maze.generate(rows, cols, rng.Rng(seed))
print("A maze of " + str(rows) + " x " + str(cols) + " cells from seed " + str(seed) + ".")
return [m, seed, [0, 0], 0]
def ask(prompt, low, high):
while True:
answer = trim(input(prompt + " (" + str(low) + " to " + str(high) + ")> "))
if answer == "":
return -1
n = number(answer)
if n >= low and n <= high:
return n
print("Type a number from " + str(low) + " to " + str(high) + ".")
def new_maze(state):
rows = ask("rows", 3, 10)
if rows == -1:
print("Cancelled.")
return state
cols = ask("columns", 3, 15)
if cols == -1:
print("Cancelled.")
return state
while True:
answer = trim(input("seed (a whole number)> "))
if answer == "":
print("Cancelled.")
return state
seed = number(answer)
if seed >= 0:
state = make(rows, cols, seed)
show(state, [])
return state
print("A seed is a whole number of up to 9 digits.")
def walk(state):
m = state[0]
if state[2][0] == m[0] - 1 and state[2][1] == m[1] - 1:
print("You have reached the goal already - choose a new maze to walk again.")
return state
answer = trim(input("moves (u, d, l, r - like rrdd)> "))
if answer == "":
print("Cancelled.")
return state
r = state[2][0]
c = state[2][1]
made = state[3]
for ch in answer:
d = -1
if ch == "u" or ch == "U":
d = 0
elif ch == "r" or ch == "R":
d = 1
elif ch == "d" or ch == "D":
d = 2
elif ch == "l" or ch == "L":
d = 3
if d == -1:
print("Stopped at " + ch + ": moves are u, d, l and r.")
return finish(state, r, c, made)
if not maze.open_between(m, r, c, d):
print("Stopped: a wall " + maze.names[d] + " from here.")
return finish(state, r, c, made)
r = r + maze.dr[d]
c = c + maze.dc[d]
made = made + 1
if r == m[0] - 1 and c == m[1] - 1:
return finish(state, r, c, made)
return finish(state, r, c, made)
def finish(state, r, c, made):
state = [state[0], state[1], [r, c], made]
show(state, [])
m = state[0]
if r == m[0] - 1 and c == m[1] - 1:
best = len(maze.shortest(m)) - 1
print("You reached the goal in " + moves_text(made) + "; the shortest way takes " + moves_text(best) + ".")
else:
print(moves_text(made) + " so far.")
return state
print("== Maze ==")
print("Walk from S to G. The same seed always makes the same maze.")
state = make(6, 10, 2026)
show(state, [])
running = True
while running:
print("")
print("1) new maze 2) walk 3) shortest way 4) backtracking way 5) show 6) quit")
choice = trim(input("choice> "))
if choice == "1":
state = new_maze(state)
elif choice == "2":
state = walk(state)
elif choice == "3":
way = maze.shortest(state[0])
show(state, way)
print("A shortest way: " + moves_text(len(way) - 1) + ", found by breadth-first search.")
elif choice == "4":
way = maze.backtracking(state[0])
show(state, way)
best = len(maze.shortest(state[0])) - 1
print("The backtracking way: " + moves_text(len(way) - 1) + ", trying down, right, up, left in that order; the shortest takes " + moves_text(best) + ".")
elif choice == "5":
show(state, [])
elif choice == "6":
running = False
else:
print("Pick a number from 1 to 6.")
print("Bye.")
maze.eml
eml# P041 maze - making a maze and finding ways through it. A maze is
# [rows, cols, right, down]: right[r][c] is True when a wall stands between
# cell (r, c) and the cell to its right, down[r][c] when one stands between
# it and the cell below. The way in is the top-left cell, the way out the
# bottom-right one.
# up, right, down, left
[-1, 0, 1, 0] => dr
[0, 1, 0, -1] => dc
["up", "right", "down", "left"] => names
def walls(rows, cols):
[] => grid
for r in [1:rows]:
grid + [[True] * cols] => grid
return grid
def open_between(m, r, c, d):
# Can one step from (r, c) in direction d (0 up, 1 right, 2 down, 3 left)?
r + dr[d] => y
c + dc[d] => x
if y < 0 or y >= m[0] or x < 0 or x >= m[1]:
return False
if d == 0:
return not m[3][y][x]
if d == 1:
return not m[2][r][c]
if d == 2:
return not m[3][r][c]
return not m[2][y][x]
def knock(m, r, c, d):
# Takes down the wall on side d of cell (r, c).
if d == 0:
False => m[3][r - 1][c]
elif d == 1:
False => m[2][r][c]
elif d == 2:
False => m[3][r][c]
else:
False => m[2][r][c - 1]
def generate(rows, cols, rng):
# A random depth-first walk knocks down the walls of a spanning tree, so
# every cell is reachable along exactly one way; then about one wall in
# eight of those left inside is knocked down too, so that some places
# can be reached in more than one way.
[rows, cols, walls(rows, cols), walls(rows, cols)] => m
[] => seen
for r in [1:rows]:
seen + [[False] * cols] => seen
True => seen[0][0]
[[0, 0]] => stack
while len(stack) > 0:
stack[len(stack) - 1] => cell
[] => choices
for d in [0:3]:
cell[0] + dr[d] => y
cell[1] + dc[d] => x
if y >= 0 and y < rows and x >= 0 and x < cols and not seen[y][x]:
choices + [d] => choices
if len(choices) == 0:
stack[0:len(stack) - 1] => stack
else:
choices[rng.below(len(choices))] => d
knock(m, cell[0], cell[1], d)
cell[0] + dr[d] => y
cell[1] + dc[d] => x
True => seen[y][x]
stack + [[y, x]] => stack
[] => standing
for r in [0:rows - 1]:
for c in [0:cols - 1]:
if c < cols - 1 and m[2][r][c]:
standing + [[r, c, 1]] => standing
if r < rows - 1 and m[3][r][c]:
standing + [[r, c, 2]] => standing
int(rows * cols / 8) => extra
while extra > 0 and len(standing) > 0:
rng.below(len(standing)) => k
standing[k] => w
knock(m, w[0], w[1], w[2])
standing[0:k] + standing[k + 1:len(standing)] => standing
extra - 1 => extra
return m
def shortest(m):
# Breadth-first search from the way in: cells are reached in order of
# distance, so the first time the way out is reached, the way there is
# a shortest one. Returns the cells from the way in to the way out.
m[0] => rows
m[1] => cols
[] => before
for r in [1:rows]:
before + [[-1] * cols] => before
0 => before[0][0]
[[0, 0]] => queue
0 => head
while head < len(queue):
queue[head] => cell
head + 1 => head
for d in [0:3]:
if open_between(m, cell[0], cell[1], d):
cell[0] + dr[d] => y
cell[1] + dc[d] => x
if before[y][x] == -1:
cell[0] * cols + cell[1] => before[y][x]
queue + [[y, x]] => queue
[[rows - 1, cols - 1]] => way
while way[0][0] != 0 or way[0][1] != 0:
before[way[0][0]][way[0][1]] => p
[[int(p / cols), p % cols]] + way => way
return way
def wander(m, marks, r, c, path):
# The corpus case maze-solver-backtracking: try down, right, up, left in
# that order, mark the cell, and unmark it when the branch dead-ends.
# It finds a way, not necessarily the shortest.
path + [[r, c]] => here
if r == m[0] - 1 and c == m[1] - 1:
return here
True => marks[r][c]
for d in [2, 1, 0, 3]:
if open_between(m, r, c, d) and not marks[r + dr[d]][c + dc[d]]:
wander(m, marks, r + dr[d], c + dc[d], here) => found
if len(found) > 0:
return found
False => marks[r][c]
return []
def backtracking(m):
[] => marks
for r in [1:m[0]]:
marks + [[False] * m[1]] => marks
return wander(m, marks, 0, 0, [])
def drawn(m, way, at):
# The maze as lines of text: walls #, the way in S, the way out G, the
# walker @, and a way through as dots, on its cells and between them.
m[0] => rows
m[1] => cols
[] => on
for r in [1:rows]:
on + [[False] * cols] => on
for cell in way:
True => on[cell[0]][cell[1]]
[] => lines
"#" * (3 * cols + 1) => top
lines + [top] => lines
for r in [0:rows - 1]:
"#" => line
"#" => under
for c in [0:cols - 1]:
" " => body
if on[r][c]:
".." => body
if r == 0 and c == 0:
"S " => body
if r == rows - 1 and c == cols - 1:
"G " => body
if r == at[0] and c == at[1]:
"@ " => body
line + body => line
if c == cols - 1 or m[2][r][c]:
line + "#" => line
elif on[r][c] and on[r][c + 1] and next_to(way, r, c, r, c + 1):
line + "." => line
else:
line + " " => line
if r == rows - 1 or m[3][r][c]:
under + "###" => under
elif on[r][c] and on[r + 1][c] and next_to(way, r, c, r + 1, c):
under + "..#" => under
else:
under + " #" => under
lines + [line, under] => lines
return lines
def next_to(way, r1, c1, r2, c2):
# Are the two cells one step apart along the way?
for i in [0:len(way) - 2]:
if way[i][0] == r1 and way[i][1] == c1 and way[i + 1][0] == r2 and way[i + 1][1] == c2:
return True
if way[i][0] == r2 and way[i][1] == c2 and way[i + 1][0] == r1 and way[i + 1][1] == c1:
return True
return False
Python projection (maze.py)
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
names = ["up", "right", "down", "left"]
def walls(rows, cols):
grid = []
for r in range(1, rows+1):
grid = grid + [[True] * cols]
return grid
def open_between(m, r, c, d):
y = r + dr[d]
x = c + dc[d]
if y < 0 or y >= m[0] or x < 0 or x >= m[1]:
return False
if d == 0:
return not m[3][y][x]
if d == 1:
return not m[2][r][c]
if d == 2:
return not m[3][r][c]
return not m[2][y][x]
def knock(m, r, c, d):
if d == 0:
m[3][r - 1][c] = False
elif d == 1:
m[2][r][c] = False
elif d == 2:
m[3][r][c] = False
else:
m[2][r][c - 1] = False
def generate(rows, cols, rng):
m = [rows, cols, walls(rows, cols), walls(rows, cols)]
seen = []
for r in range(1, rows+1):
seen = seen + [[False] * cols]
seen[0][0] = True
stack = [[0, 0]]
while len(stack) > 0:
cell = stack[len(stack) - 1]
choices = []
for d in range(0, 4):
y = cell[0] + dr[d]
x = cell[1] + dc[d]
if y >= 0 and y < rows and x >= 0 and x < cols and not seen[y][x]:
choices = choices + [d]
if len(choices) == 0:
stack = stack[0:len(stack) - 1]
else:
d = choices[rng.below(len(choices))]
knock(m, cell[0], cell[1], d)
y = cell[0] + dr[d]
x = cell[1] + dc[d]
seen[y][x] = True
stack = stack + [[y, x]]
standing = []
for r in range(0, rows):
for c in range(0, cols):
if c < cols - 1 and m[2][r][c]:
standing = standing + [[r, c, 1]]
if r < rows - 1 and m[3][r][c]:
standing = standing + [[r, c, 2]]
extra = int(rows * cols / 8)
while extra > 0 and len(standing) > 0:
k = rng.below(len(standing))
w = standing[k]
knock(m, w[0], w[1], w[2])
standing = standing[0:k] + standing[k + 1:len(standing)]
extra = extra - 1
return m
def shortest(m):
rows = m[0]
cols = m[1]
before = []
for r in range(1, rows+1):
before = before + [[-1] * cols]
before[0][0] = 0
queue = [[0, 0]]
head = 0
while head < len(queue):
cell = queue[head]
head = head + 1
for d in range(0, 4):
if open_between(m, cell[0], cell[1], d):
y = cell[0] + dr[d]
x = cell[1] + dc[d]
if before[y][x] == -1:
before[y][x] = cell[0] * cols + cell[1]
queue = queue + [[y, x]]
way = [[rows - 1, cols - 1]]
while way[0][0] != 0 or way[0][1] != 0:
p = before[way[0][0]][way[0][1]]
way = [[int(p / cols), p % cols]] + way
return way
def wander(m, marks, r, c, path):
here = path + [[r, c]]
if r == m[0] - 1 and c == m[1] - 1:
return here
marks[r][c] = True
for d in [2, 1, 0, 3]:
if open_between(m, r, c, d) and not marks[r + dr[d]][c + dc[d]]:
found = wander(m, marks, r + dr[d], c + dc[d], here)
if len(found) > 0:
return found
marks[r][c] = False
return []
def backtracking(m):
marks = []
for r in range(1, m[0]+1):
marks = marks + [[False] * m[1]]
return wander(m, marks, 0, 0, [])
def drawn(m, way, at):
rows = m[0]
cols = m[1]
on = []
for r in range(1, rows+1):
on = on + [[False] * cols]
for cell in way:
on[cell[0]][cell[1]] = True
lines = []
top = "#" * (3 * cols + 1)
lines = lines + [top]
for r in range(0, rows):
line = "#"
under = "#"
for c in range(0, cols):
body = " "
if on[r][c]:
body = ".."
if r == 0 and c == 0:
body = "S "
if r == rows - 1 and c == cols - 1:
body = "G "
if r == at[0] and c == at[1]:
body = "@ "
line = line + body
if c == cols - 1 or m[2][r][c]:
line = line + "#"
elif on[r][c] and on[r][c + 1] and next_to(way, r, c, r, c + 1):
line = line + "."
else:
line = line + " "
if r == rows - 1 or m[3][r][c]:
under = under + "###"
elif on[r][c] and on[r + 1][c] and next_to(way, r, c, r + 1, c):
under = under + "..#"
else:
under = under + " #"
lines = lines + [line, under]
return lines
def next_to(way, r1, c1, r2, c2):
for i in range(0, len(way) - 2+1):
if way[i][0] == r1 and way[i][1] == c1 and way[i + 1][0] == r2 and way[i + 1][1] == c2:
return True
if way[i][0] == r2 and way[i][1] == c2 and way[i + 1][0] == r1 and way[i + 1][1] == c1:
return True
return False
rng.eml
eml# P041 maze - random numbers written in EML: the linear congruential
# generator of P008 (number guessing), with the constants of the C
# standard's example rand(). Python's random module is not used, so a seed
# gives the same maze on every machine, and the interpreter can check a
# whole session byte for byte.
class Rng:
def __init__(self, seed):
seed % 2147483648 => self.state
def step(self):
(1103515245 * self.state + 12345) % 2147483648 => self.state
return self.state
def below(self, n):
# A number from 0 to n - 1, taken from the high bits of the state: the
# low bits of this generator repeat with short periods. Dividing by
# 65536 is exact in a float for a state below 2^31.
return int(self.step() / 65536) % n
Python projection (rng.py)
class Rng:
def __init__(self, seed):
self.state = seed % 2147483648
def step(self):
self.state = (1103515245 * self.state + 12345) % 2147483648
return self.state
def below(self, n):
return int(self.step() / 65536) % n