forked from dwave-examples/maze
-
Notifications
You must be signed in to change notification settings - Fork 0
/
test_maze.py
361 lines (294 loc) · 13.5 KB
/
test_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
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
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
# Copyright 2019 D-Wave Systems Inc.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
import itertools
import re
import sys
import unittest
from dimod import BinaryQuadraticModel
if sys.version_info >= (3,):
from unittest.mock import patch
from io import StringIO
else:
from mock import patch
from StringIO import StringIO
from maze import Maze, get_label, get_maze_bqm
from neal import SimulatedAnnealingSampler
def fill_with_zeros(solution_dict, n_rows, n_cols, ignore_list=None):
keys = set(itertools.chain(solution_dict.keys(), ignore_list or []))
# Setting west direction to zero
for i in range(n_rows):
for j in range(n_cols + 1):
west = get_label(i, j, 'w')
if west not in keys:
solution_dict[west] = 0
# Setting north direction to zero
for i in range(n_rows + 1):
for j in range(n_cols):
north = get_label(i, j, 'n')
if north not in keys:
solution_dict[north] = 0
def get_energy(solution_dict, bqm):
min_energy = float('inf')
aux_variables = [v for v in bqm.variables if re.match(r'aux\d+$', v)]
# Try all possible values of auxiliary variables
for aux_values in itertools.product([0, 1], repeat=len(aux_variables)):
for variable, value in zip(aux_variables, aux_values):
solution_dict[variable] = value
temp_energy = bqm.energy(solution_dict)
if temp_energy < min_energy:
min_energy = temp_energy
return min_energy
class TestMazeSolverConstraints(unittest.TestCase):
def test_valid_move_constraint(self):
n_rows = 2
n_cols = 3
start = '0,1n'
end = '0,3w'
maze = Maze(n_rows, n_cols, start, end, ['1,2n', '1,2w'])
maze._apply_valid_move_constraint()
# No path at all, not even at start or end locations
no_path_solution = {}
fill_with_zeros(no_path_solution, n_rows, n_cols)
self.assertTrue(maze.csp.check(no_path_solution))
# Broken path
broken_path_solution = {'1,0n': 1, '1,1w': 1}
fill_with_zeros(broken_path_solution, n_rows, n_cols)
self.assertFalse(maze.csp.check(broken_path_solution))
# Revisiting a tile 0,1
revisit_tile_solution = {'0,1w': 1, '1,0n': 1, '1,1w': 1, '1,1n': 1, '0,2w': 1, start: 1, end: 1}
fill_with_zeros(revisit_tile_solution, n_rows, n_cols)
self.assertFalse(maze.csp.check(revisit_tile_solution))
# Good path
good_path_solution = {'0,2w': 1, start: 1, end: 1}
fill_with_zeros(good_path_solution, n_rows, n_cols)
self.assertTrue(good_path_solution)
def test_set_start_and_end(self):
# Create maze
n_rows = 5
n_cols = 3
start = '4,3w'
end = '0,2n'
maze = Maze(n_rows, n_cols, start, end, [])
maze._apply_valid_move_constraint() # Apply constraint to populate csp variables
# Check to see that start and end are in csp.variables
self.assertTrue(start in maze.csp.variables)
self.assertTrue(end in maze.csp.variables)
# Check to see that start and end have been fixed
maze._set_start_and_end()
self.assertFalse(start in maze.csp.variables)
self.assertFalse(end in maze.csp.variables)
# Check that start and end are fixed to 1.
# If start and end were fixed to 0, valid_move_constraint would be satisfied with the no_path_solution.
no_path_solution = {}
fill_with_zeros(no_path_solution, n_rows, n_cols, [start, end])
self.assertFalse(maze.csp.check(no_path_solution))
def test_borders_constraint(self):
# Create maze
n_rows = 3
n_cols = 3
start = '0,1n'
end = '0,3w'
maze = Maze(n_rows, n_cols, start, end, ['1,1w', '2,1n'])
maze._apply_valid_move_constraint() # Apply constraint to populate csp variables
maze._set_start_and_end() # Start and end locations should not be considered as borders
# Grab border variables
borders = {get_label(i, 0, 'w') for i in range(n_rows)} # West border
borders.update({get_label(i, n_cols, 'w') for i in range(n_rows)}) # East border
borders.update({get_label(0, j, 'n') for j in range(n_cols)}) # North border
borders.update({get_label(n_rows, j, 'n') for j in range(n_cols)}) # South border
borders.remove(start)
borders.remove(end)
# Check to see that border appears as a variable in maze.csp
for border in borders:
self.assertTrue(border in maze.csp.variables)
# Fix borders
maze._set_borders()
# Check to see that borders are fixed; they would no longer appear as variables
for border in borders:
self.assertFalse(border in maze.csp.variables)
# Verify that borders are fixed to 0.
# If borders were fixed to 1, this good_path_solution would cause the valid_move_constraint to fail.
good_path_solution = {'0,2w': 1}
fill_with_zeros(good_path_solution, n_rows, n_cols, [start, end])
self.assertTrue(maze.csp.check(good_path_solution))
def test_inner_walls(self):
# Create maze
n_rows = 4
n_cols = 7
start = '2,0w'
end = '0,3n'
walls = ['2,3w', '2,4w', '2,5w']
maze = Maze(n_rows, n_cols, start, end, walls)
maze._apply_valid_move_constraint() # Apply constraint to populate csp variables
# Check to see that walls appear as variables in maze.csp
for wall in walls:
self.assertTrue(wall in maze.csp.variables)
# Fix wall values
maze._set_inner_walls()
# Check to see that walls are fixed; they would no longer appear as variables
for wall in walls:
self.assertFalse(wall in maze.csp.variables)
# Verify that walls are fixed to 0
# circle_solution surrounds the inner walls, if walls are fixed to 1, solution will fail valid_move_constraint.
# Since start and end locations have not been fixed, a circle is valid path
circle_solution = {'2,2n': 1, '3,2n': 1, '3,3w': 1, '3,4w': 1, '3,5w': 1, '3,5n': 1, '2,5n': 1, '1,5w': 1,
'1,4w': 1, '1,3w': 1}
fill_with_zeros(circle_solution, n_rows, n_cols) # No ignore_list because we didn't fix start and end
self.assertTrue(maze.csp.check(circle_solution))
class TestMazeSolverResponse(unittest.TestCase):
def compare(self, sample, expected):
"""Comparing response to expected results
"""
# Comparing variables found in sample and expected
expected_keys = set(expected.keys())
sample_keys = set(sample.keys())
common_keys = expected_keys & sample_keys
different_keys = expected_keys - sample_keys # expected_keys is a superset
# Check that common variables match
for key in common_keys:
if re.match(r'aux\d+$', key):
continue
self.assertAlmostEqual(sample[key], expected[key],
"Key {} does not match with expected value".format(key))
# Check that non-existent 'sample' variables are 0
for key in different_keys:
if re.match(r'aux\d+$', key):
continue
self.assertEqual(expected[key], 0,
"Key {} does not match with expected value".format(key))
def test_energy_level_one_optimal_path(self):
# Create maze
n_rows = 2
n_cols = 4
start = '1,4w'
end = '2,2n'
walls = []
maze = Maze(n_rows, n_cols, start, end, walls)
bqm = maze.get_bqm()
# Grab energy levels of different paths
shortest_path = {'1,3w': 1}
longer_path0 = {'1,2n': 1, '0,3w': 1, '1,3n': 1}
longer_path1 = {'1,2w': 1, '1,1n': 1, '0,2w': 1, '0,3w': 1, '1,3n': 1}
no_path = {}
fill_with_zeros(shortest_path, n_rows, n_cols, [start, end])
fill_with_zeros(longer_path0, n_rows, n_cols, [start, end])
fill_with_zeros(longer_path1, n_rows, n_cols, [start, end])
fill_with_zeros(no_path, n_rows, n_cols, [start, end])
energy_shortest_path = get_energy(shortest_path, bqm)
energy_longer_path0 = get_energy(longer_path0, bqm)
energy_longer_path1 = get_energy(longer_path1, bqm)
energy_no_path = get_energy(no_path, bqm)
# Compare energy levels
self.assertLess(energy_shortest_path, energy_longer_path0)
self.assertLess(energy_shortest_path, energy_longer_path1)
self.assertLess(energy_longer_path0, energy_longer_path1)
self.assertLess(energy_shortest_path, energy_no_path)
def test_energy_level_multiple_optimal_paths(self):
# Create maze
n_rows = 3
n_cols = 4
start = '0,0w'
end = '1,4w'
walls = ['1,1w']
maze = Maze(n_rows, n_cols, start, end, walls)
bqm = maze.get_bqm()
# Shortest paths through maze; should share same energy level
shortest_path0 = {'0,1w': 1, '1,1n': 1, '1,2w': 1, '1,3w': 1}
shortest_path1 = {'0,1w': 1, '0,2w': 1, '1,2n': 1, '1,3w': 1}
shortest_path2 = {'0,1w': 1, '0,2w': 1, '0,3w': 1, '1,3n': 1}
fill_with_zeros(shortest_path0, n_rows, n_cols, [start, end])
fill_with_zeros(shortest_path1, n_rows, n_cols, [start, end])
fill_with_zeros(shortest_path2, n_rows, n_cols, [start, end])
energy_shortest_path0 = get_energy(shortest_path0, bqm)
energy_shortest_path1 = get_energy(shortest_path1, bqm)
energy_shortest_path2 = get_energy(shortest_path2, bqm)
self.assertAlmostEqual(energy_shortest_path0, energy_shortest_path1)
self.assertAlmostEqual(energy_shortest_path0, energy_shortest_path2)
# Compare energy level of longer path with shortest path
longer_path = {'0,1w': 1, '1,1n': 1, '2,1n': 1, '2,2w': 1, '2,2n': 1, '1,3w': 1}
fill_with_zeros(longer_path, n_rows, n_cols, [start, end])
energy_longer_path = get_energy(longer_path, bqm)
self.assertGreater(energy_longer_path, energy_shortest_path0)
# Compare energy level of no path with shortest path
no_path = {}
fill_with_zeros(no_path, n_rows, n_cols, [start, end])
energy_no_path = get_energy(no_path, bqm)
self.assertGreater(energy_no_path, energy_shortest_path0)
def test_maze_heuristic_response(self):
"""Small and simple maze to verify that it is possible get a solution.
"""
# Create maze
n_rows = 3
n_cols = 3
start = '0,0n'
end = '3,2n'
walls = ['1,0n', '2,1n', '2,2n']
maze = Maze(n_rows, n_cols, start, end, walls)
bqm = maze.get_bqm()
# Sample and test that a response is given
sampler = SimulatedAnnealingSampler()
response = sampler.sample(bqm, num_reads=1000)
response_sample = next(response.samples())
self.assertGreaterEqual(len(response), 1)
# Test heuristic response
expected_solution = {'0,1w': 1, '1,1n': 1, '1,1w': 1, '2,0n': 1, '2,1w': 1, '2,2w': 1}
fill_with_zeros(expected_solution, n_rows, n_cols, [start, end])
self.compare(response_sample, expected_solution)
class TestGetMazeBqm(unittest.TestCase):
def test_bqm_return(self):
"""get_maze_bqm(..) is merely a wrapper. This test is to ensure that the wrapper works.
"""
# Create maze
n_rows = 2
n_cols = 2
start = '0,0n'
end = '1,0w'
walls = ['1,1n']
# Get bqm
bqm = get_maze_bqm(n_rows, n_cols, start, end, walls)
self.assertIsInstance(bqm, BinaryQuadraticModel)
class TestMazeVisualization(unittest.TestCase):
def test_maze_setup(self):
"""Test that the maze setup is visualized correctly
"""
m = Maze(3, 2, "2,0w", "0,1n", ["0,1w", "1,1w", "2,0n"])
expected_out = ("###|#\n"
"#.#.#\n"
"# #\n"
"#.#.#\n"
"## #\n"
"_. .#\n"
"#####\n")
# Replace sys.stdout with mock
with patch('sys.stdout', new_callable=StringIO) as mock_stdout:
m.visualize()
self.assertEqual(mock_stdout.getvalue(), expected_out)
def test_maze_solution(self):
"""Test that the maze path is visualized correctly
"""
m = Maze(3, 3, "2,0w", "0,3w", ["1,2n", "2,0n", "2,1n"])
path = ["2,1w", "2,2w", "2,2n", "1,2w", "1,1w", "1,0n", "0,1w", "0,2w"]
expected_out = ("#######\n"
"#._._._\n"
"#| ##\n"
"#._._.#\n"
"## # |#\n"
"_._._.#\n"
"#######\n")
# Replace sys.stdout with mock
with patch('sys.stdout', new_callable=StringIO) as mock_stdout:
m.visualize(path)
self.assertEqual(mock_stdout.getvalue(), expected_out)
if __name__ == "__main__":
unittest.main()