# Principled Programming / Tim Teitelbaum / Chapter 19.
class MRP:
"""
Maze, Rat, and Path (MRP) Representations.
## Methods
# Rat motions and path extension/retractions.
turn_clockwise(cls) -> None
turn_counter_clockwise(cls) -> None
step_forward(cls) -> None
step_backward(cls) -> None
face_previous(cls) -> None
# Maze inspection predicates.
is_facing_wall(cls) -> bool
is_at_cheese(cls) -> bool
is_about_to_repeat(cls) -> bool
is_facing_unvisited(cls) -> bool
# Maze 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
# Validity checking, testing, and debugging.
is_valid(cls) -> bool
is_valid_rat(cls) -> bool
is_solution(cls) -> bool
generate_input(cls, n: int, w: int) -> None:
print_state(self, s: str) -> None
"""
# Maze. Cells of an N-by-N maze are represented by elements of
# array M[2*N+1][2*N+1]. 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 the maze."""
_M: list[list[int]] = []
"""_M is a 2-D array containing visit numbers and wall representations.
M[r][c], for odd r and c, are int visit numbers (1 thru _move), or _UNVISITED.
M[r][c], for r and c of opposite parity, are wall representations: _WALL or _NO_WALL.
M[r][c], for even r and c, are unused.
"""
_WALL: int = -1
"""_WALL (in elements _M[r][c] with r and c of opposite parity) represents the presence of a wall."""
_NO_WALL: int = 0
"""_NO_WALL (in elements _M[r][c] with r and c of opposite parity) represents the absence of a wall."""
_lo: int = 1 # Left and right maze indices.
"""_lo is the row and column index of the upper-left cell of _M[][]."""
_hi: int = 2 * _N - 1 # Top and right maze indices.
"""_lo is the row and column index of the lower-right cell of _M[][]."""
# 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
"""_r is the row coordinate of the rat's current position."""
_c: int = _lo
"""_c is the column coordinate of the rat's current position."""
_d: int = 0
"""_d is the index number in <up,right,down,left> of the rat's present direction faced."""
# 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
"""_UNVISITED represents a cell _M[r][c] that is not on the rat's current path."""
_move: int = _lo
"""_move is the visit number of the last cell of the current path. """
# Recorded state.
_neighbor_number: int # Recorded visit #.
"""The visit number of a cell into which an arrow has been tossed."""
_neighbor_direction: int # Dir. at time of recording.
"""The direction faced by the rat at the time an arrow was tossed into the cell in front of it."""
# Unit vectors in direction d
# d = 0, 1, 2, 3
# up, right, down, left
_deltaR: list[int] = [ -1, 0, 1, 0 ]
"""_deltaR[d] is the row component of a unit vector in direction d."""
_deltaC: list[int] = [ 0, 1, 0, -1 ]
"""_deltaC[d] is the column component of a unit vector in direction d."""
# Public interface.
# =================
# Rat motions and path extension / retractions.
@classmethod
def turn_clockwise(cls) -> None:
"""Turn the rat 90 degrees clockwise."""
MRP._d = (MRP._d + 1) % 4
@classmethod
def turn_counter_clockwise(cls) -> None:
"""Turn the rat 90 degrees counter-clockwise."""
MRP._d = (MRP._d - 1) % 4
@classmethod
def step_forward(cls) -> None:
"""Step one cell forward. Precondition: Not facing a wall."""
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:
"""Step one cell along the current path (but in the direction faced). Precondition: Not facing a wall."""
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:
"""Turn in place to face the previous cell on the path."""
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
# Maze inspection predicates.
@classmethod
def is_facing_wall(cls) -> bool:
"""True if there is a wall in the facing direction, False otherwise."""
return MRP._M[MRP._r + MRP._deltaR[MRP._d]
][MRP._c + MRP._deltaC[MRP._d]] == MRP._WALL
@classmethod
def is_at_cheese(cls) -> bool:
"""True if the present rat location is colocated with the cheese."""
return (MRP._r == MRP._hi) and (MRP._c == MRP._hi)
@classmethod
def is_about_to_repeat(cls) -> bool:
"""Rat is in the upper-left cell facing left, and with next turn will re-enter the initial state."""
return (MRP._r == MRP._lo) and (MRP._c == MRP._lo) and (MRP._d==3)
@classmethod
def is_facing_unvisited(cls) -> bool:
"""The cell the rat is facing is not on the current path. Precondition: no intervening wall."""
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 an 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")
# 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 a neighboring cell.” """
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 a cell into which an arrow was tossed.” """
return MRP._M[MRP._r][MRP._c] == MRP._neighbor_number
@classmethod
def restore_direction(cls) -> None:
""" “Align rat's direction with the orientation of a tossed arrow.” """
MRP._d = MRP._neighbor_direction
# Validity checking, testing, and debugging.
@classmethod
def _is_valid_path(cls, r: int, c: int) -> bool:
"""Return False iff the 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_valid(cls) -> bool:
"""Return False on evidence that a representation invariant is violated."""
# return MRP._is_valid_path(MRP._r, MRP._c) and MRP._is_valid_rat()
@classmethod
def _is_valid_rat(cls) -> bool:
"""Return False iff rat’s representation invariant is violated."""
if (MRP._r < 0) or (MRP._r > MRP._hi) or (
(MRP._c < 0) or (MRP._c > MRP._hi)): return False
elif (MRP._d < 0) or (MRP._d > 3): return False
elif MRP._M[MRP._r][MRP._c] != MRP._move: return False
else: return True
@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 print_state(cls, s: str) -> None:
"""Print state variables for debugging purposes."""
print(s, MRP._r, MRP._c, MRP._d, MRP._move)