src/task8/task8.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 17,
   6    "metadata": {},
   7    "outputs": [],
   8    "source": [
   9     "from heapq import *"
  10    ]
  11   },
  12   {
  13    "cell_type": "code",
  14    "execution_count": 18,
  15    "metadata": {},
  16    "outputs": [],
  17    "source": [
  18     "def load_maze(fname='maze.txt'):\n",
  19     "    mazet = [l.strip() for l in open(fname)]\n",
  20     "    maze = {}\n",
  21     "    for y, row in enumerate(mazet):\n",
  22     "        for x, cell in enumerate(row):\n",
  23     "            maze[x, y] = cell\n",
  24     "    return maze"
  25    ]
  26   },
  27   {
  28    "cell_type": "code",
  29    "execution_count": 31,
  30    "metadata": {},
  31    "outputs": [],
  32    "source": [
  33     "def maze_neighbours(field, here, mow_cost=None):\n",
  34     "    x0, y0 = here\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",
  41     "           ]\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",
  49     "           ]\n",
  50     "    return neighbours"
  51    ]
  52   },
  53   {
  54    "cell_type": "code",
  55    "execution_count": 20,
  56    "metadata": {},
  57    "outputs": [],
  58    "source": [
  59     "def path_end(path):\n",
  60     "    return path[-1]\n",
  61     "    \n",
  62     "def extend_path(path, item):\n",
  63     "    return path + [item]"
  64    ]
  65   },
  66   {
  67    "cell_type": "code",
  68    "execution_count": 21,
  69    "metadata": {},
  70    "outputs": [],
  71    "source": [
  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",
  76     "        s = ''\n",
  77     "        for x in range(w+1):\n",
  78     "            if (x, y) in path:\n",
  79     "                if maze[x, y] == '#':\n",
  80     "                    s += '*'\n",
  81     "                else:\n",
  82     "                    s+= 'O'\n",
  83     "            else:\n",
  84     "                if sparse:\n",
  85     "                    if maze[x, y] == '.':\n",
  86     "                        s += ' '\n",
  87     "                    else:\n",
  88     "                        s += '.'# field[y][x]\n",
  89     "                else:\n",
  90     "                    s += maze[x, y]\n",
  91     "        print(s)"
  92    ]
  93   },
  94   {
  95    "cell_type": "code",
  96    "execution_count": 22,
  97    "metadata": {},
  98    "outputs": [],
  99    "source": [
 100     "def est_dist(here, there):\n",
 101     "    return abs(here[0] - there[0]) + abs(here[1] - there[1])"
 102    ]
 103   },
 104   {
 105    "cell_type": "code",
 106    "execution_count": 32,
 107    "metadata": {},
 108    "outputs": [],
 109    "source": [
 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",
 119     "    if agenda:\n",
 120     "        return agenda[0]\n",
 121     "    else:\n",
 122     "        return \"No route found\""
 123    ]
 124   },
 125   {
 126    "cell_type": "code",
 127    "execution_count": 33,
 128    "metadata": {},
 129    "outputs": [],
 130    "source": [
 131     "def astar(maze, start, goal, mow_cost=None):\n",
 132     "    agenda = []\n",
 133     "    closed = set()\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",
 148     "    if agenda:\n",
 149     "        return agenda[0]\n",
 150     "    else:\n",
 151     "        return \"No route found\"\n",
 152     "    "
 153    ]
 154   },
 155   {
 156    "cell_type": "code",
 157    "execution_count": 34,
 158    "metadata": {},
 159    "outputs": [],
 160    "source": [
 161     "def bestfs(maze, start, goal, mow_cost=None):\n",
 162     "    agenda = []\n",
 163     "    closed = set()\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",
 178     "    if agenda:\n",
 179     "        return agenda[0]\n",
 180     "    else:\n",
 181     "        return \"No route found\"\n",
 182     "    "
 183    ]
 184   },
 185   {
 186    "cell_type": "code",
 187    "execution_count": 35,
 188    "metadata": {},
 189    "outputs": [],
 190    "source": [
 191     "maze = load_maze('../../data/08-maze.txt')\n",
 192     "START = (0, 0)\n",
 193     "GOAL = (max(x for x, _ in maze.keys()), max(y for _, y in maze.keys()))"
 194    ]
 195   },
 196   {
 197    "cell_type": "code",
 198    "execution_count": 47,
 199    "metadata": {},
 200    "outputs": [
 201     {
 202      "name": "stdout",
 203      "output_type": "stream",
 204      "text": [
 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"
 255      ]
 256     },
 257     {
 258      "data": {
 259       "text/plain": [
 260        "142"
 261       ]
 262      },
 263      "execution_count": 47,
 264      "metadata": {},
 265      "output_type": "execute_result"
 266     }
 267    ],
 268    "source": [
 269     "fp = bfs(maze, START, GOAL)\n",
 270     "show_path(maze, fp, sparse=True)\n",
 271     "len(fp) - 1 "
 272    ]
 273   },
 274   {
 275    "cell_type": "code",
 276    "execution_count": 37,
 277    "metadata": {},
 278    "outputs": [
 279     {
 280      "name": "stdout",
 281      "output_type": "stream",
 282      "text": [
 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"
 333      ]
 334     },
 335     {
 336      "data": {
 337       "text/plain": [
 338        "(110, 110, 99)"
 339       ]
 340      },
 341      "execution_count": 37,
 342      "metadata": {},
 343      "output_type": "execute_result"
 344     }
 345    ],
 346    "source": [
 347     "h, c, ap = astar(maze, START, GOAL, mow_cost=3)\n",
 348     "show_path(maze, ap, sparse=True)\n",
 349     "h, c, len(ap)"
 350    ]
 351   },
 352   {
 353    "cell_type": "code",
 354    "execution_count": 38,
 355    "metadata": {},
 356    "outputs": [
 357     {
 358      "name": "stdout",
 359      "output_type": "stream",
 360      "text": [
 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"
 411      ]
 412     },
 413     {
 414      "data": {
 415       "text/plain": [
 416        "(98, 98, 99)"
 417       ]
 418      },
 419      "execution_count": 38,
 420      "metadata": {},
 421      "output_type": "execute_result"
 422     }
 423    ],
 424    "source": [
 425     "h, c, ap = astar(maze, START, GOAL, mow_cost=1)\n",
 426     "show_path(maze, ap, sparse=True)\n",
 427     "h, c, len(ap)"
 428    ]
 429   },
 430   {
 431    "cell_type": "code",
 432    "execution_count": 48,
 433    "metadata": {},
 434    "outputs": [
 435     {
 436      "name": "stdout",
 437      "output_type": "stream",
 438      "text": [
 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"
 489      ]
 490     },
 491     {
 492      "data": {
 493       "text/plain": [
 494        "(142, 142, 143)"
 495       ]
 496      },
 497      "execution_count": 48,
 498      "metadata": {},
 499      "output_type": "execute_result"
 500     }
 501    ],
 502    "source": [
 503     "h, c, ap = astar(maze, START, GOAL)\n",
 504     "show_path(maze, ap)\n",
 505     "h, c, len(ap)"
 506    ]
 507   },
 508   {
 509    "cell_type": "code",
 510    "execution_count": 49,
 511    "metadata": {},
 512    "outputs": [
 513     {
 514      "name": "stdout",
 515      "output_type": "stream",
 516      "text": [
 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"
 567      ]
 568     },
 569     {
 570      "data": {
 571       "text/plain": [
 572        "(110, 99)"
 573       ]
 574      },
 575      "execution_count": 49,
 576      "metadata": {},
 577      "output_type": "execute_result"
 578     }
 579    ],
 580    "source": [
 581     "c, bp = bestfs(maze, START, GOAL, mow_cost=3)\n",
 582     "show_path(maze, bp)\n",
 583     "c, len(bp)"
 584    ]
 585   },
 586   {
 587    "cell_type": "code",
 588    "execution_count": 50,
 589    "metadata": {},
 590    "outputs": [
 591     {
 592      "name": "stdout",
 593      "output_type": "stream",
 594      "text": [
 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"
 645      ]
 646     },
 647     {
 648      "data": {
 649       "text/plain": [
 650        "(142, 143)"
 651       ]
 652      },
 653      "execution_count": 50,
 654      "metadata": {},
 655      "output_type": "execute_result"
 656     }
 657    ],
 658    "source": [
 659     "c, bp = bestfs(maze, START, GOAL)\n",
 660     "show_path(maze, bp)\n",
 661     "c, len(bp)"
 662    ]
 663   },
 664   {
 665    "cell_type": "code",
 666    "execution_count": 51,
 667    "metadata": {},
 668    "outputs": [],
 669    "source": [
 670     "def path_cost(maze, path, mow_cost=1):\n",
 671     "    total = -1\n",
 672     "    for x, y in path:\n",
 673     "        if maze[x, y] == '#':\n",
 674     "            total += mow_cost\n",
 675     "        else:\n",
 676     "            total += 1\n",
 677     "    return total"
 678    ]
 679   },
 680   {
 681    "cell_type": "code",
 682    "execution_count": 52,
 683    "metadata": {},
 684    "outputs": [
 685     {
 686      "data": {
 687       "text/plain": [
 688        "(142, 143)"
 689       ]
 690      },
 691      "execution_count": 52,
 692      "metadata": {},
 693      "output_type": "execute_result"
 694     }
 695    ],
 696    "source": [
 697     "path_cost(maze, ap, 3), len(ap)"
 698    ]
 699   },
 700   {
 701    "cell_type": "code",
 702    "execution_count": 53,
 703    "metadata": {},
 704    "outputs": [
 705     {
 706      "data": {
 707       "text/plain": [
 708        "(142, 143)"
 709       ]
 710      },
 711      "execution_count": 53,
 712      "metadata": {},
 713      "output_type": "execute_result"
 714     }
 715    ],
 716    "source": [
 717     "path_cost(maze, bp), len(bp)"
 718    ]
 719   },
 720   {
 721    "cell_type": "code",
 722    "execution_count": 59,
 723    "metadata": {},
 724    "outputs": [
 725     {
 726      "name": "stdout",
 727      "output_type": "stream",
 728      "text": [
 729       "9.54 ms ± 72.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
 730      ]
 731     }
 732    ],
 733    "source": [
 734     "%%timeit\n",
 735     "bfs(maze, START, GOAL)"
 736    ]
 737   },
 738   {
 739    "cell_type": "code",
 740    "execution_count": 60,
 741    "metadata": {},
 742    "outputs": [
 743     {
 744      "name": "stdout",
 745      "output_type": "stream",
 746      "text": [
 747       "33.1 ms ± 427 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
 748      ]
 749     }
 750    ],
 751    "source": [
 752     "%%timeit\n",
 753     "bestfs(maze, START, GOAL, mow_cost=3)"
 754    ]
 755   },
 756   {
 757    "cell_type": "code",
 758    "execution_count": 61,
 759    "metadata": {},
 760    "outputs": [
 761     {
 762      "name": "stdout",
 763      "output_type": "stream",
 764      "text": [
 765       "32.8 ms ± 494 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
 766      ]
 767     }
 768    ],
 769    "source": [
 770     "%%timeit\n",
 771     "bestfs(maze, START, GOAL, mow_cost=3)"
 772    ]
 773   },
 774   {
 775    "cell_type": "code",
 776    "execution_count": 62,
 777    "metadata": {},
 778    "outputs": [
 779     {
 780      "name": "stdout",
 781      "output_type": "stream",
 782      "text": [
 783       "5.01 ms ± 30.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
 784      ]
 785     }
 786    ],
 787    "source": [
 788     "%%timeit\n",
 789     "astar(maze, START, GOAL)"
 790    ]
 791   },
 792   {
 793    "cell_type": "code",
 794    "execution_count": 63,
 795    "metadata": {},
 796    "outputs": [
 797     {
 798      "name": "stdout",
 799      "output_type": "stream",
 800      "text": [
 801       "7.65 ms ± 56 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
 802      ]
 803     }
 804    ],
 805    "source": [
 806     "%%timeit\n",
 807     "bestfs(maze, START, GOAL)"
 808    ]
 809   },
 810   {
 811    "cell_type": "code",
 812    "execution_count": null,
 813    "metadata": {},
 814    "outputs": [],
 815    "source": []
 816   }
 817  ],
 818  "metadata": {
 819   "kernelspec": {
 820    "display_name": "Python 3",
 821    "language": "python",
 822    "name": "python3"
 823   },
 824   "language_info": {
 825    "codemirror_mode": {
 826     "name": "ipython",
 827     "version": 3
 828    },
 829    "file_extension": ".py",
 830    "mimetype": "text/x-python",
 831    "name": "python",
 832    "nbconvert_exporter": "python",
 833    "pygments_lexer": "ipython3",
 834    "version": "3.6.6"
 835   }
 836  },
 837  "nbformat": 4,
 838  "nbformat_minor": 2
 839 }