-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmaze.py
143 lines (119 loc) · 5.67 KB
/
maze.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
# maze.py
# ---------------
# Licensing Information: You are free to use or extend this projects for
# educational purposes provided that (1) you do not distribute or publish
# solutions, (2) you retain this notice, and (3) you provide clear
# attribution to the University of Illinois at Urbana-Champaign
#
# Created by Kelvin Ma ([email protected]) on 01/24/2021,
# Inspired by previous work by Michael Abir ([email protected]) and Rahul Kunji ([email protected])
from collections import namedtuple
from itertools import chain
class MazeError(Exception):
pass
class maze:
"""
creates a maze instance given a `path` to a file containing characters in `legend`.
"""
def __init__(self, path, legend = {'wall': '%', 'start': 'P', 'waypoint': '.'}):
for key in 'wall', 'start', 'waypoint':
if key not in legend:
raise ValueError('undefined legend key \'{0}\''.format(key))
self.legend = namedtuple('legend', ('wall', 'start', 'waypoint'))(
legend['wall'],
legend['start'],
legend['waypoint'])
with open(path) as file:
lines = tuple(line.strip() for line in file.readlines() if line)
n = len(lines)
m = min(map(len, lines))
if any(len(line) != m for line in lines):
raise MazeError('(maze \'{0}\'): all maze rows must be the same length (shortest row has length {1})'.format(path, m))
self._storage = lines
self.size = namedtuple('size', ('x', 'y'))(m, n)
if any(self[x] != self.legend.wall for x in chain(
(( 0, j) for j in range(m)),
((n - 1, j) for j in range(m)),
((i, 0) for i in range(n)),
((i, m - 1) for i in range(n)))):
raise MazeError('(maze \'{0}\'): maze borders may only contain `wall` cells (\'{1}\')'.format(path, self.legend.wall))
if n < 3 or m < 3:
raise MazeError('(maze \'{0}\'): maze dimensions ({1}, {2}) must be at least (3, 3)'.format(path, n, m))
self.start = None
for x in ((i, j)
for i in range(self.size.y)
for j in range(self.size.x) if self[i, j] == self.legend.start):
if self.start is None:
self.start = x
elif type(self.start) is int:
self.start += 1
else:
self.start = 2
if type(self.start) is int or self.start is None:
raise MazeError('(maze \'{0}\'): maze must contain exactly one `start` cell (\'{1}\') (found {2})'.format(
path, self.legend.start, 0 if self.start is None else self.start))
self.waypoints = tuple((i, j)
for i in range(self.size.y)
for j in range(self.size.x) if self[i, j] == self.legend.waypoint)
# there is no point in making this private since anyone trying to cheat
# could simply overwrite the underscored variable
self.states_explored = 0
def __getitem__(self, index):
i, j = index
if 0 <= i < self.size.y and 0 <= j < self.size.x:
return self._storage[i][j]
else:
raise IndexError('cell index ({0}, {1}) out of range'.format(i, j))
def indices(self):
return ((i, j)
for i in range(self.size.y)
for j in range(self.size.x))
# Check if the agent can move into a specific row and column
def navigable(self, i, j):
try:
return self[i, j] != self.legend.wall
except IndexError:
return False
# Returns list of neighboing squares that can be moved to from the given row,col
def neighbors(self, i, j):
self.states_explored += 1
return tuple(x for x in (
(i + 1, j),
(i - 1, j),
(i, j + 1),
(i, j - 1))
if self.navigable( * x ))
def validate_path(self, path):
# validate type and shape
if len(path) == 0:
return 'path must not be empty'
if not all(len(vertex) == 2 for vertex in path):
return 'each path element must be a two-element sequence'
# normalize path in case student used an element type that is not `tuple`
path = tuple(map(tuple, path))
# check if path is contiguous
for i, (a, b) in enumerate(zip(path, path[1:])):
if sum(abs(b - a) for a, b in zip(a, b)) != 1:
return 'path vertex {1} ({4}, {5}) must be exactly one move away from path vertex {0} ({2}, {3})'.format(
i, i + 1, * a , * b )
# check if path is navigable
for i, x in enumerate(path):
if not self.navigable( * x ):
return 'path vertex {0} ({1}, {2}) is not a navigable maze cell'.format(i, * x )
# check if path ends at a waypoint
for waypoint in self.waypoints:
if path[-1] == waypoint:
break
else:
return 'last path vertex {0} ({1}, {2}) must be a waypoint'.format(len(path) - 1, * path[-1] )
# check for unnecessary path segments
indices = {}
for i, x in enumerate(path):
if x in indices:
if all(self[x] != self.legend.waypoint for x in path[indices[x] : i]):
return 'path segment [{0} : {1}] contains no waypoints'.format(indices[x], i)
indices[x] = i
# check if path contains all waypoints
for i, x in enumerate(self.waypoints):
if x not in indices:
return 'waypoint {0} ({1}, {2}) was never visited'.format(i, * x )