AIF_lab4.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ee3X4yU0ufQ6"
      },
      "source": [
        "# **Explanation**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LIeuQ--xvWxZ"
      },
      "source": [
        "This section is an explanation of the system you'll be working with. There aren't any problems to solve. Read it carefully anyway.\n",
        "\n",
        "This laboratory will involve implementing several search techniques. For each type of search function you are asked to write, you will get a graph (with a list of nodes and a list of edges and a heuristic), a start node, and a goal node.\n",
        "\n",
        "A graph is an object of type Graph that has lists `.nodes` and `.edges` and a dictionary `.heuristic` (you won't need to access the dictionary directly).\n",
        "\n",
        "A node is just a string representing the name of the node.\n",
        "\n",
        "An Edge is an object with attributes `.name` (a string), `.node1` (a string, the node at one end of the edge), `.node2` (a string, the node at the other end of the edge), and `.length` (a number).\n",
        "\n",
        "You will need the following methods:\n",
        "\n",
        "*  `graph.get_connected_nodes(node)`: Given a node name, return a list of all node names that are connected to the specified node directly by an edge.\n",
        "*  `graph.get_edge(node1, node2)`: Given two node names, return the edge that connects those nodes, or None if there is no such edge.\n",
        "*  `graph.get_heuristic(start, goal)`: Given the name of a starting node in the graph and the name of a goal node, return the heuristic value from that start to that goal. If that heuristic value wasn't supplied when creating the graph, then return 0.\n",
        "\n",
        "You might also want to use the following methods:\n",
        "* `graph.are_connected(node1, node2)`: Return True if and only if there is an edge running directly between node1 and node2; False otherwise.\n",
        "* `graph.is_valid_path(path)`: Given 'path' as an ordered list of node names, return True if and only if there is an edge between every two adjacent nodes in the list, False otherwise.\n",
        "\n",
        "In addition, you're expected to know how to access elements in lists and dictionaries at this point. For some portions of this lab, you may want to use lists like either stacks or queues. However, you should NOT import other modules (such as\n",
        "`deque`), because it will confuse the tests.\n",
        "\n",
        "You also may need to sort Python lists. Python has built-in sorting functionality, documented at\n",
        "[http://wiki.python.org/moin/HowTo/Sorting](http://wiki.python.org/moin/HowTo/Sorting)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bc0vYzgPvAn7"
      },
      "source": [
        "## The Agenda"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "o5dgGBlLvQle"
      },
      "source": [
        "Different search techniques explore nodes in different orders, and we will keep track of the nodes\n",
        "remaining to explore in a list we will call the **agenda** (in class we called this the **queue**). Some\n",
        "techniques will add paths to the top of the agenda, treating it like a stack, while others will add to the\n",
        "back of the agenda, treating it like a queue. Some agendas are organized by heuristic value, others are\n",
        "ordered by path distance, and others by depth in the search tree. Your job will be to show your\n",
        "knowledge of search techniques by implementing different types of search and making slight\n",
        "modifications to how the agenda is accessed and updated."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "C-zJ8pO2v4GG"
      },
      "source": [
        "## Extending a path in the agenda"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gYCZu8UwvkRA"
      },
      "source": [
        "In this laboratory, a path consists of a list of node names. When it comes time to extend a new path, a path is selected from the agenda. The last node in the path is identified as the node to be extended. The nodes that connect to the extended node, the adjacent nodes, are the possible extensions to the path. Of the possible extensions, the following nodes are NOT added:\n",
        "* nodes that already appear in the path.\n",
        "* nodes that have already been extended (if an extended-nodes set is being used.)\n",
        "\n",
        "As an example, if node *A* is connected to nodes *S*, *B*, and *C*, then the path ['S', 'A'] is extended to the new paths ['S', 'A', 'B'] and ['S', 'A', 'C'] (but not ['S', 'A', 'S']).\n",
        "\n",
        "The paths you create should be new objects. If you try to extend a path by *modifying* (or \"mutating\") the existing path, for example by using list `.append()`, you will probably find yourself in a world of hurt."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "pn7PVYKiwCgg"
      },
      "source": [
        "## The Extended-Nodes Set"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Mt8hTZyGwVWO"
      },
      "source": [
        "An extended-set, sometimes called an \"extended list\" or \"visited set\" or \"closed list\", consists of nodes \n",
        "that have been extended, and lets the algorithm avoid extending the same node multiple times, sometimes significantly speeding up search. You will be implementing types of search that use extended-sets. Note that an extended-nodes set is a set, so if, e.g., you're using a list to represent it, then be careful that a maximum of one of each node name should appear in it. Python offers other options for representing sets, which may help you avoid this issue. The main point is to check that nodes are not in the set before you extend them, and to put nodes into the extended-set when you do choose to extend them."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vhdoaWbPwe1z"
      },
      "source": [
        "## Returning a Search Result"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sDEQd80TwnVQ"
      },
      "source": [
        "A search result is a path which should consist of a list of node names, ordered from the start node,\n",
        "following existing edges, to the goal node. If no path is found, the search should return an empty list, []."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "igNzohvPw34R"
      },
      "source": [
        "## Exiting the search"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "E-UKMVEXw6ud"
      },
      "source": [
        "Non-optimal searches such as DFS, BFS, Hill-Climbing (and Beam, not in this lab) **may** exit either:\n",
        "\n",
        "* when they find a path-to-goal in the agenda\n",
        "* when a path-to-goal is first removed from the agenda.\n",
        "\n",
        "Optimal searches such as branch and bound (not in this lab) and A* **must** always exit:\n",
        "* When a path-to-goal is first removed from the agenda.\n",
        "\n",
        "(This is because the agenda is ordered by path length (or heuristic path length), so a path-to-goal is not necessarily the best when it is added to the agenda, but when it is removed, it is guaranteed to have the shortest path length (or heuristic path length).)\n",
        "\n",
        "For the sake of consistency, you should implement all your searches to exit:\n",
        "* **When a path-to-goal is first removed from the agenda.**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ctWPfxUv4GGT"
      },
      "source": [
        "# **Part 1: Non-optimal searches**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "YIulQUvBz3xE"
      },
      "source": [
        "## Warm-up: Breadth-first Search and Depth-first Search\n",
        "You should complete this section if you want to get a better understanding of the basics of search.\n",
        "\n",
        "The first two types of search to implement are breadth-first search and depth-first search. You should **allow backtracking** for the search.\n",
        "\n",
        "Your task is to implement the following functions:\n",
        "\n",
        "`def bfs(graph, start, goal):`\n",
        "\n",
        "\n",
        "`def dfs(graph, start, goal):`\n",
        "\n",
        "The inputs to the functions are:\n",
        "* `graph`: The graph\n",
        "* `start`: The name of the node that you want to start traversing from\n",
        "* `goal`: The name of the node that you want to reach\n",
        "\n",
        "When a path to the goal node has been found, return the result as explained in the section **Returning a Search Result** (above).\n",
        "\n",
        "## Hill Climbing\n",
        "\n",
        "Hill climbing is very similar to depth first search. There is only a slight modification to the ordering of\n",
        "paths that are added to the agenda. For this part, implement the following function:\n",
        "\n",
        "`def hill_climbing(graph, start, goal):`\n",
        "\n",
        "The hill-climbing procedure you define here *should* use backtracking, for consistency with the other\n",
        "methods, even though hill-climbing typically is not implemented with backtracking. Hill-climbing does\n",
        "not use an extended-set."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1aDXos7r5bKY"
      },
      "source": [
        "# **Part 2: Optimal searches**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6KzOg60c3StR"
      },
      "source": [
        "The search techniques you have implemented so far have not taken into account the edge distances.\n",
        "Instead we were just trying to find one possible solution of many. This part of the laboratory involves finding the path with the shortest distance from the start node to the goal node. The search types that guarantee optimal solutions are branch and bound (not to be implemented) and A*.\n",
        "\n",
        "Since this type of problem requires knowledge of the length of a path, implement the following function that computes the length of a path:\n",
        "\n",
        "`def path_length(graph, node_names):`\n",
        "\n",
        "The function takes in a graph and a list of node names that make up a path in that graph, and it computes the length of that path, according to the \"`LENGTH`\" values for each relevant edge. You can assume the path is valid (there are edges between each node in the graph), so you do not need to test to make sure there is actually an edge between consecutive nodes in the path. If there is only one node in the path, your function should return 0.\n",
        "\n",
        "## A*\n",
        "\n",
        "You're almost there! You've used heuristic estimates to speed up search and edge lengths to compute optimal paths. Let's combine the two ideas now to get the A* search method. In A*, the path with the least (heuristic estimate + path length) is taken from the agenda to extend. A* always uses an extended-set -- make sure to use one. (Note: If the heuristic is not consistent, then using an extended-set can sometimes prevent A* from finding an optimal solution.)\n",
        "\n",
        "`def a_star(graph, start, goal):`\n",
        "\n",
        "## Graph Heuristics\n",
        "\n",
        "A heuristic value gives an approximation from a node to a goal. You've learned that in order for the\n",
        "heuristic to be admissible, the heuristic value for every node in a graph must be less than or equal to the distance of the shortest path from the goal to that node. In order for a heuristic to be consistent, for each edge in the graph, the edge length must be greater than or equal to the absolute value of the difference between the two heuristic values of its nodes.\n",
        "\n",
        "For this part, complete the following functions, which return True if and only if the heuristics for the given goal are admissible or consistent, respectively, and False otherwise:\n",
        "\n",
        "`def is_admissible(graph, goal):`\n",
        "\n",
        "`def is_consistent(graph, goal):`"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QCvwOt9UjD5O"
      },
      "source": [
        "# **Production**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6LAqvjfkMrvd"
      },
      "source": [
        "## Graph and Edge"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 24,
      "metadata": {
        "id": "XcjWbPzdh-N7"
      },
      "outputs": [],
      "source": [
        "try:\n",
        "    set()\n",
        "except NameError:\n",
        "    from sets import Set as set, ImmutableSet as frozenset\n",
        "\n",
        "NAME=\"NAME\"\n",
        "NODE1=\"NODE1\"\n",
        "NODE2=\"NODE2\"\n",
        "VAL=\"LENGTH\"\n",
        "\n",
        "class Edge:\n",
        "    def __init__(self, name, node1, node2, length):\n",
        "        self.name = name\n",
        "        self.node1 = node1\n",
        "        self.node2 = node2\n",
        "        self.length = length\n",
        "    def __repr__(self):\n",
        "        return 'Edge ' + self.name + \\\n",
        "               ' from ' + self.node1 + ' to ' + self.node2 + \\\n",
        "               ' with length ' + str(self.length)\n",
        "\n",
        "class Graph:\n",
        "    def __init__(self, nodes=None, edgesdict=None, heuristic=None,\n",
        "                 edges=None):\n",
        "        '''specify EITHER edgesdict OR edges'''\n",
        "        if edges:\n",
        "            self.edges = edges\n",
        "        elif edgesdict:\n",
        "            try:\n",
        "                self.edges = [Edge(e['NAME'], e['NODE1'], e['NODE2'], e['LENGTH'])\\\n",
        "                              for e in edgesdict]\n",
        "            except KeyError:\n",
        "                self.edges = [Edge(e['name'], e['node1'], e['node2'], e['length'])\\\n",
        "                              for e in edgesdict]\n",
        "        else:\n",
        "            self.edges = []\n",
        "        self.nodes = nodes\n",
        "        if not nodes:\n",
        "            self.nodes = list(set([edge.node1 for edge in self.edges] + \n",
        "                                  [edge.node2 for edge in self.edges]))\n",
        "        # heuristic is a dictionary where heuristic[G][S] is the\n",
        "        #  heuristic distance from S to G\n",
        "        self.heuristic = heuristic\n",
        "        if not heuristic:\n",
        "            self.heuristic = {}\n",
        "        self.validate()\n",
        "    \n",
        "    def validate(self):\n",
        "        for name in self.nodes:\n",
        "            assert isinstance(name,str), str(type(name))+\": \"+str(name)\n",
        "        assert len(self.nodes) == len(set(self.nodes)), \"no duplicate nodes\"\n",
        "        edgenames = [edge.name for edge in self.edges]\n",
        "        assert len(edgenames) == len(set(edgenames)), \"no duplicate edges\"\n",
        "        for edge in self.edges:\n",
        "            assert isinstance(edge.name, str), type(edge.name)\n",
        "            assert edge.node1 in self.nodes\n",
        "            assert edge.node2 in self.nodes\n",
        "            assert edge.length > 0, \"positive edges only today\"\n",
        "        for start in self.nodes:\n",
        "            for end in self.nodes:\n",
        "                assert self.get_heuristic(start,end) >= 0\n",
        "\n",
        "    def get_connected_nodes(self, node):\n",
        "        \"\"\"\n",
        "        gets a list of all node id values connected to a given node.\n",
        "        'node' should be a node name, not a dictionary.\n",
        "        The return value is a list of node names.\n",
        "        \"\"\"\n",
        "        assert node in self.nodes, \"No node \"+str(node)+\" in graph \"+str(self)\n",
        "        result = [x.node2 for x in self.edges if x.node1 == node]\n",
        "        result += [x.node1 for x in self.edges if x.node2 == node]\n",
        "        return sorted(result)\n",
        "\n",
        "    def get_edge(self, node1, node2):\n",
        "        \"\"\"\n",
        "        checks the list of edges and returns an edge if\n",
        "        both connected nodes are part of the edge, or 'None' otherwise.\n",
        "        'node1' and 'node2' are names of nodes, not 'NODE' dictionaries.\n",
        "        \"\"\"\n",
        "        assert node1 in self.nodes, \"No node \"+str(node1)+\" in graph \"+str(self)\n",
        "        assert node2 in self.nodes, \"No node \"+str(node2)+\" in graph \"+str(self)\n",
        "        node_names = ( node1, node2 )\n",
        "        for edge in self.edges:\n",
        "            if ((edge.node1, edge.node2) == node_names or \n",
        "                (edge.node2, edge.node1) == node_names):\n",
        "                return edge\n",
        "        return None\n",
        "\n",
        "    def are_connected(self, node1, node2):\n",
        "        \"\"\"\n",
        "        checks if two edges are connected.\n",
        "        'node1' and 'node2' are names of nodes, not 'NODE' dictionaries.\n",
        "        \"\"\"\n",
        "        return bool( self.get_edge(node1, node2) )\n",
        "\n",
        "    def get_heuristic(self, start, goal):\n",
        "        \"\"\" Return the value of the heuristic from the start to the goal\"\"\"\n",
        "        assert start in self.nodes, \"No node \"+str(start)+\" in graph \"+str(self)\n",
        "        assert goal in self.nodes, \"No node \"+str(goal)+\" in graph \"+str(self)\n",
        "        if goal in self.heuristic:\n",
        "            if start in self.heuristic[goal]:\n",
        "                return self.heuristic[goal][start]\n",
        "            else:\n",
        "                return 0 # we have checked that everything is positive\n",
        "        else: \n",
        "            return 0 # we have checked that everything is positive\n",
        "    \n",
        "    def is_valid_path(self, path):\n",
        "        def is_valid_path_reducer(elt_a, elt_b):\n",
        "            if elt_a == False or not self.are_connected(elt_a, elt_b):\n",
        "                return False\n",
        "            else:\n",
        "                return elt_b\n",
        "        return (reduce(is_valid_path_reducer, path) != False)\n",
        "\n",
        "    def add_edge(self, node1, node2, length, name=None):\n",
        "        if node1 not in self.nodes:\n",
        "            self.nodes.append(node1)\n",
        "        if node2 not in self.nodes:\n",
        "            self.nodes.append(node2)\n",
        "        if name == None:\n",
        "            name = (\"%s %s\" % (node1, node2))\n",
        "        self.edges.append(Edge(name, node1, node2, length))\n",
        "\n",
        "    def set_heuristic(self, start, goal, value):\n",
        "        if goal not in self.heuristic:\n",
        "            self.heuristic[goal] = {}\n",
        "        self.heuristic[goal][start] = value\n",
        "\n",
        "    def __str__(self):\n",
        "        return \"Graph: \\n  edges=\"+str(self.edges)+\"\\n  heuristic=\"+str(self.heuristic)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BpNAj3IaNIA0"
      },
      "source": [
        "## Graphs for testing"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 25,
      "metadata": {
        "id": "4PpUGJ2rNIA2"
      },
      "outputs": [],
      "source": [
        "## The graphs you will use for the problem set.\n",
        "\n",
        "## The heuristic values\n",
        "## are lower bounds on the distance to the node with the id of\n",
        "## \"Common Area\"\n",
        "\n",
        "GRAPH1 = Graph(edgesdict = \\\n",
        "               [{NAME:'e1',  VAL: 5, NODE1:'Common Area', NODE2:'Stairs'},\n",
        "                {NAME:'e2',  VAL:15, NODE1:'Entrance Hall', NODE2:'Hospital'},\n",
        "                {NAME:'e3',  VAL: 7, NODE1:'Classroom 11', NODE2:'Hospital'},\n",
        "                {NAME:'e4',  VAL:25, NODE1:'Haunted Bathroom', NODE2:'The Chamber'},\n",
        "                {NAME:'e5',  VAL: 5, NODE1:'Forbidden Area', NODE2:'Trophy Room'},\n",
        "                {NAME:'e6',  VAL: 3, NODE1:'Mirrored Room', NODE2:'Statues'},\n",
        "                {NAME:'e7',  VAL: 1, NODE1:'Grand Hall', NODE2:'Entrance Hall'},\n",
        "                {NAME:'e8',  VAL: 4, NODE1:'Dungeon 5', NODE2:'Haunted Bathroom'},\n",
        "                {NAME:'e9',  VAL: 2, NODE1:'Stairs', NODE2:'Grand Hall' },\n",
        "                {NAME:'e10', VAL: 9, NODE1:'Statues', NODE2:'Stairs' },\n",
        "                {NAME:'e11', VAL: 6, NODE1:'Entrance Hall', NODE2:'Haunted Bathroom' },\n",
        "                {NAME:'e12', VAL: 4, NODE1:'Forbidden Area', NODE2:'Stairs' },\n",
        "                {NAME:'e13', VAL:10, NODE1:'Classroom 11', NODE2:'Entrance Hall' },\n",
        "                {NAME:'e14', VAL: 5, NODE1:'Trophy Room', NODE2:'Stairs' },\n",
        "                {NAME:'e15', VAL: 8, NODE1:'Stairs', NODE2:'Mirrored Room' },\n",
        "                {NAME:'e16', VAL: 3, NODE1:'Entrance Hall', NODE2:'Stairs' },\n",
        "                {NAME:'e17', VAL: 8, NODE1:'Necessary Room', NODE2:'Common Area'}\n",
        "                ],\n",
        "               heuristic = \\\n",
        "               {'Common Area':\n",
        "                    {'Hospital':17,\n",
        "                     'Classroom 11':10,\n",
        "                     'Entrance Hall':7,\n",
        "                     'Haunted Bathroom':13,\n",
        "                     'Dungeon 5':15,\n",
        "                     'The Chamber':14,\n",
        "                     'Forbidden Area':8,\n",
        "                     'Trophy Room':6,\n",
        "                     'Stairs':4,\n",
        "                     'Grand Hall':6,\n",
        "                     'Common Area':0,\n",
        "                     'Statues':12,\n",
        "                     'Mirrored Room':10,\n",
        "                     'Necessary Room':6 }})\n",
        "\n",
        "GRAPH2 = Graph(edgesdict=[ \n",
        "        {NAME: 'e1',  VAL:10, NODE1:'S', NODE2:'A' },\n",
        "        {NAME: 'e2',  VAL: 4, NODE1:'S', NODE2:'B' },\n",
        "        {NAME: 'e3',  VAL: 9, NODE1:'A', NODE2:'C' },\n",
        "        {NAME: 'e4',  VAL: 8, NODE1:'B', NODE2:'C' },\n",
        "        {NAME: 'e5',  VAL: 7, NODE1:'C', NODE2:'D' },\n",
        "        {NAME: 'e6',  VAL: 9, NODE1:'C', NODE2:'E' },\n",
        "        {NAME: 'e7',  VAL: 7, NODE1:'D', NODE2:'E' },\n",
        "        {NAME: 'e8',  VAL:13, NODE1:'D', NODE2:'F' },\n",
        "        {NAME: 'e9',  VAL: 8, NODE1:'E', NODE2:'F' },\n",
        "        {NAME: 'e10', VAL: 5, NODE1:'E', NODE2:'G' },\n",
        "        {NAME: 'e11', VAL:10, NODE1:'F', NODE2:'G' } ],\n",
        "               heuristic={'G':{'S':25, 'A':20, 'B':22, 'C':15, 'D':8, 'E':3, 'F':9}})\n",
        "                   \n",
        "GRAPH3 = Graph(edgesdict=[ \n",
        "        {NAME: 'e1', VAL: 6, NODE1:'S', NODE2:'B' },\n",
        "        {NAME: 'e2', VAL:10, NODE1:'S', NODE2:'A' },\n",
        "        {NAME: 'e3', VAL:10, NODE1:'A', NODE2:'B' },\n",
        "        {NAME: 'e4', VAL: 7, NODE1:'B', NODE2:'C' },\n",
        "        {NAME: 'e5', VAL: 4, NODE1:'A', NODE2:'D' },\n",
        "        {NAME: 'e6', VAL: 2, NODE1:'C', NODE2:'D' },\n",
        "        {NAME: 'e7', VAL: 6, NODE1:'C', NODE2:'G' },\n",
        "        {NAME: 'e8', VAL: 8, NODE1:'G', NODE2:'D' } ],\n",
        "               heuristic={'G':{\"S\":0,\"A\":2,\"B\":5,\"C\":6,\"D\":5}})\n",
        "\n",
        "GRAPH4 = Graph(edgesdict=[\n",
        "        {NAME: 'e1',  VAL:1, NODE1:'S', NODE2:'A' },\n",
        "        {NAME: 'e2',  VAL:1, NODE1:'S', NODE2:'B' },\n",
        "        {NAME: 'e3',  VAL:1, NODE1:'A', NODE2:'B' },\n",
        "        {NAME: 'e4',  VAL:1, NODE1:'C', NODE2:'A' },\n",
        "        {NAME: 'e5',  VAL:1, NODE1:'C', NODE2:'B' },\n",
        "        {NAME: 'e6',  VAL:1, NODE1:'D', NODE2:'C' },\n",
        "        {NAME: 'e7',  VAL:1, NODE1:'D', NODE2:'B' },\n",
        "        {NAME: 'e8',  VAL:1, NODE1:'E', NODE2:'C' },\n",
        "        {NAME: 'e9',  VAL:1, NODE1:'E', NODE2:'D' },\n",
        "        {NAME: 'e10', VAL:1, NODE1:'F', NODE2:'D' },\n",
        "        {NAME: 'e11', VAL:1, NODE1:'F', NODE2:'E' },\n",
        "        {NAME: 'e12', VAL:1, NODE1:'G', NODE2:'E' },\n",
        "        {NAME: 'e13', VAL:1, NODE1:'G', NODE2:'F' } ],\n",
        "               heuristic={\"G\":{\"S\":1,\"A\":3,\"B\":3,\"C\":2,\"D\":2,\"E\":1,\"F\":1}})\n",
        "\n",
        "GRAPH5 = Graph(edgesdict=[\n",
        "        {NAME: 'e1', VAL:  1, NODE1:'S', NODE2:'A' },\n",
        "        {NAME: 'e2', VAL:  1, NODE1:'G', NODE2:'C' },\n",
        "        {NAME: 'e3', VAL:100, NODE1:'B', NODE2:'C' },\n",
        "        {NAME: 'e4', VAL: 10, NODE1:'S', NODE2:'B' },\n",
        "        {NAME: 'e5', VAL: 10, NODE1:'C', NODE2:'A' } ],\n",
        "               heuristic={\"G\":{\"S\":10,\"A\":1000,\"B\":5,\"C\":5}})\n",
        "\n",
        "SAQG = Graph(edgesdict=[\n",
        "    {'NAME': 'SA', 'LENGTH': 1, 'NODE1': 'S', 'NODE2': 'A'},\n",
        "    {'NAME': 'SQ', 'LENGTH': 1, 'NODE1': 'S', 'NODE2': 'Q'},\n",
        "    {'NAME': 'AG', 'LENGTH': 1, 'NODE1': 'A', 'NODE2': 'G'},\n",
        "    {'NAME': 'QG', 'LENGTH': 1, 'NODE1': 'Q', 'NODE2': 'G'},\n",
        "    {'NAME': 'SG', 'LENGTH': 1, 'NODE1': 'S', 'NODE2': 'G'}])\n",
        "\n",
        "NEWGRAPH1 = Graph(edgesdict=[ \n",
        "        { 'NAME': 'e1',  'LENGTH':  6, 'NODE1': 'S', 'NODE2': 'A' },\n",
        "        { 'NAME': 'e2',  'LENGTH':  4, 'NODE1': 'A', 'NODE2': 'B' },\n",
        "        { 'NAME': 'e3',  'LENGTH':  7, 'NODE1': 'B', 'NODE2': 'F' },\n",
        "        { 'NAME': 'e4',  'LENGTH':  6, 'NODE1': 'C', 'NODE2': 'D' },\n",
        "        { 'NAME': 'e5',  'LENGTH':  3, 'NODE1': 'C', 'NODE2': 'A' },\n",
        "        { 'NAME': 'e6',  'LENGTH':  7, 'NODE1': 'E', 'NODE2': 'D' },\n",
        "        { 'NAME': 'e7',  'LENGTH':  6, 'NODE1': 'D', 'NODE2': 'H' },\n",
        "        { 'NAME': 'e8',  'LENGTH':  2, 'NODE1': 'S', 'NODE2': 'C' },\n",
        "        { 'NAME': 'e9',  'LENGTH':  2, 'NODE1': 'B', 'NODE2': 'D' },\n",
        "        { 'NAME': 'e10', 'LENGTH': 25, 'NODE1': 'E', 'NODE2': 'G' },\n",
        "        { 'NAME': 'e11', 'LENGTH':  5, 'NODE1': 'E', 'NODE2': 'C' } ],\n",
        "                  heuristic={\"G\":{'S': 11,\n",
        "                                  'A': 9,\n",
        "                                  'B': 6,\n",
        "                                  'C': 12,\n",
        "                                  'D': 8,\n",
        "                                  'E': 15,\n",
        "                                  'F': 1,\n",
        "                                  'H': 2},\n",
        "                             \"H\":{'S': 11,\n",
        "                                  'A': 9,\n",
        "                                  'B': 6,\n",
        "                                  'D': 12,\n",
        "                                  'E': 8,\n",
        "                                  'F': 15,\n",
        "                                  'G': 14},\n",
        "                             'A':{'S':5, # admissible\n",
        "                                  \"B\":1, # h(d) > h(b)+c(d->b) ...  6 > 1 + 2\n",
        "                                  \"C\":3,\n",
        "                                  \"D\":6,\n",
        "                                  \"E\":8,\n",
        "                                  \"F\":11,\n",
        "                                  \"G\":33,\n",
        "                                  \"H\":12},\n",
        "                             'C':{\"S\":2, # consistent\n",
        "                                  \"A\":3,\n",
        "                                  \"B\":7,\n",
        "                                  \"D\":6,\n",
        "                                  \"E\":5,\n",
        "                                  \"F\":14,\n",
        "                                  \"G\":30,\n",
        "                                  \"H\":12},\n",
        "                             \"D\":{\"D\":3}, # dumb\n",
        "                             \"E\":{} # empty\n",
        "                             })\n",
        "\n",
        "NEWGRAPH2 = Graph(edgesdict=\n",
        "                  [ { 'NAME': 'e1', 'LENGTH': 2, 'NODE1': 'D', 'NODE2': 'F' },\n",
        "                    { 'NAME': 'e2', 'LENGTH': 4, 'NODE1': 'C', 'NODE2': 'E' },\n",
        "                    { 'NAME': 'e3', 'LENGTH': 2, 'NODE1': 'S', 'NODE2': 'B' },\n",
        "                    { 'NAME': 'e4', 'LENGTH': 5, 'NODE1': 'S', 'NODE2': 'C' },\n",
        "                    { 'NAME': 'e5', 'LENGTH': 4, 'NODE1': 'S', 'NODE2': 'A' },\n",
        "                    { 'NAME': 'e6', 'LENGTH': 8, 'NODE1': 'F', 'NODE2': 'G' },\n",
        "                    { 'NAME': 'e7', 'LENGTH': 5, 'NODE1': 'D', 'NODE2': 'C' },\n",
        "                    { 'NAME': 'e8', 'LENGTH': 6, 'NODE1': 'D', 'NODE2': 'H' } ],\n",
        "                  heuristic={\"G\":{'S': 9,\n",
        "                                  'A': 1,\n",
        "                                  'B': 2,\n",
        "                                  'C': 3,\n",
        "                                  'D': 6,\n",
        "                                  'E': 5,\n",
        "                                  'F': 15,\n",
        "                                  'H': 10}})\n",
        "\n",
        "\n",
        "NEWGRAPH3 = Graph(nodes=[\"S\"])\n",
        "\n",
        "\n",
        "NEWGRAPH4 = Graph(nodes=[\"S\",\"A\", \"B\", \"C\", \"D\", \"E\", \"F\", \"H\", \"J\", \"K\",\n",
        "            \"L\", \"T\" ],\n",
        "                 edgesdict = [{ 'NAME': 'eSA', 'LENGTH': 2, 'NODE1': 'S', 'NODE2': 'A' },\n",
        "              { 'NAME': 'eSB', 'LENGTH': 10, 'NODE1': 'S', 'NODE2':'B' },\n",
        "              { 'NAME': 'eBC', 'LENGTH': 5, 'NODE1': 'B', 'NODE2':'C' },\n",
        "              { 'NAME': 'eBF', 'LENGTH': 2, 'NODE1': 'B', 'NODE2':'F' },\n",
        "              { 'NAME': 'eCE', 'LENGTH': 5, 'NODE1': 'C', 'NODE2':'E' },\n",
        "              { 'NAME': 'eCJ', 'LENGTH': 12, 'NODE1': 'C', 'NODE2':'J' },\n",
        "              { 'NAME': 'eFH', 'LENGTH': 8, 'NODE1': 'F', 'NODE2':'H' },\n",
        "              { 'NAME': 'eHD', 'LENGTH': 3, 'NODE1': 'H', 'NODE2':'D' },\n",
        "              { 'NAME': 'eHK', 'LENGTH': 5, 'NODE1': 'H', 'NODE2':'K' },\n",
        "              { 'NAME': 'eKJ', 'LENGTH': 1, 'NODE1': 'K', 'NODE2':'J' },\n",
        "              { 'NAME': 'eJL', 'LENGTH': 4, 'NODE1': 'J', 'NODE2':'L' },\n",
        "              { 'NAME': 'eKT', 'LENGTH': 7, 'NODE1': 'K', 'NODE2':'T' },\n",
        "              { 'NAME': 'eLT', 'LENGTH': 5, 'NODE1': 'L', 'NODE2':'T' },\n",
        "              ],\n",
        "                 heuristic={\"T\":{'S': 10,\n",
        "                                 'A': 6,\n",
        "                                 'B': 5,\n",
        "                                 'C': 2,\n",
        "                                 'D': 5,\n",
        "                                 'E': 1,\n",
        "                                 'F': 100,\n",
        "                                 'H': 2,\n",
        "                                 'J': 3,\n",
        "                                 'K': 100,\n",
        "                                 'L': 4,\n",
        "                                 'T': 0,}})\n",
        "\n",
        "# graph used in a_star test 7,\n",
        "# to differentiate using an extended-list vs not.\n",
        "# the heuristic is admissible but not consistent,\n",
        "# so if you use an extended-list (as you're supposed to),\n",
        "# it won't find an optimal path.\n",
        "AGRAPH = Graph(nodes = ['S', 'A', 'B', 'C', 'G'],\n",
        "               edgesdict = [{'NAME': 'eSA', 'LENGTH': 3, 'NODE1': 'S', 'NODE2': 'A'},\n",
        "                            {'NAME': 'eSB', 'LENGTH': 1, 'NODE1': 'S', 'NODE2': 'B'},\n",
        "                            {'NAME': 'eAB', 'LENGTH': 1, 'NODE1': 'A', 'NODE2': 'B'},\n",
        "                            {'NAME': 'eAC', 'LENGTH': 1, 'NODE1': 'A', 'NODE2': 'C'},\n",
        "                            {'NAME': 'eCG', 'LENGTH': 10, 'NODE1': 'C', 'NODE2': 'G'}],\n",
        "               heuristic = {'G':{'S': 12,\n",
        "                                 'A': 9,\n",
        "                                 'B': 12,\n",
        "                                 'C': 8,\n",
        "                                 'G': 0}})"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sDygfIockBgo"
      },
      "source": [
        "## Tester"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 26,
      "metadata": {
        "id": "lrKIIaM5kC3x"
      },
      "outputs": [],
      "source": [
        "from xmlrpc import client\n",
        "from functools import reduce\n",
        "import traceback\n",
        "import sys\n",
        "import os\n",
        "import tarfile\n",
        "\n",
        "try:\n",
        "    from StringIO import StringIO\n",
        "except ImportError:\n",
        "    from io import StringIO\n",
        "\n",
        "\n",
        "def test_summary(dispindex, ntests):\n",
        "    return \"Test %d/%d\" % (dispindex, ntests)\n",
        "  \n",
        "tests = []\n",
        "\n",
        "def show_result(testsummary, testcode, correct, got, expected, verbosity):\n",
        "    \"\"\" Pretty-print test results \"\"\"\n",
        "    if correct:\n",
        "        if verbosity > 0:\n",
        "            print(\"%s: Correct.\" % testsummary)\n",
        "        if verbosity > 1:\n",
        "            print('\\t', testcode)\n",
        "            print()\n",
        "    else:\n",
        "        print(\"%s: Incorrect.\" % testsummary)\n",
        "        print('\\t', testcode)\n",
        "        print(\"Got:     \", got)\n",
        "        print(\"Expected:\", expected)\n",
        "\n",
        "def show_exception(testsummary, testcode):\n",
        "    \"\"\" Pretty-print exceptions (including tracebacks) \"\"\"\n",
        "    print(\"%s: Error.\" % testsummary)\n",
        "    print(\"While running the following test case:\")\n",
        "    print('\\t', testcode)\n",
        "    print(\"Your code encountered the following error:\")\n",
        "    traceback.print_exc()\n",
        "    print()\n",
        "\n",
        "\n",
        "def get_lab_module():\n",
        "    # Try the easy way first\n",
        "    try:\n",
        "        from tests import lab_number\n",
        "    except ImportError:\n",
        "        lab_number = None\n",
        "        \n",
        "    if lab_number != None:\n",
        "        lab = __import__('lab%s' % lab_number)\n",
        "        return lab\n",
        "        \n",
        "    lab = None\n",
        "\n",
        "    for labnum in xrange(10):\n",
        "        try:\n",
        "            lab = __import__('lab%s' % labnum)\n",
        "        except ImportError:\n",
        "            pass\n",
        "\n",
        "    if lab == None:\n",
        "        raise ImportError(\"Cannot find your lab; or, error importing it.  Try loading it by running 'python labN.py' (for the appropriate value of 'N').\")\n",
        "\n",
        "    if not hasattr(lab, \"LAB_NUMBER\"):\n",
        "        lab.LAB_NUMBER = labnum\n",
        "    \n",
        "    return lab\n",
        "\n",
        "import os\n",
        "def find_attr(module, name):\n",
        "    try:\n",
        "        return getattr(module, name)\n",
        "    except AttributeError:\n",
        "        try:\n",
        "            return getattr(sys.modules[globals()['__name__']], name)\n",
        "        except AttributeError:\n",
        "            for dirname, dirnames, filenames in os.walk(\".\"):\n",
        "                for filename in filenames:\n",
        "                    if \".py\" == filename[-3:]:\n",
        "                        mod = __import__(filename[:-3])\n",
        "                        try:\n",
        "                            return getattr(mod, name)\n",
        "                        except AttributeError:\n",
        "                            continue\n",
        "            raise AttributeError()\n",
        "\n",
        "def type_decode(arg, lab):\n",
        "    \"\"\"\n",
        "    XMLRPC can only pass a very limited collection of types.\n",
        "    Frequently, we want to pass a subclass of 'list' in as a test argument.\n",
        "    We do that by converting the sub-type into a regular list of the form:\n",
        "    [ 'TYPE', (data) ] (ie., AND(['x','y','z']) becomes ['AND','x','y','z']).\n",
        "    This function assumes that TYPE is a valid attr of 'lab' and that TYPE's\n",
        "    constructor takes a list as an argument; it uses that to reconstruct the\n",
        "    original data type.\n",
        "    \"\"\"\n",
        "    if isinstance(arg, list) and len(arg) > 1: # We'll leave tuples reserved for some other future magic\n",
        "        if isinstance(arg[0], list):\n",
        "            return [type_decode(arg[0], lab)] + type_decode(arg[1:], lab)\n",
        "        elif arg[0] in ['Graph', 'IF']:\n",
        "            try:\n",
        "                mytype = arg[0]\n",
        "                data = arg[1:]\n",
        "                return apply(find_attr(lab, mytype), [ type_decode(x, lab) for x in data ])\n",
        "            except AttributeError:\n",
        "                traceback.print_exc()\n",
        "                #return [ type_decode(x, lab) for x in arg ]\n",
        "            except TypeError:\n",
        "                traceback.print_exc()\n",
        "                #return [ type_decode(x, lab) for x in arg ]\n",
        "        else:\n",
        "            return arg\n",
        "    else:\n",
        "        return arg\n",
        "\n",
        "    \n",
        "def type_encode(arg):\n",
        "    \"\"\"\n",
        "    Encode trees as lists in a way that can be decoded by 'type_decode'\n",
        "    \"\"\"\n",
        "    if isinstance(arg, list) and not type(arg) in (list,tuple):\n",
        "        return [ arg.__class__.__name__ ] + [ type_encode(x) for x in arg ]\n",
        "    elif hasattr(arg, '__class__') and arg.__class__.__name__ == 'IF':\n",
        "        return [ 'IF', type_encode(arg._conditional), type_encode(arg._action), type_encode(arg._delete_clause) ]\n",
        "    elif hasattr(arg, '__class__') and arg.__class__.__name__ == \"Graph\":\n",
        "        return [ 'Graph', type_encode(arg.nodes), type_encode(arg.edges), type_encode(arg.heuristic) ]\n",
        "    else:\n",
        "        return arg\n",
        "\n",
        "    \n",
        "def run_test(test, lab):\n",
        "    \"\"\"\n",
        "    Takes a 'test' tuple as provided by the online tester\n",
        "    (or generated by the offline tester) and executes that test,\n",
        "    returning whatever output is expected (the variable that's being\n",
        "    queried, the output of the function being called, etc)\n",
        "\n",
        "    'lab' (the argument) is the module containing the lab code.\n",
        "    \n",
        "    'test' tuples are in the following format:\n",
        "      'id': A unique integer identifying the test\n",
        "      'type': One of 'VALUE', 'FUNCTION', 'MULTIFUNCTION', or 'FUNCTION_ENCODED_ARGS'\n",
        "      'attr_name': The name of the attribute in the 'lab' module\n",
        "      'args': a list of the arguments to be passed to the function; [] if no args.\n",
        "      For 'MULTIFUNCTION's, a list of lists of arguments to be passed in\n",
        "    \"\"\"\n",
        "    id, mytype, attr_name, args = test\n",
        "\n",
        "    attr = getattr(lab, attr_name)\n",
        "\n",
        "    if mytype == 'VALUE':\n",
        "        return attr\n",
        "    elif mytype == 'FUNCTION':\n",
        "        return apply(attr, args)\n",
        "    elif mytype == 'MULTIFUNCTION':\n",
        "        return [ run_test( (id, 'FUNCTION', attr_name, FN), lab) for FN in args ]\n",
        "    elif mytype == 'FUNCTION_ENCODED_ARGS':\n",
        "        return run_test( (id, 'FUNCTION', attr_name, type_decode(args, lab)), lab )\n",
        "    else:\n",
        "        raise Exception(\"Test Error: Unknown TYPE '%s'.  Please make sure you have downloaded the latest version of the tester script.  If you continue to see this error, contact a TA.\")\n",
        "\n",
        "\n",
        "def test_offline(verbosity=1):\n",
        "    \"\"\" Run the unit tests in 'tests.py' \"\"\"\n",
        "#    import tests as tests_module\n",
        "    \n",
        "#    tests = [ (x[:-8],\n",
        "#               getattr(tests_module, x),\n",
        "#               getattr(tests_module, \"%s_testanswer\" % x[:-8]),\n",
        "#               getattr(tests_module, \"%s_expected\" % x[:-8]),\n",
        "#               \"_\".join(x[:-8].split('_')[:-1]))\n",
        "#              for x in tests_module.__dict__.keys() if x[-8:] == \"_getargs\" ]\n",
        "\n",
        "#    tests = tests_module.get_tests()\n",
        "    global tests\n",
        "\n",
        "\n",
        "    ntests = len(tests)\n",
        "    ncorrect = 0\n",
        "    \n",
        "    for index, (testname, getargs, testanswer, expected, fn_name, type) in enumerate(tests):\n",
        "        dispindex = index+1\n",
        "        summary = test_summary(dispindex, ntests)\n",
        "        \n",
        "        try:\n",
        "            if callable(getargs):\n",
        "                getargs = getargs()\n",
        "                \n",
        "            answer = fn_name(*getargs)#run_test((index, type, fn_name, getargs), get_lab_module())\n",
        "        except NotImplementedError:\n",
        "            print(\"%d: (%s: Function not yet implemented, NotImplementedError raised)\" % (index, testname))\n",
        "            continue\n",
        "        except Exception:\n",
        "            show_exception(summary, testname)\n",
        "            continue\n",
        "        \n",
        "        correct = testanswer(answer)\n",
        "        show_result(summary, testname, correct, answer, expected, verbosity)\n",
        "        if correct: ncorrect += 1\n",
        "    \n",
        "    print(\"Passed %d of %d tests.\" % (ncorrect, ntests))\n",
        "    tests = []\n",
        "    return ncorrect == ntests\n",
        "\n",
        "\n",
        "def make_test_counter_decorator():\n",
        "    #tests = []\n",
        "    def make_test(getargs, testanswer, expected_val, name = None, type = 'FUNCTION'):\n",
        "        if name != None:\n",
        "            getargs_name = name\n",
        "        elif not callable(getargs):\n",
        "            getargs_name = \"_\".join(getargs[:-8].split('_')[:-1])\n",
        "            getargs = lambda: getargs\n",
        "        else:\n",
        "            getargs_name = \"_\".join(getargs.__name__[:-8].split('_')[:-1])\n",
        "            \n",
        "        tests.append( ( getargs_name,\n",
        "                        getargs,\n",
        "                        testanswer,\n",
        "                        expected_val,\n",
        "                        getargs_name,\n",
        "                        type ) )\n",
        "\n",
        "    def get_tests():\n",
        "        return tests\n",
        "\n",
        "    return make_test, get_tests\n",
        "\n",
        "\n",
        "make_test, get_tests = make_test_counter_decorator()\n",
        "\n",
        "\n",
        "#if __name__ == '__main__':\n",
        "#    test_offline()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jTH3n_SqMh5j"
      },
      "source": [
        "## Tests"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 27,
      "metadata": {
        "id": "Gmr8kKpzMmzc"
      },
      "outputs": [],
      "source": [
        "import random\n",
        "import time\n",
        "\n",
        "############ WARM-UP: BFS and DFS ############\n",
        "\n",
        "def test_code():\n",
        "    do_bfs = True\n",
        "    \n",
        "    try:\n",
        "        bfs(NEWGRAPH1, 'S', 'H')\n",
        "    except NotImplementedError:\n",
        "        do_bfs = False\n",
        "\n",
        "    do_dfs = True\n",
        "\n",
        "    try:\n",
        "        dfs(NEWGRAPH1, 'S', 'H')\n",
        "    except NotImplementedError:\n",
        "        do_dfs = False\n",
        "\n",
        "    if do_bfs:\n",
        "\n",
        "        ### TEST 1-optional ###\n",
        "\n",
        "        def bfs_1_getargs():\n",
        "            # (graph, start, goal, extended=None, queue=None)\n",
        "            return [ NEWGRAPH1, 'S', 'H' ]\n",
        "\n",
        "        def bfs_1_testanswer(val, original_val = None):\n",
        "            if val and len(val) > 0 and isinstance(val[0], dict):\n",
        "                raise Exception(\"Error: Graph functions are supposed to return a list of node *names*, not node dictionaries!\")\n",
        "\n",
        "            return ( val and list(val) == list('SCDH') )\n",
        "\n",
        "        make_test(type = 'FUNCTION',\n",
        "                getargs = bfs_1_getargs,\n",
        "                testanswer = bfs_1_testanswer,\n",
        "                expected_val = list('SCDH'),\n",
        "                name = bfs\n",
        "                )\n",
        "\n",
        "\n",
        "        ### TEST 2-optional ###\n",
        "\n",
        "        def bfs_2_getargs():\n",
        "            return [ NEWGRAPH2, 'A', 'G' ]\n",
        "\n",
        "        def bfs_2_testanswer(val, original_val = None):\n",
        "            return ( val and list(val) == list('ASCDFG') )\n",
        "\n",
        "        make_test(type = 'FUNCTION',\n",
        "                getargs = bfs_2_getargs,\n",
        "                testanswer = bfs_2_testanswer,\n",
        "                expected_val = list('ASCDFG'),\n",
        "                name = bfs\n",
        "                )\n",
        "\n",
        "\n",
        "        ### TEST 3-optional ###\n",
        "\n",
        "        def bfs_3_getargs():\n",
        "            return [ NEWGRAPH3, 'S', 'S' ]\n",
        "\n",
        "        def bfs_3_testanswer(val, original_val = None):\n",
        "            return ( val and list(val) == list('S') )\n",
        "\n",
        "        make_test(type = 'FUNCTION',\n",
        "                getargs = bfs_3_getargs,\n",
        "                testanswer = bfs_3_testanswer,\n",
        "                expected_val = list('S'),\n",
        "                name = bfs\n",
        "                )\n",
        "\n",
        "\n",
        "        ### TEST 4-optional ###\n",
        "\n",
        "        def bfs_4_getargs():\n",
        "            return [ SAQG, 'S', 'G']\n",
        "\n",
        "        def bfs_4_testanswer(val, original_val = None):\n",
        "            return (val and list(val) == list(\"SG\"))\n",
        "\n",
        "        make_test(type = 'FUNCTION',\n",
        "                getargs = bfs_4_getargs,\n",
        "                testanswer = bfs_4_testanswer,\n",
        "                expected_val = list(\"SG\"),\n",
        "                name = bfs)\n",
        "\n",
        "    if do_dfs:\n",
        "\n",
        "        ### TEST 5-optional ###\n",
        "\n",
        "        def dfs_1_getargs():\n",
        "            return [ NEWGRAPH1, 'S', 'H' ]\n",
        "\n",
        "        def dfs_1_testanswer(val, original_val = None):\n",
        "            return ( NEWGRAPH1.is_valid_path(val) and \n",
        "                    len( NEWGRAPH1.get_connected_nodes(val[-1]) ) <= 1 )\n",
        "\n",
        "        make_test(type = 'FUNCTION',\n",
        "                getargs = dfs_1_getargs,\n",
        "                testanswer = dfs_1_testanswer,\n",
        "                expected_val = \"A valid path along NEWGRAPH1\",\n",
        "                name = dfs\n",
        "                )\n",
        "\n",
        "\n",
        "        ### TEST 6-optional ###\n",
        "\n",
        "        def dfs_2_getargs():\n",
        "            return [ NEWGRAPH2, 'A', 'G' ]\n",
        "\n",
        "        def dfs_2_testanswer(val, original_val = None):\n",
        "            return ( NEWGRAPH2.is_valid_path(val) and \n",
        "                    len( NEWGRAPH2.get_connected_nodes(val[-1]) ) <= 1 )\n",
        "\n",
        "        make_test(type = 'FUNCTION',\n",
        "                getargs = dfs_2_getargs,\n",
        "                testanswer = dfs_2_testanswer,\n",
        "                expected_val = \"A valid path along NEWGRAPH1\",\n",
        "                name = dfs\n",
        "                )\n",
        "\n",
        "\n",
        "        ### TEST 7-optional ###\n",
        "\n",
        "        def dfs_3_getargs():\n",
        "            return [ NEWGRAPH3, 'S', 'S' ]\n",
        "\n",
        "        def dfs_3_testanswer(val, original_val = None):\n",
        "            return ( NEWGRAPH3.is_valid_path(val) and \n",
        "                    len( NEWGRAPH3.get_connected_nodes(val[-1]) ) <= 1 )\n",
        "\n",
        "        make_test(type = 'FUNCTION',\n",
        "                getargs = dfs_3_getargs,\n",
        "                testanswer = dfs_3_testanswer,\n",
        "                expected_val = \"A valid path along NEWGRAPH1\",\n",
        "                name = dfs\n",
        "                )\n",
        "\n",
        "\n",
        "        ### TEST 8-optional ###\n",
        "\n",
        "        def dfs_4_getargs():\n",
        "            return [ SAQG, 'S', 'G']\n",
        "\n",
        "        def dfs_4_testanswer(val, original_val = None):\n",
        "            return (val and (list(val) == list(\"SQG\") or \n",
        "                            list(val) == list(\"SAG\") or \n",
        "                            list(val) == list(\"SG\")))\n",
        "\n",
        "        make_test(type = 'FUNCTION',\n",
        "                getargs = dfs_4_getargs,\n",
        "                testanswer = dfs_4_testanswer,\n",
        "                expected_val = str(list(\"SQG\"))+\" or \"+str(list(\"SAG\")),\n",
        "                name = dfs)\n",
        "\n",
        "\n",
        "    ### TEST 1 ###\n",
        "\n",
        "    def path_length_1_getargs():\n",
        "        return [ NEWGRAPH2, list('S') ]\n",
        "\n",
        "    def path_length_1_testanswer(val, original_val = None):\n",
        "        return ( val == 0 )\n",
        "\n",
        "    make_test(type = 'FUNCTION',\n",
        "            getargs = path_length_1_getargs,\n",
        "            testanswer = path_length_1_testanswer,\n",
        "            expected_val = 0,\n",
        "            name = path_length\n",
        "            )\n",
        "\n",
        "\n",
        "    ### TEST 2 ###\n",
        "\n",
        "    def path_length_2_getargs():\n",
        "        return [ NEWGRAPH1, list('SASAS') ]\n",
        "\n",
        "    def path_length_2_testanswer(val, original_val = None):\n",
        "        return ( val == 24 )\n",
        "\n",
        "    make_test(type = 'FUNCTION',\n",
        "            getargs = path_length_2_getargs,\n",
        "            testanswer = path_length_2_testanswer,\n",
        "            expected_val = 24,\n",
        "            name = path_length\n",
        "            )\n",
        "\n",
        "\n",
        "    ### TEST 3 ###\n",
        "\n",
        "    def path_length_3_getargs():\n",
        "        return [ NEWGRAPH2, list('HDCECSBSA') ]\n",
        "\n",
        "    def path_length_3_testanswer(val, original_val = None):\n",
        "        return ( val == 32 )\n",
        "\n",
        "    make_test(type = 'FUNCTION',\n",
        "            getargs = path_length_3_getargs,\n",
        "            testanswer = path_length_3_testanswer,\n",
        "            expected_val = 32,\n",
        "            name = path_length\n",
        "            )\n",
        "\n",
        "\n",
        "    ### TEST 4 ###\n",
        "\n",
        "    def hill_climbing_1_getargs():\n",
        "        return [ NEWGRAPH1, 'S', 'G' ]\n",
        "\n",
        "    def hill_climbing_1_testanswer(val, original_val = None):\n",
        "        return ( val == list('SABDCEG') )\n",
        "\n",
        "    make_test(type = 'FUNCTION',\n",
        "            getargs = hill_climbing_1_getargs,\n",
        "            testanswer = hill_climbing_1_testanswer,\n",
        "            expected_val = list('SABDCEG'),\n",
        "            name = hill_climbing\n",
        "            )\n",
        "\n",
        "\n",
        "    ### TEST 5 ###\n",
        "\n",
        "    def hill_climbing_2_getargs():\n",
        "        return [ NEWGRAPH1, 'F', 'G' ]\n",
        "\n",
        "    def hill_climbing_2_testanswer(val, original_val = None):\n",
        "        return ( val == list('FBDCEG') )\n",
        "\n",
        "    make_test(type = 'FUNCTION',\n",
        "            getargs = hill_climbing_2_getargs,\n",
        "            testanswer = hill_climbing_2_testanswer,\n",
        "            expected_val = list('FBDCEG'),\n",
        "            name = hill_climbing\n",
        "            )\n",
        "\n",
        "\n",
        "    ### TEST 6 ###\n",
        "\n",
        "    def hill_climbing_3_getargs():\n",
        "        return [ NEWGRAPH1, 'H', 'G' ]\n",
        "\n",
        "    def hill_climbing_3_testanswer(val, original_val = None):\n",
        "        return ( val == list('HDBASCEG') )\n",
        "\n",
        "    make_test(type = 'FUNCTION',\n",
        "            getargs = hill_climbing_3_getargs,\n",
        "            testanswer = hill_climbing_3_testanswer,\n",
        "            expected_val = list('HDBASCEG'),\n",
        "            name = hill_climbing\n",
        "            )\n",
        "\n",
        "\n",
        "    ### TEST 7 ###\n",
        "\n",
        "    def hill_climbing_4_getargs():\n",
        "        return [ NEWGRAPH2, 'G', 'H' ]\n",
        "\n",
        "    def hill_climbing_4_testanswer(val, original_val = None):\n",
        "        return ( val == list('GFDH') )\n",
        "\n",
        "    make_test(type = 'FUNCTION',\n",
        "            getargs = hill_climbing_4_getargs,\n",
        "            testanswer = hill_climbing_4_testanswer,\n",
        "            expected_val = list('GFDH'),\n",
        "            name = hill_climbing\n",
        "            )\n",
        "\n",
        "\n",
        "    ### TEST 8 ###\n",
        "\n",
        "    def hill_climbing_5_getargs():\n",
        "        return [ NEWGRAPH2, 'E', 'A' ]\n",
        "\n",
        "    def hill_climbing_5_testanswer(val, original_val = None):\n",
        "        return ( val == list('ECSA') )\n",
        "\n",
        "    make_test(type = 'FUNCTION',\n",
        "            getargs = hill_climbing_5_getargs,\n",
        "            testanswer = hill_climbing_5_testanswer,\n",
        "            expected_val = list('ECSA'),\n",
        "            name = hill_climbing\n",
        "            )\n",
        "\n",
        "\n",
        "    ### TEST 9 ###\n",
        "\n",
        "    def exp_graph(depth):\n",
        "        g = Graph([\"1\"])\n",
        "        goal = 1\n",
        "        for d in range(depth):\n",
        "            nodeids = range(2**(d+1), 2**(d+2))\n",
        "            goal = random.choice(nodeids)\n",
        "            for nodeid in nodeids:\n",
        "                parent = nodeid//2 # intentional integer division\n",
        "                g.add_edge(str(parent), str(nodeid), 1)\n",
        "        best_path = [goal]\n",
        "        while goal > 0:\n",
        "            goal = goal//2 # intentional integer division\n",
        "            best_path.append(goal)\n",
        "        goal = best_path[0]\n",
        "\n",
        "        for nodeid in range(1,2**(depth+1)):\n",
        "            distance = 0\n",
        "            shared_parent = nodeid\n",
        "            while shared_parent not in best_path:\n",
        "                distance += 1\n",
        "                shared_parent = shared_parent // 2 # intentional integer division\n",
        "            g.set_heuristic(str(nodeid), str(goal), distance+best_path.index(shared_parent))\n",
        "        return g\n",
        "\n",
        "    hill_climbing_test_6_graph = exp_graph(10)\n",
        "    hill_climbing_test_6_goal = list(hill_climbing_test_6_graph.heuristic.keys())[0]\n",
        "    hill_climbing_timing = {'START': 0}\n",
        "\n",
        "    def hill_climbing_6_getargs():\n",
        "        hill_climbing_timing[\"START\"] = time.time()\n",
        "        return [hill_climbing_test_6_graph, \"1\", hill_climbing_test_6_goal]\n",
        "\n",
        "    def hill_climbing_6_testanswer(val, original_val = None):\n",
        "        elapsed = time.time() - hill_climbing_timing[\"START\"]\n",
        "        return ( elapsed < 5 and val[-1] == hill_climbing_test_6_goal)\n",
        "\n",
        "    make_test(type = 'FUNCTION',\n",
        "            getargs = hill_climbing_6_getargs,\n",
        "            testanswer = hill_climbing_6_testanswer,\n",
        "            expected_val = (\"hill climbing to take less than one second and get to %s\"\n",
        "                            % hill_climbing_test_6_goal),\n",
        "            name = hill_climbing\n",
        "            )\n",
        "\n",
        "\n",
        "    ### TEST 19 ###\n",
        "\n",
        "    def a_star_1_getargs():\n",
        "        return [ NEWGRAPH3, 'S', 'S' ]\n",
        "\n",
        "    def a_star_1_testanswer(val, original_val = None):\n",
        "        return ( list(val) == list('S') )\n",
        "\n",
        "    make_test(type = 'FUNCTION',\n",
        "            getargs = a_star_1_getargs,\n",
        "            testanswer = a_star_1_testanswer,\n",
        "            expected_val = list('S'),\n",
        "            name = a_star\n",
        "            )\n",
        "\n",
        "\n",
        "    ### TEST 20 ###\n",
        "\n",
        "    def a_star_2_getargs():\n",
        "        return [ NEWGRAPH1, 'S', 'G' ]\n",
        "\n",
        "    def a_star_2_testanswer(val, original_val = None):\n",
        "        return ( list(val) == list('SCEG') )\n",
        "\n",
        "    make_test(type = 'FUNCTION',\n",
        "            getargs = a_star_2_getargs,\n",
        "            testanswer = a_star_2_testanswer,\n",
        "            expected_val = list('SCEG'),\n",
        "            name = a_star\n",
        "            )\n",
        "\n",
        "\n",
        "    ### TEST 21 ###\n",
        "\n",
        "    def a_star_3_getargs():\n",
        "        return [ NEWGRAPH2, 'S', 'G' ]\n",
        "\n",
        "    def a_star_3_testanswer(val, original_val = None):\n",
        "        return ( list(val) == list('SCDFG') )\n",
        "\n",
        "    make_test(type = 'FUNCTION',\n",
        "            getargs = a_star_3_getargs,\n",
        "            testanswer = a_star_3_testanswer,\n",
        "            expected_val = list('SCDFG'),\n",
        "            name = a_star\n",
        "            )\n",
        "\n",
        "\n",
        "    ### TEST 22 ###\n",
        "\n",
        "    def a_star_4_getargs():\n",
        "        return [ NEWGRAPH2, 'E', 'G' ]\n",
        "\n",
        "    def a_star_4_testanswer(val, original_val = None):\n",
        "        return ( list(val) == list('ECDFG') )\n",
        "\n",
        "    make_test(type = 'FUNCTION',\n",
        "            getargs = a_star_4_getargs,\n",
        "            testanswer = a_star_4_testanswer,\n",
        "            expected_val = list('ECDFG'),\n",
        "            name = a_star\n",
        "            )\n",
        "\n",
        "\n",
        "    ### TEST 23 ###\n",
        "\n",
        "    a_star_test_5_graph = exp_graph(11)\n",
        "    a_star_test_5_goal = list(a_star_test_5_graph.heuristic.keys())[0]\n",
        "    a_star_timing = {'START': 0}\n",
        "\n",
        "    def a_star_5_getargs():\n",
        "        a_star_timing[\"START\"] = time.time()\n",
        "        return [a_star_test_5_graph, \"1\", a_star_test_5_goal]\n",
        "\n",
        "    def a_star_5_testanswer(val, original_val = None):\n",
        "        elapsed = time.time() - a_star_timing[\"START\"]\n",
        "        return ( elapsed < 1 and val[-1] == a_star_test_5_goal)\n",
        "\n",
        "    make_test(type = 'FUNCTION',\n",
        "            getargs = a_star_5_getargs,\n",
        "            testanswer = a_star_5_testanswer,\n",
        "            expected_val = (\"a_star to take less than one second and get to %s\"\n",
        "                            % a_star_test_5_goal),\n",
        "            name = a_star\n",
        "            )\n",
        "\n",
        "\n",
        "    ### TEST 24 ###\n",
        "\n",
        "    def a_star_test_6_getargs():\n",
        "        return [NEWGRAPH4, \"S\", \"T\"]\n",
        "\n",
        "    def a_star_test_6_testanswer(val, original_val=None):\n",
        "        return (list(val) == list(\"SBCJLT\"))\n",
        "                \n",
        "    make_test(type = 'FUNCTION_ENCODED_ARGS',\n",
        "            getargs = a_star_test_6_getargs,\n",
        "            testanswer = a_star_test_6_testanswer,\n",
        "            expected_val = \"correct path for the quiz search problem\",\n",
        "            name = a_star\n",
        "            )\n",
        "\n",
        "\n",
        "    ### TEST 25 ###\n",
        "\n",
        "    def a_star_7_getargs():\n",
        "        return [AGRAPH, \"S\", \"G\"]\n",
        "\n",
        "    def a_star_7_testanswer(val, original_val=None):\n",
        "        return (val and list(val) == list('SACG'))\n",
        "                \n",
        "    make_test(type = 'FUNCTION',\n",
        "            getargs = a_star_7_getargs,\n",
        "            testanswer = a_star_7_testanswer,\n",
        "            expected_val = list('SACG'),\n",
        "            name = a_star\n",
        "            )\n",
        "    \n",
        "\n",
        "    ### TEST 26 ###\n",
        "\n",
        "    def is_admissible_1_getargs():\n",
        "        return [ NEWGRAPH1, \"H\" ]\n",
        "\n",
        "    def is_admissible_1_testanswer(val, original_val = None):\n",
        "        return False == bool(val)\n",
        "\n",
        "    make_test(type='FUNCTION',\n",
        "            getargs = is_admissible_1_getargs,\n",
        "            testanswer = is_admissible_1_testanswer,\n",
        "            expected_val = 'False for NEWGRAPH1/H',\n",
        "            name = is_admissible)\n",
        "\n",
        "\n",
        "    ### TEST 27 ###\n",
        "\n",
        "    def is_admissible_2_getargs():\n",
        "        return [ NEWGRAPH1, \"A\" ]\n",
        "\n",
        "    def is_admissible_2_testanswer(val, original_val = None):\n",
        "        return True == bool(val)\n",
        "\n",
        "    make_test(type='FUNCTION',\n",
        "            getargs = is_admissible_2_getargs,\n",
        "            testanswer = is_admissible_2_testanswer,\n",
        "            expected_val = 'True for NEWGRAPH1/A',\n",
        "            name = is_admissible)\n",
        "\n",
        "\n",
        "    ### TEST 28 ###\n",
        "\n",
        "    def is_admissible_3_getargs():\n",
        "        return [ NEWGRAPH1, \"C\" ]\n",
        "\n",
        "    def is_admissible_3_testanswer(val, original_val = None):\n",
        "        return True == bool(val)\n",
        "\n",
        "    make_test(type='FUNCTION',\n",
        "            getargs = is_admissible_3_getargs,\n",
        "            testanswer = is_admissible_3_testanswer,\n",
        "            expected_val = 'True for NEWGRAPH1/C',\n",
        "            name = is_admissible)\n",
        "\n",
        "\n",
        "    ### TEST 29 ###\n",
        "\n",
        "    def is_admissible_4_getargs():\n",
        "        return [ NEWGRAPH1, \"D\" ]\n",
        "\n",
        "    def is_admissible_4_testanswer(val, original_val = None):\n",
        "        return False == bool(val)\n",
        "\n",
        "    make_test(type='FUNCTION',\n",
        "            getargs = is_admissible_4_getargs,\n",
        "            testanswer = is_admissible_4_testanswer,\n",
        "            expected_val = 'False for NEWGRAPH1/D',\n",
        "            name = is_admissible)\n",
        "\n",
        "\n",
        "    ### TEST 30 ###\n",
        "\n",
        "    def is_admissible_5_getargs():\n",
        "        return [ NEWGRAPH1, \"E\" ]\n",
        "\n",
        "    def is_admissible_5_testanswer(val, original_val = None):\n",
        "        return True == bool(val)\n",
        "\n",
        "    make_test(type='FUNCTION',\n",
        "            getargs = is_admissible_5_getargs,\n",
        "            testanswer = is_admissible_5_testanswer,\n",
        "            expected_val = 'True for NEWGRAPH1/E',\n",
        "            name = is_admissible)\n",
        "\n",
        "\n",
        "    ### TEST 31 ###\n",
        "\n",
        "    def is_consistent_1_getargs():\n",
        "        return [ NEWGRAPH1, \"H\" ]\n",
        "\n",
        "    def is_consistent_1_testanswer(val, original_val = None):\n",
        "        return False == bool(val)\n",
        "\n",
        "    make_test(type='FUNCTION',\n",
        "            getargs = is_consistent_1_getargs,\n",
        "            testanswer = is_consistent_1_testanswer,\n",
        "            expected_val = 'False for NEWGRAPH1/H',\n",
        "            name = is_consistent)\n",
        "\n",
        "\n",
        "    ### TEST 32 ###\n",
        "\n",
        "    def is_consistent_2_getargs():\n",
        "        return [ NEWGRAPH1, \"A\" ]\n",
        "\n",
        "    def is_consistent_2_testanswer(val, original_val = None):\n",
        "        return False == bool(val)\n",
        "\n",
        "    make_test(type='FUNCTION',\n",
        "            getargs = is_consistent_2_getargs,\n",
        "            testanswer = is_consistent_2_testanswer,\n",
        "            expected_val = 'False for NEWGRAPH1/A',\n",
        "            name = is_consistent)\n",
        "\n",
        "\n",
        "    ### TEST 33 ###\n",
        "\n",
        "    def is_consistent_3_getargs():\n",
        "        return [ NEWGRAPH1, \"C\" ]\n",
        "\n",
        "    def is_consistent_3_testanswer(val, original_val = None):\n",
        "        return True == bool(val)\n",
        "\n",
        "    make_test(type='FUNCTION',\n",
        "            getargs = is_consistent_3_getargs,\n",
        "            testanswer = is_consistent_3_testanswer,\n",
        "            expected_val = 'True for NEWGRAPH1/C',\n",
        "            name = is_consistent)\n",
        "\n",
        "\n",
        "    ### TEST 34 ###\n",
        "\n",
        "    def is_consistent_4_getargs():\n",
        "        return [ NEWGRAPH1, \"D\" ]\n",
        "\n",
        "    def is_consistent_4_testanswer(val, original_val = None):\n",
        "        return False == bool(val)\n",
        "\n",
        "    make_test(type='FUNCTION',\n",
        "            getargs = is_consistent_4_getargs,\n",
        "            testanswer = is_consistent_4_testanswer,\n",
        "            expected_val = 'False for NEWGRAPH1/D',\n",
        "            name = is_consistent)\n",
        "\n",
        "\n",
        "    ### TEST 35 ###\n",
        "\n",
        "    def is_consistent_5_getargs():\n",
        "        return [ NEWGRAPH1, \"E\" ]\n",
        "\n",
        "    def is_consistent_5_testanswer(val, original_val = None):\n",
        "        return True == bool(val)\n",
        "\n",
        "    make_test(type='FUNCTION',\n",
        "            getargs = is_consistent_5_getargs,\n",
        "            testanswer = is_consistent_5_testanswer,\n",
        "            expected_val = 'True for NEWGRAPH1/E',\n",
        "            name = is_consistent)\n",
        "\n",
        "    test_offline()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TwXioaqEjNxV"
      },
      "source": [
        "# **To be implemented**"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sQWt5opyWhbB"
      },
      "source": [
        "## *Part 1: Non-optimal Searches*"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 28,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Helper function to get path from parent dictionary\n",
        "\n",
        "def backtrack_path(parent, goal: str):\n",
        "    path = [goal]\n",
        "    next_vertex = goal\n",
        "\n",
        "    while parent[next_vertex]:\n",
        "        next_vertex = parent[next_vertex]\n",
        "        path.insert(0, next_vertex)\n",
        "\n",
        "    return path"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3a7ie2nLVy3S"
      },
      "source": [
        "### Warm-up: BFS and DFS"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 29,
      "metadata": {
        "id": "UhlYeFLTV6l_"
      },
      "outputs": [],
      "source": [
        "## Warm-up: BFS and DFS - Solving these assures that you pass this laboratory (with grade = 6)\n",
        "\n",
        "def bfs(graph: Graph, start: str, goal: str):\n",
        "    queue = [start]  \n",
        "    parent = {start: None}  \n",
        "\n",
        "    while queue:\n",
        "        vertex = queue.pop(0)  \n",
        "\n",
        "        if vertex == goal:\n",
        "            return backtrack_path(parent, goal)  \n",
        "\n",
        "        neighbors = [neighbor for neighbor in graph.get_connected_nodes(vertex) if neighbor not in parent]\n",
        "\n",
        "        for neighbor in neighbors:\n",
        "            queue += [neighbor]  \n",
        "            parent[neighbor] = vertex  \n",
        "\n",
        "    return []  \n",
        "\n",
        "\n",
        "\n",
        "def dfs(graph: Graph, start: str, goal: str):\n",
        "    stack = [start]  \n",
        "    parent = {start: None}  \n",
        "    while stack:\n",
        "        vertex = stack.pop() \n",
        "\n",
        "        if vertex == goal:\n",
        "            return backtrack_path(parent, goal)  \n",
        "\n",
        "        neighbors = [neighbor for neighbor in graph.get_connected_nodes(vertex) if neighbor not in parent]\n",
        "\n",
        "        for neighbor in neighbors:\n",
        "            stack += [neighbor]  \n",
        "            parent[neighbor] = vertex  \n",
        "\n",
        "    return []  \n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tkAWQHy7WAZP"
      },
      "source": [
        "### Hill Climbing"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 30,
      "metadata": {
        "id": "97XgtscgWC8V"
      },
      "outputs": [],
      "source": [
        "## Remember that hill-climbing is a modified version of depth-first search.\n",
        "\n",
        "def hill_climbing_paths(graph: Graph, start: str, goal: str):\n",
        "    queue = [[start]]  # Initialize a queue with the start node as the initial path\n",
        "\n",
        "    while queue:\n",
        "        path = queue.pop(0)\n",
        "        vertex = path[-1] \n",
        "\n",
        "        if vertex == goal:\n",
        "            return path\n",
        "\n",
        "        new_paths: list[list[str]] = []\n",
        "        neighbors: list[str] = [neighbor for neighbor in graph.get_connected_nodes(vertex) if neighbor not in path]\n",
        "        \n",
        "        for neighbor in neighbors:\n",
        "            new_paths += [path + [neighbor]]\n",
        "         \n",
        "        new_paths.sort(key=lambda path: graph.get_heuristic(path[-1], goal))\n",
        "        queue = new_paths + queue  \n",
        "\n",
        "    return []\n",
        "\n",
        "\n",
        "def hill_climbing(graph: Graph, start: str, goal: str):\n",
        "    queue = [start]\n",
        "    parent = {start: None}\n",
        "    visited = set()\n",
        "\n",
        "    while queue:\n",
        "        vertex = queue.pop(0)\n",
        "\n",
        "        visited |= {vertex} \n",
        "        if vertex == goal:\n",
        "            return backtrack_path(parent, goal)\n",
        "\n",
        "        queue_temp: list[str] = [] # Initialize a temporary queue for the next level of nodes.\n",
        "        neighbors: list[str] = [neighbor for neighbor in graph.get_connected_nodes(vertex) if neighbor not in visited]\n",
        "       \n",
        "        for neighbor in neighbors:\n",
        "            queue_temp += [neighbor]\n",
        "            parent[neighbor] = vertex\n",
        "\n",
        "        queue_temp.sort(key=lambda vert: graph.get_heuristic(vert, goal))\n",
        "        queue = queue_temp + queue\n",
        "\n",
        "    return []\n",
        "    "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oAxz9e9ZW6k2"
      },
      "source": [
        "## *Part 2: Optimal Searches*"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 31,
      "metadata": {
        "id": "qLB2l1mNXIWc"
      },
      "outputs": [],
      "source": [
        "## Now we're going to try optimal search.  The previous searches haven't\n",
        "## used edge distances in the calculation.\n",
        "\n",
        "## This function takes in a graph and a list of node names, and returns\n",
        "## the sum of edge lengths along the path -- the total distance in the path.\n",
        "\n",
        "def path_length(graph: Graph, path: list[str]) -> int:\n",
        "    path_len = 0\n",
        "    node = path[0]\n",
        "    for next_node in path[1:]:\n",
        "        path_len += graph.get_edge(node, next_node).length\n",
        "        node = next_node\n",
        "\n",
        "    return path_len\n",
        "    "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qBRJNfriXRhg"
      },
      "source": [
        "### A*"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 32,
      "metadata": {
        "id": "oPcNZK3BjQhY"
      },
      "outputs": [],
      "source": [
        "def a_star(graph: Graph, start: str, goal: str) -> list[str]:\n",
        "   \n",
        "    queue = [[start]]\n",
        "    visited = set()\n",
        "\n",
        "    while queue:\n",
        "        path = queue.pop(0)\n",
        "        vertex = path[-1]\n",
        "\n",
        "        visited |= {vertex}\n",
        "\n",
        "        if vertex == goal:\n",
        "            return path\n",
        "\n",
        "        new_paths: list[list[str]] = []\n",
        "        neighbors: list[str] = [neighbor for neighbor in graph.get_connected_nodes(vertex) if neighbor not in visited]\n",
        "        for neighbor in neighbors:\n",
        "            new_paths += [path + [neighbor]]\n",
        "\n",
        "        \n",
        "        queue += new_paths\n",
        "        queue.sort(key=lambda path: path_length(graph, path) + graph.get_heuristic(path[-1], goal))\n",
        "\n",
        "    return []"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NnmqADCRXWk8"
      },
      "source": [
        "### Heuristics: admissible and consistent"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 33,
      "metadata": {
        "id": "q6swE_HWXdkB"
      },
      "outputs": [],
      "source": [
        "## It's useful to determine if a graph has a consistent and admissible\n",
        "## heuristic.  You've seen graphs with heuristics that are\n",
        "## admissible, but not consistent.  Have you seen any graphs that are\n",
        "## consistent, but not admissible?\n",
        "\n",
        "def is_admissible(graph: Graph, goal: str) -> bool:\n",
        "    for node in graph.nodes:\n",
        "        path = a_star(graph, node, goal)\n",
        "\n",
        "        heuristic = graph.get_heuristic(node, goal)\n",
        "        distance = path_length(graph, path)\n",
        "        \n",
        "        if heuristic > distance:\n",
        "            return False\n",
        "    \n",
        "    return True\n",
        "\n",
        "def is_consistent(graph: Graph, goal: str) -> bool:\n",
        "    for node_x in graph.nodes:\n",
        "        for node_y in graph.nodes:\n",
        "            path = a_star(graph, node_x, node_y)\n",
        "\n",
        "            heuristic_x = graph.get_heuristic(node_x, goal)\n",
        "            heuristic_y = graph.get_heuristic(node_y, goal)\n",
        "            distance = path_length(graph, path)\n",
        "\n",
        "            if abs(heuristic_x - heuristic_y) > distance:\n",
        "                return False\n",
        "\n",
        "    return True"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jCykAXsG59uB"
      },
      "source": [
        "# **Test your code**"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 34,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "y2TG_SguLAR1",
        "outputId": "5f882642-a47b-473b-b8b2-af00a32bad47"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Test 1/34: Correct.\n",
            "Test 2/34: Correct.\n",
            "Test 3/34: Correct.\n",
            "Test 4/34: Correct.\n",
            "Test 5/34: Correct.\n",
            "Test 6/34: Correct.\n",
            "Test 7/34: Correct.\n",
            "Test 8/34: Correct.\n",
            "Test 9/34: Correct.\n",
            "Test 10/34: Correct.\n",
            "Test 11/34: Correct.\n",
            "Test 12/34: Correct.\n",
            "Test 13/34: Correct.\n",
            "Test 14/34: Correct.\n",
            "Test 15/34: Correct.\n",
            "Test 16/34: Correct.\n",
            "Test 17/34: Correct.\n",
            "Test 18/34: Correct.\n",
            "Test 19/34: Correct.\n",
            "Test 20/34: Correct.\n",
            "Test 21/34: Correct.\n",
            "Test 22/34: Correct.\n",
            "Test 23/34: Correct.\n",
            "Test 24/34: Correct.\n",
            "Test 25/34: Correct.\n",
            "Test 26/34: Correct.\n",
            "Test 27/34: Correct.\n",
            "Test 28/34: Correct.\n",
            "Test 29/34: Correct.\n",
            "Test 30/34: Correct.\n",
            "Test 31/34: Correct.\n",
            "Test 32/34: Correct.\n",
            "Test 33/34: Correct.\n",
            "Test 34/34: Correct.\n",
            "Passed 34 of 34 tests.\n"
          ]
        }
      ],
      "source": [
        "test_code()"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [
        "Ee3X4yU0ufQ6",
        "ctWPfxUv4GGT",
        "1aDXos7r5bKY",
        "QCvwOt9UjD5O",
        "TwXioaqEjNxV",
        "jCykAXsG59uB"
      ],
      "provenance": []
    },
    "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.9.6"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}