# Principled Programming / Tim Teitelbaum / Chapter 17.
# Maze, Rat, and Path (MRP) Representations.
class MRP:
# GRAPH REPRESENTATIONS
# Maze. Cells of a maze are represented by N*N nodes of an
# undirected graph. G[n] is an edge list for node n, i.e., for
# 0<=e<len(G[n]), G[n][e] is an adjacent node n, i.e., a cell
# adjacent to n with no Wall between them. The upper-left cell is
# node 0. Cheese is at cheese_node. */
_G: list[list[int]] # Edge lists.
_cheese_node: int # Cheese.
# Path. Array path[0..path_length-1] is a list of adjacent nodes in
# G reaching from node 0 to some node path[path_length-1]. */
_path: list[int]
_path_length: int
@classmethod
def is_at_cheese(cls) -> bool:
return MRP._path[MRP._path_length - 1] == MRP._cheese_node
# SOLUTION BY DEPTH-FIRST SEARCH
@classmethod
def search(cls) -> None:
"""
Convert representation M[N][N] to graph G, then perform DFS from upper-left,
then convert computed path to representation M[N][N].
"""
MRP._make_graph_from_input()
try:
MRP._DFS(0, 0)
except Exception:
pass
MRP._make_output_from_path()
_mark: list[bool] # mark[n] iff DFS reached node n.
@classmethod
def _DFS(cls, n: int, p: int) -> None:
"""Depth First Search (DFS) of node n for cheese_node at depth p."""
if not MRP._mark[n]: # Node n has not been visited before.
MRP._mark[n] = True # Mark that n has been visited.
MRP._path[p] = n # Extend the path to include n.
if n == MRP._cheese_node: # Terminate search if cheese found.
MRP._path_length = p + 1 # Length of path is one longer than p.
raise Exception("found cheese")
for e in range(0, len(MRP._G[n])):
MRP._DFS(MRP._G[n][e], p + 1)
# LEGACY REPRESENTATIONS (Chapter 15)
# Maze. Cells of an N-by-N maze are represented by elements of a
# (2*N+1)-by(2*N+1) array M. Maze cell ⟨r,c⟩ is represented by array
# element M[2*r+1][2*c+1]. The possible walls ⟨top, right, bottom,
# left⟩ of the maze cell corresponding to ⟨r,c⟩ are represented by
# WALL or NO_WALL in ⟨M[r-1][c], M[r][c+1], M[r+1][c], M[r][c-1]⟩.
# The remaining elements of M are unused. lo is 1, and hi is 2*N-1.
_N: int = 0 # _N is size of maze.
_M: list[list[int]] = [] # _M is _N-by-_N maze, walls, and path.
_WALL: int = -1 # _WALL encodes presence of a wall.
_NO_WALL: int = 0 # _NO_WALL encodes absence of a wall.
_lo: int = 1 # _lo is left and top maze indices.
_hi: int = 2 * _N - 1 # _hi is right and bottom maze indices.
# Rat. The rat is located in cell M[r][c] facing direction d, where
# d=⟨0,1,2,3⟩ represents the orientation ⟨up,right,down,left⟩,
# respectively.
_r: int = _lo
_c: int = _lo
_d: int = 0
# Path. When the rat has traveled to cell ⟨r,c⟩ via a given path
# through cells of the maze, the elements of M that correspond to
# those cells will be 1, 2, 3, etc., and all other elements of M
# that correspond to cells of the maze will be UNVISITED. The
# number of the last step in the path is move.
_UNVISITED: int = 0
_move: int = _lo
# Unit vectors in direction d
# d = 0, 1, 2, 3
# up, right, down, left
_deltaR: list[int] = [ -1, 0, 1, 0 ]
_deltaC: list[int] = [ 0, 1, 0, -1 ]
# Input N-by-N maze.
@classmethod
def input(cls) -> None:
# Input file split into lines.
# file = "3\nxxxxxxx\nx x\nx x x\nx xx x\nx xxxxx\nx x\nxxxxxxx" # 3x3, with room.
# file = "1\nxxx\nx x\nxxx\nxxx" # 1x1.
# file = "2\nxxxxx\nx x x\nx x\nx x\nxxxxx" # 2x2, with obstacle.
# file = "2\nxxxxx\nx x\nx x\nx x\nxxxxx" # 2x2, no obstacle.
file = "5\nxxxxxxxxxxx\nx x x\nx x x\nx x x x\nx x xx\nx x x x\nx x x\nx x x x x x\nx x x xx\nx x x\nxxxxxxxxxxx\n" # 5x5, for Chapter 19.
lines = file.split("\n")
# Maze. As per representation invariant.
MRP._N = int(lines[0]); del lines[0]
MRP._lo = 1; MRP._hi = 2 * MRP._N - 1
MRP._M = [[0 for _ in range(2 * MRP._N + 1)] for _ in range(2 * MRP._N + 1)]
for r in range(MRP._lo - 1, MRP._hi + 2):
line = lines[0]; del lines[0]
for c in range(MRP._lo - 1, MRP._hi + 2):
if (r % 2 == 1) and (c % 2 == 1): MRP._M[r][c] = MRP._UNVISITED
elif line[c:c+1] == " ":
MRP._M[r][c] = MRP._NO_WALL
else: MRP._M[r][c] = MRP._WALL
# Rat. Place rat in upper-left cell facing up.
MRP._r = MRP._lo; MRP._c = MRP._lo; MRP._d = 0
# Path. Establish the rat in the upper-left cell.
MRP._move = 1; MRP._M[MRP._r][MRP._c] = MRP._move
@classmethod
def print_maze(cls) -> None:
"""Output N-by-N maze, with walls and path."""
for r in range(MRP._lo - 1, MRP._hi + 2):
for c in range(MRP._lo - 1, MRP._hi + 2):
if MRP._M[r][c] == MRP._WALL: s = "#"
elif ((MRP._M[r][c] == MRP._NO_WALL) or
(MRP._M[r][c] == MRP._UNVISITED)): s = " "
else: s = str(MRP._M[r][c]) + ""
print((s + " ")[0:3], end='')
print()
# CONVERSION LEGACY ==> GRAPH
@classmethod
def _make_graph_from_input(cls) -> None:
"""Create undirected graph representation of maze and path."""
MRP._G = [[0] for _ in range(MRP._N)
for _ in range(MRP._N)]
MRP._cheese_node = (MRP._N * MRP._N) - 1 # Node containing cheese.
MRP._path = [0] * (MRP._N * MRP._N) # Path of rat from 0 to cheese_node, if possible.
MRP._mark = [False] * (MRP._N * MRP._N) # mark[n] iff DFS has reached n.
MRP._path_length = 0
n: int = 0 # Node number.
for r in range(MRP._lo, MRP._hi + 1, 2):
for c in range (MRP._lo, MRP._hi + 1, 2):
MRP._G[n] = [0] * MRP._count_edges(r, c)
e: int = 0 # Edge number.
for d in range(0, 4):
if MRP._M[r + MRP._deltaR[d]][c + MRP._deltaC[d]] == MRP._NO_WALL:
MRP._G[n][e] = MRP._node(r + 2 * MRP._deltaR[d], c + 2 * MRP._deltaC[d])
e += 1
n += 1
# CONVERSION GRAPH ==> LEGACY
@classmethod
def _count_edges(cls, r: int, c: int) -> int:
"""Return cell <r,c>'s number of outgoing edges."""
e: int = 0 # Number of edges.
for d in range(0, 4):
if MRP._M[r + MRP._deltaR[d]][c + MRP._deltaC[d]] == MRP._NO_WALL:
e += 1
return e
@classmethod
def _node(cls, r: int, c: int) -> int:
"""Return node number from <r,c> in M."""
return MRP._N * (r//2) + (c//2)
@classmethod
def _row(cls, n: int) -> int:
"""Return r of <r,c> in M given node n."""
return 2 * (n // MRP._N) + 1
@classmethod
def _column(cls, n: int) -> int:
"""Return c of <r,c> in M given node n."""
return 2 * (n % MRP._N ) + 1
@classmethod
def _make_output_from_path(cls) -> None:
"""Create undirected graph representation of maze and path."""
for q in range(0, MRP._path_length):
MRP._M[MRP._row(MRP._path[q])][MRP._column(MRP._path[q])] = q + 1
# MISC LEGACY SELF-CHECKING, EXHAUSTIVE TESTING, AND FUZZ TESTING. (Chapter15)
@classmethod
def _is_valid_path(cls, r: int, c: int) -> bool:
"""Return False iff rat reached cell ⟨r,c⟩ via an invalid path."""
if MRP._M[r][c] == MRP._UNVISITED: return True # No claim if UNVISITED.
else:
while not((r == MRP._lo) and (c == MRP._lo)):
# Go to any valid predecessor; return False if there is none.
d = 0
while (d < 4) and ( (
MRP._M[r + MRP._deltaR[d]
][c + MRP._deltaC[d]] == MRP._WALL
) or (MRP._M[r + 2 * MRP._deltaR[d]][
c + 2 * MRP._deltaC[d]] != (MRP._M[r][c] - 1)
) ): d += 1
if d == 4: return False
r += 2 * MRP._deltaR[d]; c += 2 * MRP._deltaC[d]
return True # Reached upper-left cell.
@classmethod
def is_solution(cls) -> bool:
"""Return False iff rat reached lower-right cell via an invalid path."""
return MRP._is_valid_path(MRP._hi, MRP._hi)
@classmethod
def generate_input(cls, n: int, w: int) -> None:
"""Create an N-by-N maze with walls given by the bits of w."""
# Maze.
MRP._N = n; lo = MRP._lo = 1; hi = MRP._hi = 2 * n - 1
MRP._M = [[0 for _ in range(2 * n + 1)] for _ in range(2 * n + 1)]
# Set boundary walls.
for i in range(0, hi+2):
MRP._M[lo - 1][i] = MRP._M[hi + 1][i] = MRP._WALL
MRP._M[i][lo - 1] = MRP._M[i][hi + 1] = MRP._WALL
# Set 2*n*(n-1) interior walls to the corresponding bits of w.
for r in range(lo, hi + 1):
for c in range(lo, hi + 1):
if (r%2 == 0 and c%2 == 1) or (r%2 == 1 and c%2 == 0):
if w%2 == 1: MRP._M[r][c] = MRP._WALL
else: MRP._M[r][c] = MRP._NO_WALL
w = w // 2
# Rat.
MRP._r = lo; MRP._c = lo; MRP._d = 0
# Path.
MRP._move = 1; MRP._M[lo][lo] = MRP._move