From 115d813702f9e92abadcf744a8568e3ed53845f2 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Sat, 6 Oct 2018 20:18:38 +0100 Subject: [PATCH] Task 8 Python done --- src/task8/task8.ipynb | 839 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 839 insertions(+) create mode 100644 src/task8/task8.ipynb diff --git a/src/task8/task8.ipynb b/src/task8/task8.ipynb new file mode 100644 index 0000000..6145dd1 --- /dev/null +++ b/src/task8/task8.ipynb @@ -0,0 +1,839 @@ +{ + "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 +} -- 2.34.1