-
Notifications
You must be signed in to change notification settings - Fork 0
/
parking_lot_problem_statement.py
274 lines (225 loc) · 8.93 KB
/
parking_lot_problem_statement.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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
"""
UNIT 4: Search
Your task is to maneuver a car in a crowded parking lot. This is a kind of
puzzle, which can be represented with a diagram like this:
| | | | | | | |
| G G . . . Y |
| P . . B . Y |
| P * * B . Y @
| P . . B . . |
| O . . . A A |
| O . S S S . |
| | | | | | | |
A '|' represents a wall around the parking lot, a '.' represents an empty square,
and a letter or asterisk represents a car. '@' marks a goal square.
Note that there are long (3 spot) and short (2 spot) cars.
Your task is to get the car that is represented by '**' out of the parking lot
(on to a goal square). Cars can move only in the direction they are pointing.
In this diagram, the cars GG, AA, SSS, and ** are pointed right-left,
so they can move any number of squares right or left, as long as they don't
bump into another car or wall. In this diagram, GG could move 1, 2, or 3 spots
to the right; AA could move 1, 2, or 3 spots to the left, and ** cannot move
at all. In the up-down direction, BBB can move one up or down, YYY can move
one down, and PPP and OO cannot move.
You should solve this puzzle (and ones like it) using search. You will be
given an initial state like this diagram and a goal location for the ** car;
in this puzzle the goal is the '@' empty spot in the wall on the right side.
You should return a path -- an alternation of states and actions -- that leads
to a state where the car overlaps the goal.
An action is a move by one car in one direction (by any number of spaces).
For example, here is a successor state where the AA car moves 3 to the left:
| | | | | | | |
| G G . . . Y |
| P . . B . Y |
| P * * B . Y @
| P . . B . . |
| O A A . . . |
| O . . . . . |
| | | | | | | |
And then after BBB moves 2 down and YYY moves 3 down, we can solve the puzzle
by moving ** 4 spaces to the right:
| | | | | | | |
| G G . . . . |
| P . . . . . |
| P . . . . * *
| P . . B . Y |
| O A A B . Y |
| O . . B . Y |
| | | | | | | |
You will write the function
solve_parking_puzzle(start, N=N)
where 'start' is the initial state of the puzzle and 'N' is the length of a side
of the square that encloses the pieces (including the walls, so N=8 here).
We will represent the grid with integer indexes. Here we see the
non-wall index numbers (with the goal at index 31):
| | | | | | | |
| 9 10 11 12 13 14 |
| 17 18 19 20 21 22 |
| 25 26 27 28 29 30 31
| 33 34 35 36 37 38 |
| 41 42 43 44 45 46 |
| 49 50 51 52 53 54 |
| | | | | | | |
The wall in the upper left has index 0 and the one in the lower right has 63.
We represent a state of the problem with one big tuple of (object, locations)
pairs, where each pair is a tuple and the locations are a tuple. Here is the
initial state for the problem above in this format:
"""
puzzle0 = (
('@', (31,)),
('*', (26, 27)),
('G', (9, 10)),
('Y', (14, 22, 30)),
('P', (17, 25, 33)),
('O', (41, 49)),
('B', (20, 28, 36)),
('A', (45, 46)),
('|', (0, 1, 2, 3, 4, 5, 6, 7, 8, 15, 16, 23, 24, 32, 39,
40, 47, 48, 55, 56, 57, 58, 59, 60, 61, 62, 63)))
# A solution to this puzzle is as follows:
# path = solve_parking_puzzle(puzzle1, N=8)
# path_actions(path) == [('A', -3), ('B', 16), ('Y', 24), ('*', 4)]
# That is, move car 'A' 3 spaces left, then 'B' 2 down, then 'Y' 3 down,
# and finally '*' moves 4 spaces right to the goal.
# Your task is to define solve_parking_puzzle:
N = 8
def solve_parking_puzzle(start, N=N):
"""Solve the puzzle described by the starting position (a tuple
of (object, locations) pairs). Return a path of [state, action, ...]
alternating items; an action is a pair (object, distance_moved),
such as ('B', 16) to move 'B' two squares down on the N=8 grid."""
pass
# But it would also be nice to have a simpler format to describe puzzles,
# and a way to visualize states.
# You will do that by defining the following two functions:
def locs(start, n, incr=1):
"Return a tuple of n locations, starting at start and incrementing by incr."
pass
def grid(cars, N=N):
"""Return a tuple of (object, locations) pairs -- the format expected for
this puzzle. This function includes a wall pair, ('|', (0, ...)) to
indicate there are walls all around the NxN grid, except at the goal
location, which is the middle of the right-hand wall; there is a goal
pair, like ('@', (31,)), to indicate this. The variable 'cars' is a
tuple of pairs like ('*', (26, 27)). The return result is a big tuple
of the 'cars' pairs along with the walls and goal pairs."""
pass
def show(state, N=N):
"Print a representation of a state as an NxN grid."
# Initialize and fill in the board.
board = ['.'] * N**2
for (c, squares) in state:
for s in squares:
board[s] = c
# Now print it out
for i,s in enumerate(board):
print s,
if i % N == N - 1: print
# Here we see the grid and locs functions in use:
puzzle1 = grid((
('*', locs(26, 2)),
('G', locs(9, 2)),
('Y', locs(14, 3, N)), # N used for cars oriented up-down; it will be passed in for incr in locs()
('P', locs(17, 3, N)),
('O', locs(41, 2, N)),
('B', locs(20, 3, N)),
('A', locs(45, 2))))
puzzle2 = grid((
('*', locs(26, 2)),
('B', locs(20, 3, N)),
('P', locs(33, 3)),
('O', locs(41, 2, N)),
('Y', locs(51, 3))))
puzzle3 = grid((
('*', locs(25, 2)),
('B', locs(19, 3, N)),
('P', locs(36, 3)),
('O', locs(45, 2, N)),
('Y', locs(49, 3))))
# Here are the shortest_path_search and path_actions functions from the unit.
# You may use these if you want, but you don't have to.
def shortest_path_search(start, successors, is_goal):
"""Find the shortest path from start state to a state
such that is_goal(state) is true."""
if is_goal(start):
return [start]
explored = set() # set of states we have visited
frontier = [ [start] ] # ordered list of paths we have blazed
while frontier:
path = frontier.pop(0)
s = path[-1]
for (state, action) in sorted(successors(s).items(), key=lambda t: abs(t[1][1])):
state = tuple(sorted(state, key=lambda t: t[0]))
if state not in explored:
explored.add(state)
path2 = path + [action, state]
if is_goal(state):
return path2
else:
frontier.append(path2)
return []
def path_actions(path):
"Return a list of actions in this path."
return path[1::2]
def path_states(path): return path[0::2]
### TO DO
# create successors function (state1 -> {state2: action}) to be used by shortest_path_search
# successors fn will return {state: action} where action is the action taken to get to state
# states will be provided by grid()
# action is a pair (object, distance_moved), such as ('B', 16) to move 'B' two squares down on the N=8 grid
# create is_goal function for shortest_path_search to tell whether * is in @
# problem: (initial state, goal location for **) -> shortest solution path (state -> action -> state...)
# ** must overlap @ for goal to be achieved
# An action is a move by one car in one direction (by any number of spaces)
# You will write the function solve_parking_puzzle(start, N=N)
# where 'start' is the initial state of the puzzle and 'N' is the length of a side
# of the square that encloses the pieces (including the walls, so N=8 here)
# The wall in the upper left has index 0 and the one in the lower right has 63.
# We represent a state of the problem with one big tuple of (object, locations)
# pairs, where each pair is a tuple and the locations are a tuple. Here is the
# initial state for the problem above in this format:
# puzzle1 = (
# ('@', (31,)),
# ('*', (26, 27)),
# ('G', (9, 10)),
# ('Y', (14, 22, 30)),
# ('P', (17, 25, 33)),
# ('O', (41, 49)),
# ('B', (20, 28, 36)),
# ('A', (45, 46)),
# ('|', (0, 1, 2, 3, 4, 5, 6, 7, 8, 15, 16, 23, 24, 32, 39,
# 40, 47, 48, 55, 56, 57, 58, 59, 60, 61, 62, 63)))
# concepts:
# directions
# up-down
# left-right
# moving one, two, three, or more spaces
# path_actions
# spaces
# cars
# empty
# walls
# ** will always be in the same column or row of @ (depending
# on whether ** is oriented up-down or left-right)
# A solution to this puzzle is as follows:
# puzzle4 = (
# ('@', (24,)),
# ('*', (26, 27)),
# ('G', (9, 10)),
# ('Y', (14, 22, 30)),
# ('P', (17, 25)),
# ('O', (41, 49)),
# ('B', (20, 28, 36)),
# ('A', (45, 46)),
# ('|', (0, 1, 2, 3, 4, 5, 6, 7, 8, 15, 16, 23, 31, 32, 39,
# 40, 47, 48, 55, 56, 57, 58, 59, 60, 61, 62, 63)))
# def c(x): print x; return x
# path = solve_parking_puzzle(puzzle4, N=8)
# #print path_actions(path) == [('A', -3), ('B', 16), ('Y', 24), ('*', 4)]
# print path_actions(path)
# for i,s in enumerate(path_states(path)):
# print
# print 'State {}'.format(i)
# show(s)
# That is, move car 'A' 3 spaces left, then 'B' 2 down, then 'Y' 3 down,
# and finally '*' moves 4 spaces right to the goal.