# Principled Programming / Tim Teitelbaum / Chapter 16.
class MRP:
"""
# Maze, Rat, and Path (MRP) Representations.
# Methods.
# Motion
turn_clockwise(cls) -> None
turn_counter_clockwise(cls) -> None
step_forward(cls) -> None
step_backward(cls) -> None
face_previous(cls) -> None
# Predicates
is_facing_wall(cls) -> bool
is_facing_unvisited(cls) -> bool
is_about_to_repeat(cls) -> bool
is_at_cheese(cls) -> bool
# I/O.
input(cls) -> None
print_maze(cls) -> None
# Tossed arrow abstraction.
record_neighbor_and_direction(cls) -> None
is_at_neighbor(cls) -> bool
restore_direction(cls) -> None
# Self-Checking and Validity Checking.
is_solution(cls) -> bool
generate_input(cls, n int, w: int) -> None
# See also.
Chapter 15 of Principled Programming
Chapter 17 of Principled Programming, which uses elements of MRP for an alternative solution.
"""
# 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 ]
# Recorded state.
_neighbor_number: int ## Visit number of cell into which the arrow was tossed.
_neighbor_direction: int # Direction when the arrow was tossed.
# Public interface.
# Motion.
@classmethod
def turn_clockwise(cls) -> None:
MRP._d = (MRP._d + 1) % 4
@classmethod
def turn_counter_clockwise(cls) -> None:
MRP._d = (MRP._d + 3) % 4
@classmethod
def step_forward(cls) -> None:
MRP._r += 2 * MRP._deltaR[MRP._d]; MRP._c += 2 * MRP._deltaC[MRP._d]
MRP._move += 1; MRP._M[MRP._r][MRP._c] = MRP._move
@classmethod
def step_backward(cls) -> None:
MRP._M[MRP._r][MRP._c] = MRP._UNVISITED
MRP._move -= 1
MRP._r += 2 * MRP._deltaR[MRP._d]
MRP._c += 2 * MRP._deltaC[MRP._d]
@classmethod
def face_previous(cls) -> None:
MRP._d = 0
while MRP.is_facing_wall() or (MRP._M[MRP._r][MRP._c] - 1 !=
MRP._M[MRP._r + 2 * MRP._deltaR[MRP._d]
][MRP._c + 2 * MRP._deltaC[MRP._d]]
): MRP._d += 1
# Predicates
@classmethod
def is_facing_wall(cls) -> bool:
return MRP._M[MRP._r + MRP._deltaR[MRP._d]
][MRP._c + MRP._deltaC[MRP._d]] == MRP._WALL
@classmethod
def is_at_cheese(cls) -> bool:
return (MRP._r == MRP._hi) and (MRP._c == MRP._hi)
@classmethod
def is_about_to_repeat(cls) -> bool:
return (MRP._r == MRP._lo) and (MRP._c == MRP._lo) and (MRP._d == 3)
@classmethod
def is_facing_unvisited(cls) -> bool:
return MRP._M[MRP._r + 2 * MRP._deltaR[MRP._d]
][MRP._c + 2 * MRP._deltaC[MRP._d]] == MRP._UNVISITED
# I/O.
@classmethod
def input(cls) -> None:
"""Input N-by-N maze."""
# Input file split into lines.
# file = "1\nxxx\nx x\nxxx\nxxx" # 1x1.
# file = "2\nxxxxx\nx x x\nx x\nx x\nxxxxx" # 2x2, with obstacle.
# file = "3\nxxxxxxx\nx x\nx x x\nx xx x\nx xxxxx\nx x\nxxxxxxx" # 3x3, with room.
file = "5\n###########\n# # #\n# ## # # #\n# # # #\n# # ## ###\n# # # #\n# # # ### #\n# # # # #\n# ### #####\n# # #\n###########\n" # 5x5, for Chapter 19. lines = file.split("\n")
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()
# Tossed arrow abstraction.
@classmethod
def record_neighbor_and_direction(cls) -> None:
"""Toss an arrow into the neighboring cell in the direction faced."""
MRP._neighbor_number = MRP._M[MRP._r + 2 * MRP._deltaR[MRP._d]
][MRP._c + 2 * MRP._deltaC[MRP._d]]
MRP._neighbor_direction = MRP._d
@classmethod
def is_at_neighbor(cls) -> bool:
"""Detect being in the same cell as the arrow."""
return MRP._M[MRP._r][MRP._c] == MRP._neighbor_number
@classmethod
def restore_direction(cls) -> None:
"""'Align direction with the arrow'"""
MRP._d = MRP._neighbor_direction
# Self-Checking and Validity Checking.
@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
@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.