14 "execution_count": 18,
18 "def load_maze(fname='maze.txt'):\n",
19 " mazet = [l.strip() for l in open(fname)]\n",
21 " for y, row in enumerate(mazet):\n",
22 " for x, cell in enumerate(row):\n",
23 " maze[x, y] = cell\n",
29 "execution_count": 31,
33 "def maze_neighbours(field, here, mow_cost=None):\n",
35 " neighbours = [((x, y), 1)\n",
36 " for x in range(x0-1, x0+2)\n",
37 " for y in range(y0-1, y0+2)\n",
38 " if (x, y) in field\n",
39 " if x == x0 and y != y0 or x != x0 and y == y0\n",
40 " if field[x, y] == '.'\n",
42 " if mow_cost is not None:\n",
43 " neighbours += [((x, y), mow_cost)\n",
44 " for x in range(x0-1, x0+2)\n",
45 " for y in range(y0-1, y0+2)\n",
46 " if (x, y) in field\n",
47 " if x == x0 and y != y0 or x != x0 and y == y0\n",
48 " if field[x, y] == '#'\n",
55 "execution_count": 20,
59 "def path_end(path):\n",
62 "def extend_path(path, item):\n",
63 " return path + [item]"
68 "execution_count": 21,
72 "def show_path(maze, path, sparse=True):\n",
73 " w = max(x for x, _ in maze.keys())\n",
74 " h = max(y for _, y in maze.keys())\n",
75 " for y in range(h+1):\n",
77 " for x in range(w+1):\n",
78 " if (x, y) in path:\n",
79 " if maze[x, y] == '#':\n",
85 " if maze[x, y] == '.':\n",
88 " s += '.'# field[y][x]\n",
96 "execution_count": 22,
100 "def est_dist(here, there):\n",
101 " return abs(here[0] - there[0]) + abs(here[1] - there[1])"
106 "execution_count": 32,
110 "def bfs(maze, start, goal):\n",
111 " agenda = [extend_path([], start)]\n",
112 " while agenda and path_end(agenda[0]) != goal:\n",
113 " current = agenda[0]\n",
114 " here = path_end(current)\n",
115 " neighbours = maze_neighbours(maze, here)\n",
116 "# print(here, neighbours, len(current), len(agenda))\n",
117 " new_paths = [extend_path(current, n) for n, _ in neighbours if n not in current]\n",
118 " agenda = agenda[1:] + new_paths\n",
120 " return agenda[0]\n",
122 " return \"No route found\""
127 "execution_count": 33,
131 "def astar(maze, start, goal, mow_cost=None):\n",
134 " heappush(agenda, (est_dist(start, goal), 0, extend_path([], start)))\n",
135 " while agenda and path_end(agenda[0][2]) != goal:\n",
136 " _, cost, current = heappop(agenda)\n",
137 " here = path_end(current)\n",
138 " if here not in closed:\n",
139 "# print(here, len(current), len(agenda), len(closed))\n",
140 " closed.add(here)\n",
141 " neighbours = maze_neighbours(maze, here, mow_cost=mow_cost)\n",
142 " new_paths = [(cost + c + est_dist(n, goal), cost + c,\n",
143 " extend_path(current, n)) \n",
144 " for n, c in neighbours \n",
145 " if n not in closed]\n",
146 " for np in new_paths:\n",
147 " heappush(agenda, np)\n",
149 " return agenda[0]\n",
151 " return \"No route found\"\n",
157 "execution_count": 34,
161 "def bestfs(maze, start, goal, mow_cost=None):\n",
164 " heappush(agenda, (0, extend_path([], start)))\n",
165 " while agenda and path_end(agenda[0][1]) != goal:\n",
166 " cost, current = heappop(agenda)\n",
167 " here = path_end(current)\n",
168 " if here not in closed:\n",
169 "# print(here, len(current), len(agenda), len(closed))\n",
170 " closed.add(here)\n",
171 " neighbours = maze_neighbours(maze, here, mow_cost=mow_cost)\n",
172 " new_paths = [(cost + c,\n",
173 " extend_path(current, n)) \n",
174 " for n, c in neighbours \n",
175 " if n not in closed]\n",
176 " for np in new_paths:\n",
177 " heappush(agenda, np)\n",
179 " return agenda[0]\n",
181 " return \"No route found\"\n",
187 "execution_count": 35,
191 "maze = load_maze('../../data/08-maze.txt')\n",
193 "GOAL = (max(x for x, _ in maze.keys()), max(y for _, y in maze.keys()))"
198 "execution_count": 47,
203 "output_type": "stream",
205 "OOOO.. . . . .. .. . . . . . . . \n",
206 ". .OO. . ... . .. . .. . .... ..... . ..\n",
207 "....O. . . . ... ... ... .. .. .. ..... \n",
208 " . OOOOO. ..... . .... . .... .. . ... . \n",
209 " .. ..OOO. . . . . . .... ..... .. .\n",
210 " .... ....O . ..... .. . . . ... . . ..\n",
211 ".. . . O..... . . . . . .... .... ....... \n",
212 " .. . ....O . . . .. ... ... .. . .. .. . .. \n",
213 " .. . . . O.. . .. .... .. .. ... . . . . \n",
214 " ... ..OO. . . . . . ... .. . . .. .. .... \n",
215 "... .. ...O. . .. . . . .. . . . \n",
216 " .. . .O. . . . . ... . . .. . ... . ... .. \n",
217 "... ... OOO. .. ... . . .... . ..... ... \n",
218 ". . . .. ....O . . . ..... ... . . . .\n",
219 " . . ... O.... .. ...... .. . . . .. .. ... \n",
220 ". . . .. ....O. . . . .. . . . . . .\n",
221 " . . .. .O.. . .... . ....... .. .. .. . . \n",
222 "... .. . OO . .. . . . ... .... . .\n",
223 " . .. ....O... ... .. .... ... .. ...\n",
224 "...... . . ..O. . . . ..... .. . .. .... ... \n",
225 ". . . .. . .OO . . . ..... .. . . .\n",
226 " . .. .. .O. ...... ...... .... . ... \n",
227 ". . . ... O. .. . ... . . . .. . . ......\n",
228 ". . .. .. ...O.... . .. . .. . . .. . .. .. \n",
229 " . . .OOO. .. . . . . . .. .. ...\n",
230 ".. ... .. .O.... . .. .... . . ...... .... . \n",
231 " . . . .OO.. . .... . . . . . \n",
232 " . .. ... ..OO.. . .. .. . ....... . .. .....\n",
233 " . . . . ...O .. ... . .. .... ... \n",
234 " . .. . ..O.. . . ... .. .. . .........\n",
235 " ... ..OO . ........... .. .. .. .. \n",
236 ".. .. ....O... . . . ... . . . .... . \n",
237 " . ... . .O .. .. .. .. ... .. ... \n",
238 " . . .. ..OOO............ . .. . ...... ..\n",
239 " . . .O... . . .. ... .. .. ... . .\n",
240 " ... . ...O. . . .... .. . . ..... . ... \n",
241 " . . O . .. . . . . .... . . . ...\n",
242 " . .....O........ .... . ............ \n",
243 " . .... OOO . .. . ... ....... .. . . \n",
244 ".. . ..O....... . . . . . ... .... .... \n",
245 " .. .OO .. . .. . ......... ... . . \n",
246 " .. ...O... . OOOOO ..... . .. . . ... ..... \n",
247 " OOOOO ......O...O..OOOO .... . . \n",
248 "...O....... .. .O . OOOO..O.. .. . .......... ....\n",
249 " OOO. ..OOOOOO.... ... O.. .OOOOOOOOOO.. ... \n",
250 ".....O ..OO.. . . ..OOOOOO. . .. .OO.OOOO . \n",
251 " . ..O...OO.. . .... . . . .. .........OOO..O...\n",
252 " .OOOOO...... ...... .. . . . .O \n",
253 "... . ..... . .. ... . .. .... . . ... .. .O...\n",
254 " . . .. . . . . . . .OOOO\n"
263 "execution_count": 47,
265 "output_type": "execute_result"
269 "fp = bfs(maze, START, GOAL)\n",
270 "show_path(maze, fp, sparse=True)\n",
276 "execution_count": 37,
281 "output_type": "stream",
283 "OOOO.. . . . .. .. . . . . . . . \n",
284 ". .OO. . ... . .. . .. . .... ..... . ..\n",
285 "....O. . . . ... ... ... .. .. .. ..... \n",
286 " . OOOOO. ..... . .... . .... .. . ... . \n",
287 " .. ..OOO. . . . . . .... ..... .. .\n",
288 " .... ....O . ..... .. . . . ... . . ..\n",
289 ".. . . O..... . . . . . .... .... ....... \n",
290 " .. . ....O . . . .. ... ... .. . .. .. . .. \n",
291 " .. . . . O.. . .. .... .. .. ... . . . . \n",
292 " ... ..OO. . . . . . ... .. . . .. .. .... \n",
293 "... .. ...O. . .. . . . .. . . . \n",
294 " .. . .O. . . . . ... . . .. . ... . ... .. \n",
295 "... ... OOO. .. ... . . .... . ..... ... \n",
296 ". . . .. ....O . . . ..... ... . . . .\n",
297 " . . ... O.... .. ...... .. . . . .. .. ... \n",
298 ". . . .. ....O. . . . .. . . . . . .\n",
299 " . . .. .O.. . .... . ....... .. .. .. . . \n",
300 "... .. . OO . .. . . . ... .... . .\n",
301 " . .. ....O... ... .. .... ... .. ...\n",
302 "...... . . ..O. . . . ..... .. . .. .... ... \n",
303 ". . . .. . . OO . . . ..... .. . . .\n",
304 " . .. .. . .O...... ...... .... . ... \n",
305 ". . . ... .O .. . ... . . . .. . . ......\n",
306 ". . .. .. ... .*.. . .. . .. . . .. . .. .. \n",
307 " . . . .OO.. . . . . . .. .. ...\n",
308 ".. ... .. . ....O. .. .... . . ...... .... . \n",
309 " . . . . .. O. .... . . . . . \n",
310 " . .. ... .. ..OO . .. .. . ....... . .. .....\n",
311 " . . . . ... ..O... . .. .... ... \n",
312 " . .. . .. .. OOOO . . ... .. .. . .........\n",
313 " ... .. . ...*....... .. .. .. .. \n",
314 ".. .. .... ... . .OOOO . ... . . . .... . \n",
315 " . ... . . ..O.. .. .. ... .. ... \n",
316 " . . .. .. ..........**O . .. . ...... ..\n",
317 " . . . ... . . ..O... .. .. ... . .\n",
318 " ... . ... . . . .... .. O. . ..... . ... \n",
319 " . . . ..O. . . . .... . . . ...\n",
320 " . ..... ........ .... OOOOOOOOOO*O............ \n",
321 " . .... . .. . ... ....... ..OO. . \n",
322 ".. . .. ....... . . . . . ...OOO.... .... \n",
323 " .. . .. . .. . ......... ...O . . \n",
324 " .. ... ... . ..... . .. . .O... ..... \n",
325 " ...... ... .. .... . OOOOO . \n",
326 "... ....... .. . . .. .. .. . ........*. ....\n",
327 " . .. .... ... .. . ..O... \n",
328 "..... .. .. . . .. . . .. . .OOOO . \n",
329 " . .. ... .. . .... . . . .. ......... ..O...\n",
330 " . ...... ...... .. . . . .O \n",
331 "... . ..... . .. ... . .. .... . . ... .. .O...\n",
332 " . . .. . . . . . . .OOOO\n"
341 "execution_count": 37,
343 "output_type": "execute_result"
347 "h, c, ap = astar(maze, START, GOAL, mow_cost=3)\n",
348 "show_path(maze, ap, sparse=True)\n",
354 "execution_count": 38,
359 "output_type": "stream",
361 "O .. . . . .. .. . . . . . . . \n",
362 "* . . . ... . .. . .. . .... ..... . ..\n",
363 "*... . . . . ... ... ... .. .. .. ..... \n",
364 "O. . ..... . .... . .... .. . ... . \n",
365 "O .. .. . . . . . . .... ..... .. .\n",
366 "O.... .... . ..... .. . . . ... . . ..\n",
367 "*. . . ..... . . . . . .... .... ....... \n",
368 "O.. . .... . . . .. ... ... .. . .. .. . .. \n",
369 "O.. . . . .. . .. .... .. .. ... . . . . \n",
370 "O ... .. . . . . . . ... .. . . .. .. .... \n",
371 "*.. .. ... . . .. . . . .. . . . \n",
372 "O .. . . . . . . . ... . . .. . ... . ... .. \n",
373 "*.. ... . .. ... . . .... . ..... ... \n",
374 "* . . .. .... . . . ..... ... . . . .\n",
375 "O . . ... .... .. ...... .. . . . .. .. ... \n",
376 "* . . .. .... . . . . .. . . . . . .\n",
377 "O . . .. . .. . .... . ....... .. .. .. . . \n",
378 "*.. .. . . .. . . . ... .... . .\n",
379 "O . .. .... ... ... .. .... ... .. ...\n",
380 "*..... . . .. . . . . ..... .. . .. .... ... \n",
381 "* . . .. . . . . . ..... .. . . .\n",
382 "O . .. .. . . ...... ...... .... . ... \n",
383 "* . . ... . .. . ... . . . .. . . ......\n",
384 "* . .. .. ... .... . .. . .. . . .. . .. .. \n",
385 "O . . . . .. . . . . . .. .. ...\n",
386 "*. ... .. . .... . .. .... . . ...... .... . \n",
387 "O. . . . .. . .... . . . . . \n",
388 "O. .. ... .. .. . .. .. . ....... . .. .....\n",
389 "O. . . . ... .. ... . .. .... ... \n",
390 "O. .. . .. .. . . ... .. .. . .........\n",
391 "O ... .. . ........... .. .. .. .. \n",
392 "*. .. .... ... . . . ... . . . .... . \n",
393 "O. ... . . .. .. .. .. ... .. ... \n",
394 "O. . .. .. ............ . .. . ...... ..\n",
395 "O . . . ... . . .. ... .. .. ... . .\n",
396 "O... . ... . . . .... .. . . ..... . ... \n",
397 "O. . . .. . . . . .... . . . ...\n",
398 "O . ..... ........ .... . ............ \n",
399 "O. .... . .. . ... ....... .. . . \n",
400 "*. . .. ....... . . . . . ... .... .... \n",
401 "O.. . .. . .. . ......... ... . . \n",
402 "O.. ... ... . ..... . .. . . ... ..... \n",
403 "O ...... ... .. .... . . \n",
404 "*.. ....... .. . . .. .. .. . .......... ....\n",
405 "O . .. .... ... .. . .. ... \n",
406 "*.... .. .. . . .. . . .. . . . \n",
407 "O. .. ... .. . .... . . . .. ......... .. ...\n",
408 "O . ...... ...... .. . . . . \n",
409 "*.. . ..... . .. ... . .. .... . . ... .. . ...\n",
410 "OOOOOOOOOOOOOOO*OOOOO*O**OO*OOOO*O*O*OOO*OO*O*OOOO\n"
419 "execution_count": 38,
421 "output_type": "execute_result"
425 "h, c, ap = astar(maze, START, GOAL, mow_cost=1)\n",
426 "show_path(maze, ap, sparse=True)\n",
432 "execution_count": 48,
437 "output_type": "stream",
439 "OOOO.. . . . .. .. . . . . . . . \n",
440 ". .OO. . ... . .. . .. . .... ..... . ..\n",
441 "....O. . . . ... ... ... .. .. .. ..... \n",
442 " . OOOOO. ..... . .... . .... .. . ... . \n",
443 " .. ..OOO. . . . . . .... ..... .. .\n",
444 " .... ....O . ..... .. . . . ... . . ..\n",
445 ".. . . O..... . . . . . .... .... ....... \n",
446 " .. . ....O . . . .. ... ... .. . .. .. . .. \n",
447 " .. . . . O.. . .. .... .. .. ... . . . . \n",
448 " ... ..OO. . . . . . ... .. . . .. .. .... \n",
449 "... .. ...O. . .. . . . .. . . . \n",
450 " .. . .O. . . . . ... . . .. . ... . ... .. \n",
451 "... ... OOO. .. ... . . .... . ..... ... \n",
452 ". . . .. ....O . . . ..... ... . . . .\n",
453 " . . ... O.... .. ...... .. . . . .. .. ... \n",
454 ". . . .. ....O. . . . .. . . . . . .\n",
455 " . . .. .O.. . .... . ....... .. .. .. . . \n",
456 "... .. . OO . .. . . . ... .... . .\n",
457 " . .. ....O... ... .. .... ... .. ...\n",
458 "...... . . ..O. . . . ..... .. . .. .... ... \n",
459 ". . . .. . .OO . . . ..... .. . . .\n",
460 " . .. .. .O. ...... ...... .... . ... \n",
461 ". . . ... O. .. . ... . . . .. . . ......\n",
462 ". . .. .. ...O.... . .. . .. . . .. . .. .. \n",
463 " . . .OOO. .. . . . . . .. .. ...\n",
464 ".. ... .. .O.... . .. .... . . ...... .... . \n",
465 " . . . .OO.. . .... . . . . . \n",
466 " . .. ... ..OO.. . .. .. . ....... . .. .....\n",
467 " . . . . ...O .. ... . .. .... ... \n",
468 " . .. . ..O.. . . ... .. .. . .........\n",
469 " ... ..OO . ........... .. .. .. .. \n",
470 ".. .. ....O... . . . ... . . . .... . \n",
471 " . ... . .O .. .. .. .. ... .. ... \n",
472 " . . .. ..OOO............ . .. . ...... ..\n",
473 " . . .O... . . .. ... .. .. ... . .\n",
474 " ... . ...O. . . .... .. . . ..... . ... \n",
475 " . . O . .. . . . . .... . . . ...\n",
476 " . .....O........ .... . ............ \n",
477 " . .... OOO . .. . ... ....... .. . . \n",
478 ".. . ..O....... . . . . . ... .... .... \n",
479 " .. .OO .. . .. . ......... ... . . \n",
480 " .. ...O... . OOOOO ..... . .. . . ... ..... \n",
481 " OOOOO ......O...O..OOOO .... . . \n",
482 "...O....... .. .O . OOOO..O.. .. . .......... ....\n",
483 " OOO. ..OOOOOO.... ... O.. .OOOOOOOOOO.. ... \n",
484 ".....O ..OO.. . . ..OOOOOO. . .. .OO.OOOO . \n",
485 " . ..O...OO.. . .... . . . .. .........OOO..O...\n",
486 " .OOOOO...... ...... .. . . . .O \n",
487 "... . ..... . .. ... . .. .... . . ... .. .O...\n",
488 " . . .. . . . . . . .OOOO\n"
497 "execution_count": 48,
499 "output_type": "execute_result"
503 "h, c, ap = astar(maze, START, GOAL)\n",
504 "show_path(maze, ap)\n",
510 "execution_count": 49,
515 "output_type": "stream",
517 "OOOO.. . . . .. .. . . . . . . . \n",
518 ". .OO. . ... . .. . .. . .... ..... . ..\n",
519 "....O. . . . ... ... ... .. .. .. ..... \n",
520 " . OOOOO. ..... . .... . .... .. . ... . \n",
521 " .. ..OOO. . . . . . .... ..... .. .\n",
522 " .... ....O . ..... .. . . . ... . . ..\n",
523 ".. . . O..... . . . . . .... .... ....... \n",
524 " .. . ....O . . . .. ... ... .. . .. .. . .. \n",
525 " .. . . . O.. . .. .... .. .. ... . . . . \n",
526 " ... ..OO. . . . . . ... .. . . .. .. .... \n",
527 "... .. ...O. . .. . . . .. . . . \n",
528 " .. . .O. . . . . ... . . .. . ... . ... .. \n",
529 "... ... OOO. .. ... . . .... . ..... ... \n",
530 ". . . .. ....O . . . ..... ... . . . .\n",
531 " . . ... O.... .. ...... .. . . . .. .. ... \n",
532 ". . . .. ....O. . . . .. . . . . . .\n",
533 " . . .. .O.. . .... . ....... .. .. .. . . \n",
534 "... .. . OO . .. . . . ... .... . .\n",
535 " . .. ....O... ... .. .... ... .. ...\n",
536 "...... . . ..O. . . . ..... .. . .. .... ... \n",
537 ". . . .. . . OO . . . ..... .. . . .\n",
538 " . .. .. . .O...... ...... .... . ... \n",
539 ". . . ... .O .. . ... . . . .. . . ......\n",
540 ". . .. .. ... .*.. . .. . .. . . .. . .. .. \n",
541 " . . . .OO.. . . . . . .. .. ...\n",
542 ".. ... .. . ....O. .. .... . . ...... .... . \n",
543 " . . . . .. O. .... . . . . . \n",
544 " . .. ... .. ..OO . .. .. . ....... . .. .....\n",
545 " . . . . ... ..O... . .. .... ... \n",
546 " . .. . .. .. OOOO . . ... .. .. . .........\n",
547 " ... .. . ...*....... .. .. .. .. \n",
548 ".. .. .... ... . .OOOO . ... . . . .... . \n",
549 " . ... . . ..O.. .. .. ... .. ... \n",
550 " . . .. .. ..........**O . .. . ...... ..\n",
551 " . . . ... . . ..O... .. .. ... . .\n",
552 " ... . ... . . . .... .. O. . ..... . ... \n",
553 " . . . ..O. . . . .... . . . ...\n",
554 " . ..... ........ .... OOOOOOOOOO*O............ \n",
555 " . .... . .. . ... ....... ..OO. . \n",
556 ".. . .. ....... . . . . . ...OOO.... .... \n",
557 " .. . .. . .. . ......... ...O . . \n",
558 " .. ... ... . ..... . .. . .O... ..... \n",
559 " ...... ... .. .... . OOOOO . \n",
560 "... ....... .. . . .. .. .. . ........*. ....\n",
561 " . .. .... ... .. . ..O... \n",
562 "..... .. .. . . .. . . .. . .OOOO . \n",
563 " . .. ... .. . .... . . . .. ......... ..O...\n",
564 " . ...... ...... .. . . . .O \n",
565 "... . ..... . .. ... . .. .... . . ... .. .O...\n",
566 " . . .. . . . . . . .OOOO\n"
575 "execution_count": 49,
577 "output_type": "execute_result"
581 "c, bp = bestfs(maze, START, GOAL, mow_cost=3)\n",
582 "show_path(maze, bp)\n",
588 "execution_count": 50,
593 "output_type": "stream",
595 "OOOO.. . . . .. .. . . . . . . . \n",
596 ". .OO. . ... . .. . .. . .... ..... . ..\n",
597 "....O. . . . ... ... ... .. .. .. ..... \n",
598 " . OOOOO. ..... . .... . .... .. . ... . \n",
599 " .. ..OOO. . . . . . .... ..... .. .\n",
600 " .... ....O . ..... .. . . . ... . . ..\n",
601 ".. . . O..... . . . . . .... .... ....... \n",
602 " .. . ....O . . . .. ... ... .. . .. .. . .. \n",
603 " .. . . . O.. . .. .... .. .. ... . . . . \n",
604 " ... ..OO. . . . . . ... .. . . .. .. .... \n",
605 "... .. ...O. . .. . . . .. . . . \n",
606 " .. . .O. . . . . ... . . .. . ... . ... .. \n",
607 "... ... OOO. .. ... . . .... . ..... ... \n",
608 ". . . .. ....O . . . ..... ... . . . .\n",
609 " . . ... O.... .. ...... .. . . . .. .. ... \n",
610 ". . . .. ....O. . . . .. . . . . . .\n",
611 " . . .. .O.. . .... . ....... .. .. .. . . \n",
612 "... .. . OO . .. . . . ... .... . .\n",
613 " . .. ....O... ... .. .... ... .. ...\n",
614 "...... . . ..O. . . . ..... .. . .. .... ... \n",
615 ". . . .. . .OO . . . ..... .. . . .\n",
616 " . .. .. .O. ...... ...... .... . ... \n",
617 ". . . ... O. .. . ... . . . .. . . ......\n",
618 ". . .. .. ...O.... . .. . .. . . .. . .. .. \n",
619 " . . .OOO. .. . . . . . .. .. ...\n",
620 ".. ... .. .O.... . .. .... . . ...... .... . \n",
621 " . . . .OO.. . .... . . . . . \n",
622 " . .. ... ..OO.. . .. .. . ....... . .. .....\n",
623 " . . . . ...O .. ... . .. .... ... \n",
624 " . .. . ..O.. . . ... .. .. . .........\n",
625 " ... ..OO . ........... .. .. .. .. \n",
626 ".. .. ....O... . . . ... . . . .... . \n",
627 " . ... . .O .. .. .. .. ... .. ... \n",
628 " . . .. ..OOO............ . .. . ...... ..\n",
629 " . . .O... . . .. ... .. .. ... . .\n",
630 " ... . ...O. . . .... .. . . ..... . ... \n",
631 " . . O . .. . . . . .... . . . ...\n",
632 " . .....O........ .... . ............ \n",
633 " . .... OOO . .. . ... ....... .. . . \n",
634 ".. . ..O....... . . . . . ... .... .... \n",
635 " .. .OO .. . .. . ......... ... . . \n",
636 " .. ...O... . OOOOO ..... . .. . . ... ..... \n",
637 " OOOOO ......O...O..OOOO .... . . \n",
638 "...O....... .. .O . OOOO..O.. .. . .......... ....\n",
639 " OOO. ..OOOOOO.... ... O.. .OOOOOOOOOO.. ... \n",
640 ".....O ..OO.. . . ..OOOOOO. . .. .OO.OOOO . \n",
641 " . ..O...OO.. . .... . . . .. .........OOO..O...\n",
642 " .OOOOO...... ...... .. . . . .O \n",
643 "... . ..... . .. ... . .. .... . . ... .. .O...\n",
644 " . . .. . . . . . . .OOOO\n"
653 "execution_count": 50,
655 "output_type": "execute_result"
659 "c, bp = bestfs(maze, START, GOAL)\n",
660 "show_path(maze, bp)\n",
666 "execution_count": 51,
670 "def path_cost(maze, path, mow_cost=1):\n",
672 " for x, y in path:\n",
673 " if maze[x, y] == '#':\n",
674 " total += mow_cost\n",
682 "execution_count": 52,
691 "execution_count": 52,
693 "output_type": "execute_result"
697 "path_cost(maze, ap, 3), len(ap)"
702 "execution_count": 53,
711 "execution_count": 53,
713 "output_type": "execute_result"
717 "path_cost(maze, bp), len(bp)"
722 "execution_count": 59,
727 "output_type": "stream",
729 "9.54 ms ± 72.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
735 "bfs(maze, START, GOAL)"
740 "execution_count": 64,
745 "output_type": "stream",
747 "26.2 ms ± 249 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
753 "astar(maze, START, GOAL, mow_cost=3)"
758 "execution_count": 61,
763 "output_type": "stream",
765 "32.8 ms ± 494 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
771 "bestfs(maze, START, GOAL, mow_cost=3)"
776 "execution_count": 62,
781 "output_type": "stream",
783 "5.01 ms ± 30.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
789 "astar(maze, START, GOAL)"
794 "execution_count": 63,
799 "output_type": "stream",
801 "7.65 ms ± 56 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
807 "bestfs(maze, START, GOAL)"
812 "execution_count": null,
820 "display_name": "Python 3",
821 "language": "python",
829 "file_extension": ".py",
830 "mimetype": "text/x-python",
832 "nbconvert_exporter": "python",
833 "pygments_lexer": "ipython3",