{ "cells": [ { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [], "source": [ "from heapq import *" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [], "source": [ "def load_maze(fname='maze.txt'):\n", " mazet = [l.strip() for l in open(fname)]\n", " maze = {}\n", " for y, row in enumerate(mazet):\n", " for x, cell in enumerate(row):\n", " maze[x, y] = cell\n", " return maze" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [], "source": [ "def maze_neighbours(field, here, mow_cost=None):\n", " x0, y0 = here\n", " neighbours = [((x, y), 1)\n", " for x in range(x0-1, x0+2)\n", " for y in range(y0-1, y0+2)\n", " if (x, y) in field\n", " if x == x0 and y != y0 or x != x0 and y == y0\n", " if field[x, y] == '.'\n", " ]\n", " if mow_cost is not None:\n", " neighbours += [((x, y), mow_cost)\n", " for x in range(x0-1, x0+2)\n", " for y in range(y0-1, y0+2)\n", " if (x, y) in field\n", " if x == x0 and y != y0 or x != x0 and y == y0\n", " if field[x, y] == '#'\n", " ]\n", " return neighbours" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [], "source": [ "def path_end(path):\n", " return path[-1]\n", " \n", "def extend_path(path, item):\n", " return path + [item]" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [], "source": [ "def show_path(maze, path, sparse=True):\n", " w = max(x for x, _ in maze.keys())\n", " h = max(y for _, y in maze.keys())\n", " for y in range(h+1):\n", " s = ''\n", " for x in range(w+1):\n", " if (x, y) in path:\n", " if maze[x, y] == '#':\n", " s += '*'\n", " else:\n", " s+= 'O'\n", " else:\n", " if sparse:\n", " if maze[x, y] == '.':\n", " s += ' '\n", " else:\n", " s += '.'# field[y][x]\n", " else:\n", " s += maze[x, y]\n", " print(s)" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [], "source": [ "def est_dist(here, there):\n", " return abs(here[0] - there[0]) + abs(here[1] - there[1])" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [], "source": [ "def bfs(maze, start, goal):\n", " agenda = [extend_path([], start)]\n", " while agenda and path_end(agenda[0]) != goal:\n", " current = agenda[0]\n", " here = path_end(current)\n", " neighbours = maze_neighbours(maze, here)\n", "# print(here, neighbours, len(current), len(agenda))\n", " new_paths = [extend_path(current, n) for n, _ in neighbours if n not in current]\n", " agenda = agenda[1:] + new_paths\n", " if agenda:\n", " return agenda[0]\n", " else:\n", " return \"No route found\"" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [], "source": [ "def astar(maze, start, goal, mow_cost=None):\n", " agenda = []\n", " closed = set()\n", " heappush(agenda, (est_dist(start, goal), 0, extend_path([], start)))\n", " while agenda and path_end(agenda[0][2]) != goal:\n", " _, cost, current = heappop(agenda)\n", " here = path_end(current)\n", " if here not in closed:\n", "# print(here, len(current), len(agenda), len(closed))\n", " closed.add(here)\n", " neighbours = maze_neighbours(maze, here, mow_cost=mow_cost)\n", " new_paths = [(cost + c + est_dist(n, goal), cost + c,\n", " extend_path(current, n)) \n", " for n, c in neighbours \n", " if n not in closed]\n", " for np in new_paths:\n", " heappush(agenda, np)\n", " if agenda:\n", " return agenda[0]\n", " else:\n", " return \"No route found\"\n", " " ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [], "source": [ "def bestfs(maze, start, goal, mow_cost=None):\n", " agenda = []\n", " closed = set()\n", " heappush(agenda, (0, extend_path([], start)))\n", " while agenda and path_end(agenda[0][1]) != goal:\n", " cost, current = heappop(agenda)\n", " here = path_end(current)\n", " if here not in closed:\n", "# print(here, len(current), len(agenda), len(closed))\n", " closed.add(here)\n", " neighbours = maze_neighbours(maze, here, mow_cost=mow_cost)\n", " new_paths = [(cost + c,\n", " extend_path(current, n)) \n", " for n, c in neighbours \n", " if n not in closed]\n", " for np in new_paths:\n", " heappush(agenda, np)\n", " if agenda:\n", " return agenda[0]\n", " else:\n", " return \"No route found\"\n", " " ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [], "source": [ "maze = load_maze('../../data/08-maze.txt')\n", "START = (0, 0)\n", "GOAL = (max(x for x, _ in maze.keys()), max(y for _, y in maze.keys()))" ] }, { "cell_type": "code", "execution_count": 47, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "OOOO.. . . . .. .. . . . . . . . \n", ". .OO. . ... . .. . .. . .... ..... . ..\n", "....O. . . . ... ... ... .. .. .. ..... \n", " . OOOOO. ..... . .... . .... .. . ... . \n", " .. ..OOO. . . . . . .... ..... .. .\n", " .... ....O . ..... .. . . . ... . . ..\n", ".. . . O..... . . . . . .... .... ....... \n", " .. . ....O . . . .. ... ... .. . .. .. . .. \n", " .. . . . O.. . .. .... .. .. ... . . . . \n", " ... ..OO. . . . . . ... .. . . .. .. .... \n", "... .. ...O. . .. . . . .. . . . \n", " .. . .O. . . . . ... . . .. . ... . ... .. \n", "... ... OOO. .. ... . . .... . ..... ... \n", ". . . .. ....O . . . ..... ... . . . .\n", " . . ... O.... .. ...... .. . . . .. .. ... \n", ". . . .. ....O. . . . .. . . . . . .\n", " . . .. .O.. . .... . ....... .. .. .. . . \n", "... .. . OO . .. . . . ... .... . .\n", " . .. ....O... ... .. .... ... .. ...\n", "...... . . ..O. . . . ..... .. . .. .... ... \n", ". . . .. . .OO . . . ..... .. . . .\n", " . .. .. .O. ...... ...... .... . ... \n", ". . . ... O. .. . ... . . . .. . . ......\n", ". . .. .. ...O.... . .. . .. . . .. . .. .. \n", " . . .OOO. .. . . . . . .. .. ...\n", ".. ... .. .O.... . .. .... . . ...... .... . \n", " . . . .OO.. . .... . . . . . \n", " . .. ... ..OO.. . .. .. . ....... . .. .....\n", " . . . . ...O .. ... . .. .... ... \n", " . .. . ..O.. . . ... .. .. . .........\n", " ... ..OO . ........... .. .. .. .. \n", ".. .. ....O... . . . ... . . . .... . \n", " . ... . .O .. .. .. .. ... .. ... \n", " . . .. ..OOO............ . .. . ...... ..\n", " . . .O... . . .. ... .. .. ... . .\n", " ... . ...O. . . .... .. . . ..... . ... \n", " . . O . .. . . . . .... . . . ...\n", " . .....O........ .... . ............ \n", " . .... OOO . .. . ... ....... .. . . \n", ".. . ..O....... . . . . . ... .... .... \n", " .. .OO .. . .. . ......... ... . . \n", " .. ...O... . OOOOO ..... . .. . . ... ..... \n", " OOOOO ......O...O..OOOO .... . . \n", "...O....... .. .O . OOOO..O.. .. . .......... ....\n", " OOO. ..OOOOOO.... ... O.. .OOOOOOOOOO.. ... \n", ".....O ..OO.. . . ..OOOOOO. . .. .OO.OOOO . \n", " . ..O...OO.. . .... . . . .. .........OOO..O...\n", " .OOOOO...... ...... .. . . . .O \n", "... . ..... . .. ... . .. .... . . ... .. .O...\n", " . . .. . . . . . . .OOOO\n" ] }, { "data": { "text/plain": [ "142" ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ "fp = bfs(maze, START, GOAL)\n", "show_path(maze, fp, sparse=True)\n", "len(fp) - 1 " ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "OOOO.. . . . .. .. . . . . . . . \n", ". .OO. . ... . .. . .. . .... ..... . ..\n", "....O. . . . ... ... ... .. .. .. ..... \n", " . OOOOO. ..... . .... . .... .. . ... . \n", " .. ..OOO. . . . . . .... ..... .. .\n", " .... ....O . ..... .. . . . ... . . ..\n", ".. . . O..... . . . . . .... .... ....... \n", " .. . ....O . . . .. ... ... .. . .. .. . .. \n", " .. . . . O.. . .. .... .. .. ... . . . . \n", " ... ..OO. . . . . . ... .. . . .. .. .... \n", "... .. ...O. . .. . . . .. . . . \n", " .. . .O. . . . . ... . . .. . ... . ... .. \n", "... ... OOO. .. ... . . .... . ..... ... \n", ". . . .. ....O . . . ..... ... . . . .\n", " . . ... O.... .. ...... .. . . . .. .. ... \n", ". . . .. ....O. . . . .. . . . . . .\n", " . . .. .O.. . .... . ....... .. .. .. . . \n", "... .. . OO . .. . . . ... .... . .\n", " . .. ....O... ... .. .... ... .. ...\n", "...... . . ..O. . . . ..... .. . .. .... ... \n", ". . . .. . . OO . . . ..... .. . . .\n", " . .. .. . .O...... ...... .... . ... \n", ". . . ... .O .. . ... . . . .. . . ......\n", ". . .. .. ... .*.. . .. . .. . . .. . .. .. \n", " . . . .OO.. . . . . . .. .. ...\n", ".. ... .. . ....O. .. .... . . ...... .... . \n", " . . . . .. O. .... . . . . . \n", " . .. ... .. ..OO . .. .. . ....... . .. .....\n", " . . . . ... ..O... . .. .... ... \n", " . .. . .. .. OOOO . . ... .. .. . .........\n", " ... .. . ...*....... .. .. .. .. \n", ".. .. .... ... . .OOOO . ... . . . .... . \n", " . ... . . ..O.. .. .. ... .. ... \n", " . . .. .. ..........**O . .. . ...... ..\n", " . . . ... . . ..O... .. .. ... . .\n", " ... . ... . . . .... .. O. . ..... . ... \n", " . . . ..O. . . . .... . . . ...\n", " . ..... ........ .... OOOOOOOOOO*O............ \n", " . .... . .. . ... ....... ..OO. . \n", ".. . .. ....... . . . . . ...OOO.... .... \n", " .. . .. . .. . ......... ...O . . \n", " .. ... ... . ..... . .. . .O... ..... \n", " ...... ... .. .... . OOOOO . \n", "... ....... .. . . .. .. .. . ........*. ....\n", " . .. .... ... .. . ..O... \n", "..... .. .. . . .. . . .. . .OOOO . \n", " . .. ... .. . .... . . . .. ......... ..O...\n", " . ...... ...... .. . . . .O \n", "... . ..... . .. ... . .. .... . . ... .. .O...\n", " . . .. . . . . . . .OOOO\n" ] }, { "data": { "text/plain": [ "(110, 110, 99)" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "h, c, ap = astar(maze, START, GOAL, mow_cost=3)\n", "show_path(maze, ap, sparse=True)\n", "h, c, len(ap)" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "O .. . . . .. .. . . . . . . . \n", "* . . . ... . .. . .. . .... ..... . ..\n", "*... . . . . ... ... ... .. .. .. ..... \n", "O. . ..... . .... . .... .. . ... . \n", "O .. .. . . . . . . .... ..... .. .\n", "O.... .... . ..... .. . . . ... . . ..\n", "*. . . ..... . . . . . .... .... ....... \n", "O.. . .... . . . .. ... ... .. . .. .. . .. \n", "O.. . . . .. . .. .... .. .. ... . . . . \n", "O ... .. . . . . . . ... .. . . .. .. .... \n", "*.. .. ... . . .. . . . .. . . . \n", "O .. . . . . . . . ... . . .. . ... . ... .. \n", "*.. ... . .. ... . . .... . ..... ... \n", "* . . .. .... . . . ..... ... . . . .\n", "O . . ... .... .. ...... .. . . . .. .. ... \n", "* . . .. .... . . . . .. . . . . . .\n", "O . . .. . .. . .... . ....... .. .. .. . . \n", "*.. .. . . .. . . . ... .... . .\n", "O . .. .... ... ... .. .... ... .. ...\n", "*..... . . .. . . . . ..... .. . .. .... ... \n", "* . . .. . . . . . ..... .. . . .\n", "O . .. .. . . ...... ...... .... . ... \n", "* . . ... . .. . ... . . . .. . . ......\n", "* . .. .. ... .... . .. . .. . . .. . .. .. \n", "O . . . . .. . . . . . .. .. ...\n", "*. ... .. . .... . .. .... . . ...... .... . \n", "O. . . . .. . .... . . . . . \n", "O. .. ... .. .. . .. .. . ....... . .. .....\n", "O. . . . ... .. ... . .. .... ... \n", "O. .. . .. .. . . ... .. .. . .........\n", "O ... .. . ........... .. .. .. .. \n", "*. .. .... ... . . . ... . . . .... . \n", "O. ... . . .. .. .. .. ... .. ... \n", "O. . .. .. ............ . .. . ...... ..\n", "O . . . ... . . .. ... .. .. ... . .\n", "O... . ... . . . .... .. . . ..... . ... \n", "O. . . .. . . . . .... . . . ...\n", "O . ..... ........ .... . ............ \n", "O. .... . .. . ... ....... .. . . \n", "*. . .. ....... . . . . . ... .... .... \n", "O.. . .. . .. . ......... ... . . \n", "O.. ... ... . ..... . .. . . ... ..... \n", "O ...... ... .. .... . . \n", "*.. ....... .. . . .. .. .. . .......... ....\n", "O . .. .... ... .. . .. ... \n", "*.... .. .. . . .. . . .. . . . \n", "O. .. ... .. . .... . . . .. ......... .. ...\n", "O . ...... ...... .. . . . . \n", "*.. . ..... . .. ... . .. .... . . ... .. . ...\n", "OOOOOOOOOOOOOOO*OOOOO*O**OO*OOOO*O*O*OOO*OO*O*OOOO\n" ] }, { "data": { "text/plain": [ "(98, 98, 99)" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "h, c, ap = astar(maze, START, GOAL, mow_cost=1)\n", "show_path(maze, ap, sparse=True)\n", "h, c, len(ap)" ] }, { "cell_type": "code", "execution_count": 48, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "OOOO.. . . . .. .. . . . . . . . \n", ". .OO. . ... . .. . .. . .... ..... . ..\n", "....O. . . . ... ... ... .. .. .. ..... \n", " . OOOOO. ..... . .... . .... .. . ... . \n", " .. ..OOO. . . . . . .... ..... .. .\n", " .... ....O . ..... .. . . . ... . . ..\n", ".. . . O..... . . . . . .... .... ....... \n", " .. . ....O . . . .. ... ... .. . .. .. . .. \n", " .. . . . O.. . .. .... .. .. ... . . . . \n", " ... ..OO. . . . . . ... .. . . .. .. .... \n", "... .. ...O. . .. . . . .. . . . \n", " .. . .O. . . . . ... . . .. . ... . ... .. \n", "... ... OOO. .. ... . . .... . ..... ... \n", ". . . .. ....O . . . ..... ... . . . .\n", " . . ... O.... .. ...... .. . . . .. .. ... \n", ". . . .. ....O. . . . .. . . . . . .\n", " . . .. .O.. . .... . ....... .. .. .. . . \n", "... .. . OO . .. . . . ... .... . .\n", " . .. ....O... ... .. .... ... .. ...\n", "...... . . ..O. . . . ..... .. . .. .... ... \n", ". . . .. . .OO . . . ..... .. . . .\n", " . .. .. .O. ...... ...... .... . ... \n", ". . . ... O. .. . ... . . . .. . . ......\n", ". . .. .. ...O.... . .. . .. . . .. . .. .. \n", " . . .OOO. .. . . . . . .. .. ...\n", ".. ... .. .O.... . .. .... . . ...... .... . \n", " . . . .OO.. . .... . . . . . \n", " . .. ... ..OO.. . .. .. . ....... . .. .....\n", " . . . . ...O .. ... . .. .... ... \n", " . .. . ..O.. . . ... .. .. . .........\n", " ... ..OO . ........... .. .. .. .. \n", ".. .. ....O... . . . ... . . . .... . \n", " . ... . .O .. .. .. .. ... .. ... \n", " . . .. ..OOO............ . .. . ...... ..\n", " . . .O... . . .. ... .. .. ... . .\n", " ... . ...O. . . .... .. . . ..... . ... \n", " . . O . .. . . . . .... . . . ...\n", " . .....O........ .... . ............ \n", " . .... OOO . .. . ... ....... .. . . \n", ".. . ..O....... . . . . . ... .... .... \n", " .. .OO .. . .. . ......... ... . . \n", " .. ...O... . OOOOO ..... . .. . . ... ..... \n", " OOOOO ......O...O..OOOO .... . . \n", "...O....... .. .O . OOOO..O.. .. . .......... ....\n", " OOO. ..OOOOOO.... ... O.. .OOOOOOOOOO.. ... \n", ".....O ..OO.. . . ..OOOOOO. . .. .OO.OOOO . \n", " . ..O...OO.. . .... . . . .. .........OOO..O...\n", " .OOOOO...... ...... .. . . . .O \n", "... . ..... . .. ... . .. .... . . ... .. .O...\n", " . . .. . . . . . . .OOOO\n" ] }, { "data": { "text/plain": [ "(142, 142, 143)" ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "h, c, ap = astar(maze, START, GOAL)\n", "show_path(maze, ap)\n", "h, c, len(ap)" ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "OOOO.. . . . .. .. . . . . . . . \n", ". .OO. . ... . .. . .. . .... ..... . ..\n", "....O. . . . ... ... ... .. .. .. ..... \n", " . OOOOO. ..... . .... . .... .. . ... . \n", " .. ..OOO. . . . . . .... ..... .. .\n", " .... ....O . ..... .. . . . ... . . ..\n", ".. . . O..... . . . . . .... .... ....... \n", " .. . ....O . . . .. ... ... .. . .. .. . .. \n", " .. . . . O.. . .. .... .. .. ... . . . . \n", " ... ..OO. . . . . . ... .. . . .. .. .... \n", "... .. ...O. . .. . . . .. . . . \n", " .. . .O. . . . . ... . . .. . ... . ... .. \n", "... ... OOO. .. ... . . .... . ..... ... \n", ". . . .. ....O . . . ..... ... . . . .\n", " . . ... O.... .. ...... .. . . . .. .. ... \n", ". . . .. ....O. . . . .. . . . . . .\n", " . . .. .O.. . .... . ....... .. .. .. . . \n", "... .. . OO . .. . . . ... .... . .\n", " . .. ....O... ... .. .... ... .. ...\n", "...... . . ..O. . . . ..... .. . .. .... ... \n", ". . . .. . . OO . . . ..... .. . . .\n", " . .. .. . .O...... ...... .... . ... \n", ". . . ... .O .. . ... . . . .. . . ......\n", ". . .. .. ... .*.. . .. . .. . . .. . .. .. \n", " . . . .OO.. . . . . . .. .. ...\n", ".. ... .. . ....O. .. .... . . ...... .... . \n", " . . . . .. O. .... . . . . . \n", " . .. ... .. ..OO . .. .. . ....... . .. .....\n", " . . . . ... ..O... . .. .... ... \n", " . .. . .. .. OOOO . . ... .. .. . .........\n", " ... .. . ...*....... .. .. .. .. \n", ".. .. .... ... . .OOOO . ... . . . .... . \n", " . ... . . ..O.. .. .. ... .. ... \n", " . . .. .. ..........**O . .. . ...... ..\n", " . . . ... . . ..O... .. .. ... . .\n", " ... . ... . . . .... .. O. . ..... . ... \n", " . . . ..O. . . . .... . . . ...\n", " . ..... ........ .... OOOOOOOOOO*O............ \n", " . .... . .. . ... ....... ..OO. . \n", ".. . .. ....... . . . . . ...OOO.... .... \n", " .. . .. . .. . ......... ...O . . \n", " .. ... ... . ..... . .. . .O... ..... \n", " ...... ... .. .... . OOOOO . \n", "... ....... .. . . .. .. .. . ........*. ....\n", " . .. .... ... .. . ..O... \n", "..... .. .. . . .. . . .. . .OOOO . \n", " . .. ... .. . .... . . . .. ......... ..O...\n", " . ...... ...... .. . . . .O \n", "... . ..... . .. ... . .. .... . . ... .. .O...\n", " . . .. . . . . . . .OOOO\n" ] }, { "data": { "text/plain": [ "(110, 99)" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "c, bp = bestfs(maze, START, GOAL, mow_cost=3)\n", "show_path(maze, bp)\n", "c, len(bp)" ] }, { "cell_type": "code", "execution_count": 50, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "OOOO.. . . . .. .. . . . . . . . \n", ". .OO. . ... . .. . .. . .... ..... . ..\n", "....O. . . . ... ... ... .. .. .. ..... \n", " . OOOOO. ..... . .... . .... .. . ... . \n", " .. ..OOO. . . . . . .... ..... .. .\n", " .... ....O . ..... .. . . . ... . . ..\n", ".. . . O..... . . . . . .... .... ....... \n", " .. . ....O . . . .. ... ... .. . .. .. . .. \n", " .. . . . O.. . .. .... .. .. ... . . . . \n", " ... ..OO. . . . . . ... .. . . .. .. .... \n", "... .. ...O. . .. . . . .. . . . \n", " .. . .O. . . . . ... . . .. . ... . ... .. \n", "... ... OOO. .. ... . . .... . ..... ... \n", ". . . .. ....O . . . ..... ... . . . .\n", " . . ... O.... .. ...... .. . . . .. .. ... \n", ". . . .. ....O. . . . .. . . . . . .\n", " . . .. .O.. . .... . ....... .. .. .. . . \n", "... .. . OO . .. . . . ... .... . .\n", " . .. ....O... ... .. .... ... .. ...\n", "...... . . ..O. . . . ..... .. . .. .... ... \n", ". . . .. . .OO . . . ..... .. . . .\n", " . .. .. .O. ...... ...... .... . ... \n", ". . . ... O. .. . ... . . . .. . . ......\n", ". . .. .. ...O.... . .. . .. . . .. . .. .. \n", " . . .OOO. .. . . . . . .. .. ...\n", ".. ... .. .O.... . .. .... . . ...... .... . \n", " . . . .OO.. . .... . . . . . \n", " . .. ... ..OO.. . .. .. . ....... . .. .....\n", " . . . . ...O .. ... . .. .... ... \n", " . .. . ..O.. . . ... .. .. . .........\n", " ... ..OO . ........... .. .. .. .. \n", ".. .. ....O... . . . ... . . . .... . \n", " . ... . .O .. .. .. .. ... .. ... \n", " . . .. ..OOO............ . .. . ...... ..\n", " . . .O... . . .. ... .. .. ... . .\n", " ... . ...O. . . .... .. . . ..... . ... \n", " . . O . .. . . . . .... . . . ...\n", " . .....O........ .... . ............ \n", " . .... OOO . .. . ... ....... .. . . \n", ".. . ..O....... . . . . . ... .... .... \n", " .. .OO .. . .. . ......... ... . . \n", " .. ...O... . OOOOO ..... . .. . . ... ..... \n", " OOOOO ......O...O..OOOO .... . . \n", "...O....... .. .O . OOOO..O.. .. . .......... ....\n", " OOO. ..OOOOOO.... ... O.. .OOOOOOOOOO.. ... \n", ".....O ..OO.. . . ..OOOOOO. . .. .OO.OOOO . \n", " . ..O...OO.. . .... . . . .. .........OOO..O...\n", " .OOOOO...... ...... .. . . . .O \n", "... . ..... . .. ... . .. .... . . ... .. .O...\n", " . . .. . . . . . . .OOOO\n" ] }, { "data": { "text/plain": [ "(142, 143)" ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" } ], "source": [ "c, bp = bestfs(maze, START, GOAL)\n", "show_path(maze, bp)\n", "c, len(bp)" ] }, { "cell_type": "code", "execution_count": 51, "metadata": {}, "outputs": [], "source": [ "def path_cost(maze, path, mow_cost=1):\n", " total = -1\n", " for x, y in path:\n", " if maze[x, y] == '#':\n", " total += mow_cost\n", " else:\n", " total += 1\n", " return total" ] }, { "cell_type": "code", "execution_count": 52, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(142, 143)" ] }, "execution_count": 52, "metadata": {}, "output_type": "execute_result" } ], "source": [ "path_cost(maze, ap, 3), len(ap)" ] }, { "cell_type": "code", "execution_count": 53, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(142, 143)" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "path_cost(maze, bp), len(bp)" ] }, { "cell_type": "code", "execution_count": 59, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "9.54 ms ± 72.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n" ] } ], "source": [ "%%timeit\n", "bfs(maze, START, GOAL)" ] }, { "cell_type": "code", "execution_count": 60, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "33.1 ms ± 427 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n" ] } ], "source": [ "%%timeit\n", "bestfs(maze, START, GOAL, mow_cost=3)" ] }, { "cell_type": "code", "execution_count": 61, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "32.8 ms ± 494 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n" ] } ], "source": [ "%%timeit\n", "bestfs(maze, START, GOAL, mow_cost=3)" ] }, { "cell_type": "code", "execution_count": 62, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "5.01 ms ± 30.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n" ] } ], "source": [ "%%timeit\n", "astar(maze, START, GOAL)" ] }, { "cell_type": "code", "execution_count": 63, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "7.65 ms ± 56 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n" ] } ], "source": [ "%%timeit\n", "bestfs(maze, START, GOAL)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.6" } }, "nbformat": 4, "nbformat_minor": 2 }