CA1-PacMan.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CA1 - PacMan\n",
    "## Yasaman Jafari - 810195376"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this project I am going to implement a version of Pacman without any ghosts and with two agents."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "import numpy as np\n",
    "import time\n",
    "from queue import PriorityQueue\n",
    "import pandas as pd \n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, I read the game's map."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "%%%%%%\n",
      "%    %\n",
      "%    %\n",
      "%   P%\n",
      "%% %%%\n",
      "%  23%\n",
      "%1 1 %\n",
      "%%% %%\n",
      "%   Q%\n",
      "%%%%%% \n"
     ]
    }
   ],
   "source": [
    "file = open(\"./test cases/test5\", \"r\") \n",
    "map_data = file.read()\n",
    "print(map_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this project, we have a map which consists of 2 agents which are shown with P and Q. There are foods in the map shown with 1, 2 and 3. 3 is edible for both P and Q. P can eat 1 and 2 is poison for it. Q can eat 2 and 1 is poison for it. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Model The Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need to find the steps which leads to a map with no food.\n",
    "\n",
    "We need to find the optimal way of doing this. We can model the problem and change it in order to make it a search problem. Then we can use search strategies to solve the problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To model the problem we need to have the components of a search problem which are the following parts:\n",
    "\n",
    "- Initial State\n",
    "\n",
    "- Actions\n",
    "\n",
    "- Transition model\n",
    "\n",
    "- Goal State\n",
    "\n",
    "- Path Cost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this problem we will have the followings as these components:\n",
    "\n",
    "- Initial State: The map structure as read from the file\n",
    "\n",
    "- Actions: Each agent can move UP, DOWN, RIGHT, and LEFT if its way is not blocked by walls, other agent or the poison for that agent\n",
    "\n",
    "- Transition Model: If an agent goes from one place to another, it will be removed from the previous place and added to the new one in the map. If food exists in the new place, the agent will eat it and the food will no longer appear on the map. After each movement the state will be the new map with the changed mentioned.\n",
    "\n",
    "- Goal State: The goal is to have a map free of food.\n",
    "\n",
    "- Path Cost: The number of movements in order to reach the solution will be the path cost. (The depth of the solution in the search tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to keep the states and do the necessary actions on them, I have defined a class structure called Pacman. This class has the attributes below:\n",
    "\n",
    "- map_data: The string of map (same format with the one read from the input file.)\n",
    "\n",
    "- q_position and p_position: The positions of agents in the map are stored in the class. These positions are only found the first time an object from this class is instantiated. The next time the p_position and q_position is calculated based on the last state and the action. This way we do not search for them each time and we can save some time.\n",
    "\n",
    "- food: Food is the count of food left in the map. Just like agents' positions, this attribute is only calculated once and then calculated based on the previous state and action. (It only gets updated and not calculated from scratch)\n",
    "\n",
    "- eaten and all_food_pos: Eaten shows if a food was eaten in previous step. all_food_pos shows the position of all foods in the previous state. These are only used for A* algorithm to update the food positions. Otherwise food attribute will be sufficient. all_food_pos is only calculated the first time and when some food is eaten in the previous step. If food is eaten in previous state,  the positions for foods will be updated.\n",
    "\n",
    "This is actually the state in our problem and each node keeps an state inside it. The actions needed for the states are implemented as methods of the class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Pacman:\n",
    "    \n",
    "    def __init__(self, map_data, p_position=[], q_position=[], food=-1, eaten=False, all_food_pos=[]):\n",
    "        self.moves = [\"U\", \"R\", \"D\", \"L\"]\n",
    "        self.element_per_line = len(map_data.splitlines()[0]) + 1\n",
    "        self.all_food_pos = all_food_pos\n",
    "        self.eaten = eaten\n",
    "        self.map = map_data\n",
    "        self.all_food = food\n",
    "        if food == -1:\n",
    "            self.all_food = map_data.count(\"1\") + map_data.count(\"2\") + map_data.count(\"3\")\n",
    "        self.p_position, self.q_position = p_position, q_position\n",
    "        if len(p_position) == 0 or len(q_position) == 0:\n",
    "            self.p_position, self.q_position = self.get_agents_position()\n",
    "        \n",
    "    def get_position_in_map(self, pos):\n",
    "        return([int((pos - (pos % self.element_per_line))/self.element_per_line),\n",
    "               (pos % self.element_per_line)])\n",
    "    \n",
    "    def get_position_of_foods(self):\n",
    "        if (self.all_food_pos == [] and self.all_food != 0) or self.eaten == True:\n",
    "            self.eaten = False\n",
    "            self.all_food_pos = [i for i, letter in enumerate(self.map) if letter in [\"1\", \"2\", \"3\"]]\n",
    "            return self.all_food_pos\n",
    "        return self.all_food_pos\n",
    "        \n",
    "    def get_1_dimension_position(self, x, y):\n",
    "        return x * self.element_per_line + y\n",
    "        \n",
    "    def get_agents_position(self):\n",
    "        q_position = self.get_position_in_map(self.map.find(\"Q\"))\n",
    "        p_position = self.get_position_in_map(self.map.find(\"P\"))\n",
    "        return p_position, q_position  \n",
    "    \n",
    "    def get_poison(self, agent_name):\n",
    "        return \"1\" if agent_name == \"Q\" else \"2\"\n",
    "    \n",
    "    def get_other_agent(self, agent_name):\n",
    "        return \"P\" if agent_name == \"Q\" else \"Q\"\n",
    "    \n",
    "    def check_directions(self, agent_name):\n",
    "        poison = self.get_poison(agent_name)\n",
    "        other = self.get_other_agent(agent_name)\n",
    "        position = self.q_position if agent_name == \"Q\" else self.p_position\n",
    "        x, y = position[0], position[1]\n",
    "        up_right_down_left_x = [x-1, x, x+1, x]\n",
    "        up_right_down_left_y = [y, y+1, y, y-1]\n",
    "        return list(map(lambda x, y:not(self.map[self.get_1_dimension_position(x, y)] in ['%', poison, other]), up_right_down_left_x, up_right_down_left_y))\n",
    "        \n",
    "    def get_map_after_movements(self, direction, agent):\n",
    "        poison = self.get_poison(agent)\n",
    "        other = self.get_other_agent(agent)\n",
    "        state = self.map\n",
    "        pos = self.q_position if agent == \"Q\" else self.p_position\n",
    "        x, y = pos[0], pos[1]\n",
    "        new_pos = [x-1, y] if direction == \"U\" else [x, y+1] if direction == \"R\" else [x+1, y] if direction == \"D\" else [x, y-1]\n",
    "        pos_1d = self.get_1_dimension_position(new_pos[0], new_pos[1])\n",
    "        if self.map[pos_1d] in ['%', poison, other]:\n",
    "            return\n",
    "        new_q_position = [new_pos[0], new_pos[1]] if agent == \"Q\" else self.q_position\n",
    "        new_p_position = [new_pos[0], new_pos[1]] if agent == \"P\" else self.p_position\n",
    "        new_pos = self.get_1_dimension_position(new_pos[0], new_pos[1])\n",
    "        state = state.replace(agent, \" \")\n",
    "        new_all_food = self.all_food\n",
    "        eaten = False\n",
    "        if state[new_pos] in [\"1\", \"2\", \"3\"]:\n",
    "            new_all_food = self.all_food - 1\n",
    "            eaten = True\n",
    "        state = state[:new_pos] + agent + state[new_pos + 1:]\n",
    "        return state, new_p_position, new_q_position, new_all_food, eaten, self.all_food_pos\n",
    "    \n",
    "    def get_maps_for_all_possible_moves(self):\n",
    "        q_moves = self.check_directions(\"Q\")\n",
    "        p_moves = self.check_directions(\"P\")\n",
    "        q_maps = [self.get_map_after_movements(self.moves[i], \"Q\") for i in np.where(q_moves)[0].tolist()]\n",
    "        p_maps = [self.get_map_after_movements(self.moves[i], \"P\") for i in np.where(p_moves)[0].tolist()]\n",
    "        return q_maps + p_maps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "pacman_board = Pacman(map_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we create a node class for each node of the search graph. This class has the map state and its parent.Level shows the depth of the current state of the node. Parent is set as default value of -1 now but can be given to the constructor of the node if needed. By having the parent node, we can trace the solution and view the steps which lead to the current state."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    \n",
    "    def __init__(self, state, level, parent=-1):\n",
    "        self.state = state\n",
    "        self.level = level\n",
    "        self.parent = parent\n",
    "        \n",
    "    def __gt__(self, other):\n",
    "        return self.heuristic > other.heuristic\n",
    "        \n",
    "    def set_heuristic(self, heuristic):\n",
    "        self.heuristic = heuristic\n",
    "      "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Search Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I will implement the search algorithms listed below in this project and explain their pros and cons later:\n",
    "\n",
    "- BFS (Breadth First Search)\n",
    "\n",
    "- IDS (Iterative Deepening Search)\n",
    "\n",
    "- A*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### BFS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "BFS or Breadth First Search is a search algorithm which will give us the optimal solution.\n",
    "\n",
    "In BFS, we traverse the tree by expanding the nodes in the closest depth and going to the next depth after visiting all the nodes in the current level. \n",
    "\n",
    "As the nodes are explored based on their depth, it is guarantied that the solution (if found) is optimal. In other words, we go forward according to the depth so if solutions exist in different levels, it will definately find the one with lower depth first."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To implement BFS, I have chosen the initial state(read from input file) as the root and its level is considered 0.\n",
    "\n",
    "In each step, I pop a node from the frontier FIFO queue. Frontier consists of the nodes which are not yet expanded themselves (but their parent is expanded.) Frontier is a FIFO queue because in BFS we choose nodes in FIFO manner.\n",
    "\n",
    "I also have a set called explored. I have chosen the set data structure for it as we can lookup a value in set with time complexity of O(1). \n",
    "\n",
    "After expanding each node, I create the child nodes with a level(depth) of their parent plus one. I check each child node to see if they are the goal state ot not. If the state of a child node is goal, I return it. If it is not, we need to check if it is in frontier or explored. If it is not, we add it to the frontier set. As explored set in only there for this cause, I decided to also add the frontier states to the explored(as well as keeping a separate FIFO queue for it) in order to save time on checking the existance of new child node in these lists. (We will have a set containing both explored and frontier states to check if we need to add the node to frontier.) This is exactly same as checking them separately."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bfs(initial_state):\n",
    "    nodes_count = 1\n",
    "    root = Node(initial_state, 0)\n",
    "    if root.state.all_food == 0:\n",
    "        return root\n",
    "    frontier = collections.deque([root])\n",
    "    explored = set([root.state.map])\n",
    "    while True:\n",
    "        if len(frontier) == 0:\n",
    "            return \"FAIL\", -1, -1\n",
    "        node = frontier.popleft()\n",
    "        states = node.state.get_maps_for_all_possible_moves()\n",
    "        for state, p_pos, q_pos, food, eaten, all_food_pos in states:\n",
    "            child = Node(Pacman(state, p_pos, q_pos, food), node.level + 1)\n",
    "            if not child.state.map in explored:\n",
    "                nodes_count += 1\n",
    "                if child.state.all_food == 0:\n",
    "                    return child, nodes_count, nodes_count\n",
    "                frontier.append(child)\n",
    "                explored.add(child.state.map)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, I run the BFS algorithm and measure the time it takes to complete the search and also find the number of nodes visited in order to find the solution. In order to find the node count, I added a counter to BFS function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--- 0.010934114456176758 seconds ---\n",
      "Solution's Depth:  13\n",
      "Nodes Visited:  308\n",
      "Distinct Nodes Visited:  308\n"
     ]
    }
   ],
   "source": [
    "start_time = time.time()\n",
    "\n",
    "node, nodes_count, distint_nodes_count = bfs(pacman_board)\n",
    "\n",
    "print(\"--- %s seconds ---\" % (time.time() - start_time))\n",
    "\n",
    "print(\"Solution's Depth: \", node.level)\n",
    "print(\"Nodes Visited: \", nodes_count)\n",
    "print(\"Distinct Nodes Visited: \", distint_nodes_count)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### IDS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "IDS or Iterative Deepening Search is a depth-limit version of DFS (Depth First Search). In IDS we start with level (depth) of zero and increase it in every iteration. In the depth of i, we run DFS with maximum depth of i. We repeatedly increase the depth limit until a solution is found."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to implement the DFS algorithm which is called by IDS, I modified the BFS algorithm explained above. The modifications are listed below:\n",
    "\n",
    "- The frontier list is implemented as stack (LIFO) instead of FIFO queue in BFS.\n",
    "\n",
    "- In order to check if I need to add the child node to the frontier, it is not enough to check the state and the depth must also be checked. This is because the fact that we might reach the same state in different depths and we want the one with smaller depth in order to reach the optimal solution.\n",
    "\n",
    "- A level limit is added to the algorithm. I only expand a node if its level is smaller that the level limit. Otherwise the child's depth will be larger that the limit. If node's level is not smaller than the limit level, I onlt pop it from the frontier stack and not expand it.\n",
    "\n",
    "- We check if we have reached the goal after expansion only."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dfs_with_max_level(level, initial_state):\n",
    "    nodes_count = 1\n",
    "    nodes_distinct_count = 1\n",
    "    node = Node(initial_state, 0)\n",
    "    if node.state.all_food == 0:\n",
    "        return node\n",
    "    frontier = [node]\n",
    "    explored = {}\n",
    "    explored[node.state.map] = 0\n",
    "    explored_state = set([node.state.map])\n",
    "    first = True\n",
    "    while True:\n",
    "        if len(frontier) == 0:\n",
    "            return \"FAIL\", nodes_count, nodes_distinct_count\n",
    "        node = frontier.pop()\n",
    "        if node.state.all_food == 0:\n",
    "            return node, nodes_count, nodes_distinct_count\n",
    "        if node.level >= level:\n",
    "            continue\n",
    "        states = node.state.get_maps_for_all_possible_moves()\n",
    "        for state, p_pos, q_pos, food, eaten, all_food_pos in states:\n",
    "            child = Node(Pacman(state, p_pos, q_pos, food), node.level + 1)\n",
    "            if not child.state.map in explored or explored[child.state.map] > child.level:\n",
    "                nodes_count += 1\n",
    "                frontier.append(child)\n",
    "                explored[child.state.map] = child.level\n",
    "                if not child.state.map in explored_state:\n",
    "                    explored_state.add(child.state.map)\n",
    "                    nodes_distinct_count += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "IDS algorithm starts with level 0 and calls DFS function with that. It will increase the level limit until a solution is found. If DFS finds a solution in some level, IDS will return its solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ids(initial_state):\n",
    "    level = 0\n",
    "    all_nodes_count = 0\n",
    "    while True:\n",
    "        result, nodes_count, nodes_distinct_count = dfs_with_max_level(level, initial_state)\n",
    "        all_nodes_count += nodes_count\n",
    "        if result != \"FAIL\":\n",
    "            break\n",
    "        level += 1\n",
    "    return result, all_nodes_count, nodes_distinct_count"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, I run the IDS algorithm and measure the time it takes to complete the search and also find the number of nodes visited in order to find the solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--- 0.07356595993041992 seconds ---\n",
      "Solution's Depth:  13\n",
      "Nodes Visited:  2451\n",
      "Distinct Nodes Visited:  264\n"
     ]
    }
   ],
   "source": [
    "start_time = time.time()\n",
    "\n",
    "node, all_nodes_count, nodes_count = ids(pacman_board)\n",
    "\n",
    "print(\"--- %s seconds ---\" % (time.time() - start_time))\n",
    "\n",
    "print(\"Solution's Depth: \", node.level)\n",
    "print(\"Nodes Visited: \", all_nodes_count)\n",
    "print(\"Distinct Nodes Visited: \", nodes_count)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A* is an informed search algorithm. In A* we use a heuristic function as well as trying not to expand the paths which have already cost us a lot. \n",
    "\n",
    "Heuristic function h(n) estimates the cost of reaching goal from node n.\n",
    "\n",
    "A* will give us the optimal solution if:\n",
    "\n",
    "- The heuristic function is admissible - for tree search\n",
    "\n",
    "- The heuristic function is consistent - for graph search\n",
    "\n",
    "A* chooses the node with minimum value of f(n) = g(n) + h(n) in each step to expand. g(n) is the actual cost so far to reach node n and h(n) is the estmated cost to goal from node n."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Heuristic Function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For heuristic function, for each food in the map, I calculated its manhattan distance from each agent. Then I got the minimum of its distance from P and Q. This shows the minimum steps (depth) needed for that fruit to be eaten by either P and Q. In reality, it is probably much more than that as there may be obstacles in the way or the agents may choose to go in opposite directions, etc. This way I calculated the minimum steps required for each fruit to be eaten. Then I found the maximum of these values. This value is the minimum steps needed for the fruit which is furthest from both agents to be eaten. In the goal state, this fruit must be eaten for sure and the minimum steps needed for it to be eaten is the value explained above. \n",
    "\n",
    "According to the explanaitions above, this value is admissible because it is not more than the actual value to the goal. Even when only one food exists in the map, this value will be admissible as explained above.\n",
    "\n",
    "This heuristic function is also consistent because for each h(a) and h(b) the actual cost from a to b will always be greater or equal to h(a) - h(b) as the actual cost from a to b if no obstacles exist is the manhattan distance between a and b (and if there are obstacles it will be more). If there are no obstacles and b is in the way of a to goal, the actual distance from a to b will be h(a) - h(b) but as explained in the more realistic cases above, this value is likely to be much larger."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_heuristic(state):\n",
    "    if state.all_food == 0:\n",
    "        return 0\n",
    "    all_food_pos = state.get_position_of_foods()\n",
    "    max_dist = 0\n",
    "    for food in all_food_pos:\n",
    "        food_pos = state.get_position_in_map(food)\n",
    "        x, y = food_pos[0], food_pos[1]\n",
    "        dist_from_p = abs(state.p_position[0] - x) + abs(state.p_position[1] - y)\n",
    "        dist_from_q = abs(state.q_position[0] - x) + abs(state.q_position[1] - y)\n",
    "        max_from_agent = min(dist_from_p, dist_from_q)\n",
    "        if max_dist < max_from_agent:\n",
    "            max_dist = max_from_agent\n",
    "    return max_dist"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to implement A*, we modify the BFS algorithm. The modifications are listed below:\n",
    "\n",
    "- Frontier is implemented as a PriorityQueue. PriorityQueue is actually a heap which keeps the values inside it based on their priority. This way, when we want to pop a node from frontier, the node with smallest value for f(n) will be popped. In frontier, I keep the node objects and in order to handle the comparison for adding/getting a value from heap, I overrided the __gt__ (greater) implementation of node class.\n",
    "\n",
    "- f(n) is computed for each node when created and added to it as an attribute.\n",
    "\n",
    "- We check if a node is goal after expansion of that node and not when it is created.\n",
    "\n",
    "- If we reach a state with lower depth again, we replace the previous one with the one with lower depth."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def a_star(initial_state):\n",
    "    dup_node_count = 0\n",
    "    distinct_node_count = 1\n",
    "    root = Node(initial_state, 0)\n",
    "    if root.state.all_food == 0:\n",
    "        return root, -1, distinct_node_count\n",
    "    frontier = PriorityQueue()\n",
    "    priority_num = get_heuristic(root.state) + root.level\n",
    "    root.set_heuristic(priority_num)\n",
    "    frontier.put(root)\n",
    "    explored = set()\n",
    "    frontier_state = {}\n",
    "    frontier_state[root.state.map] = root.level\n",
    "    while True:\n",
    "        if frontier.empty():\n",
    "            return \"FAIL\", -1, distinct_node_count\n",
    "        node = (frontier.get())\n",
    "        if node.state.all_food == 0:\n",
    "            return node, distinct_node_count + dup_node_count, distinct_node_count\n",
    "        states = node.state.get_maps_for_all_possible_moves()\n",
    "        for state, p_pos, q_pos, food, eaten, all_food_pos in states:\n",
    "            child = Node(Pacman(state, p_pos, q_pos, food, eaten, all_food_pos), node.level + 1)\n",
    "            priority_num = get_heuristic(child.state) + child.level\n",
    "            child.set_heuristic(priority_num)\n",
    "            if not child.state.map in explored:\n",
    "                distinct_node_count += 1\n",
    "                frontier.put(child)\n",
    "                explored.add(child.state.map)\n",
    "            elif child.state.map in frontier_state and frontier_state[child.state.map] > child.level:\n",
    "                dup_node_count += 1\n",
    "                frontier_state[child.state.map] = child.level\n",
    "                frontier.put(child)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, I run the A* algorithm and measure the time it takes to complete the search and also find the number of nodes visited in order to find the solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--- 0.016764163970947266 seconds ---\n",
      "Solution's Depth:  13\n",
      "Nodes Visited:  271\n",
      "Distinct Nodes Visited:  271\n"
     ]
    }
   ],
   "source": [
    "start_time = time.time()\n",
    "\n",
    "node, all_nodes_count, distinct_node_count = a_star(pacman_board)\n",
    "\n",
    "print(\"--- %s seconds ---\" % (time.time() - start_time))\n",
    "\n",
    "print(\"Solution's Depth: \", node.level)\n",
    "print(\"Nodes Visited: \", all_nodes_count)\n",
    "print(\"Distinct Nodes Visited: \", distinct_node_count)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As it is shown above, the states visited are less than BFS but the execution time is more. This is becuase of the calculations done for the heuristic of each node which take some more time for each node."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Comparison of the Search Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### BFS:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Complete? Yes (If branching factor is finite.)\n",
    "\n",
    "- Optimal? Yes (If cost of the edges are equal.)\n",
    "\n",
    "- Time? O($b^d$) where b is the branching factor and d is the solution's depth.\n",
    "\n",
    "- Space? O($b^d$)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### IDS:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Complete? Yes (If branching factor is finite.)\n",
    "\n",
    "- Optimal? Yes (If cost of the edges are equal.)\n",
    "\n",
    "- Time? (d+1)$b^0$ + (d)$b^1$ + (d-1)$b^2$ + ... + $b^d$ = O($b^d$)\n",
    "\n",
    "- Space? O(bd)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A*:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Complete? Yes \n",
    "\n",
    "- Optimal? Yes \n",
    "\n",
    "- Time? Number of nodes for which f(n) ≤ C* where C* is the optimal path cost (exponential)\n",
    "    It actually depends on the heuristic and it reduces when the heuristic gets closer to the actual cost. \n",
    "\n",
    "- Space? Space is also exponential and it depends on the heuristic and how close it is to the actual cost."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithms' Exectutions with Details"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_mean_exec_and_state_count(count, algorithm, test):\n",
    "    file = open(\"./test cases/\" + test, \"r\") \n",
    "    map_data = file.read()\n",
    "    board = Pacman(map_data)\n",
    "    sum_time = 0\n",
    "    for i in range(count):        \n",
    "        start_time = time.time()\n",
    "\n",
    "        node, all_nodes_count, distinct_count = algorithm(board)\n",
    "\n",
    "        sum_time += (time.time() - start_time)\n",
    "    return (sum_time / count), all_nodes_count, distinct_count, node.level"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below, there is a table which shows the details of each algorithm on each test case."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "time_bfs_1, all_node_bfs_1, distinct_bfs_1, level_bfs_1 = get_mean_exec_and_state_count(3, bfs, \"test1\")\n",
    "time_bfs_2, all_node_bfs_2, distinct_bfs_2, level_bfs_2 = get_mean_exec_and_state_count(3, bfs, \"test2\")\n",
    "time_bfs_3, all_node_bfs_3, distinct_bfs_3, level_bfs_3 = get_mean_exec_and_state_count(3, bfs, \"test3\")\n",
    "time_bfs_4, all_node_bfs_4, distinct_bfs_4, level_bfs_4 = get_mean_exec_and_state_count(3, bfs, \"test4\")\n",
    "time_bfs_5, all_node_bfs_5, distinct_bfs_5, level_bfs_5 = get_mean_exec_and_state_count(3, bfs, \"test5\")\n",
    "time_ids_1, all_node_ids_1, distinct_ids_1, level_ids_1 = get_mean_exec_and_state_count(3, ids, \"test1\")\n",
    "time_ids_2, all_node_ids_2, distinct_ids_2, level_ids_2 = get_mean_exec_and_state_count(3, ids, \"test2\")\n",
    "time_ids_3, all_node_ids_3, distinct_ids_3, level_ids_3 = get_mean_exec_and_state_count(3, ids, \"test3\")\n",
    "time_ids_4, all_node_ids_4, distinct_ids_4, level_ids_4 = get_mean_exec_and_state_count(3, ids, \"test4\")\n",
    "time_ids_5, all_node_ids_5, distinct_ids_5, level_ids_5 = get_mean_exec_and_state_count(3, ids, \"test5\")\n",
    "time_a_star_1, all_node_a_star_1, distinct_a_star_1, level_a_star_1 = get_mean_exec_and_state_count(3, a_star, \"test1\")\n",
    "time_a_star_2, all_node_a_star_2, distinct_a_star_2, level_a_star_2 = get_mean_exec_and_state_count(3, a_star, \"test2\")\n",
    "time_a_star_3, all_node_a_star_3, distinct_a_star_3, level_a_star_3 = get_mean_exec_and_state_count(3, a_star, \"test3\")\n",
    "time_a_star_4, all_node_a_star_4, distinct_a_star_4, level_a_star_4 = get_mean_exec_and_state_count(3, a_star, \"test4\")\n",
    "time_a_star_5, all_node_a_star_5, distinct_a_star_5, level_a_star_5 = get_mean_exec_and_state_count(3, a_star, \"test5\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Solution Depth</th>\n",
       "      <th>Distinct States Viewed</th>\n",
       "      <th>All States Viewed</th>\n",
       "      <th>Exec. Time (sec)</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>BFS - Test1</th>\n",
       "      <td>33</td>\n",
       "      <td>148557</td>\n",
       "      <td>148557</td>\n",
       "      <td>6.155249</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>BFS - Test2</th>\n",
       "      <td>17</td>\n",
       "      <td>3706</td>\n",
       "      <td>3706</td>\n",
       "      <td>0.143780</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>BFS - Test3</th>\n",
       "      <td>20</td>\n",
       "      <td>2672</td>\n",
       "      <td>2672</td>\n",
       "      <td>0.098720</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>BFS - Test4</th>\n",
       "      <td>17</td>\n",
       "      <td>10744</td>\n",
       "      <td>10744</td>\n",
       "      <td>0.443167</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>BFS - Test5</th>\n",
       "      <td>13</td>\n",
       "      <td>308</td>\n",
       "      <td>308</td>\n",
       "      <td>0.007908</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>IDS - Test1</th>\n",
       "      <td>33</td>\n",
       "      <td>142137</td>\n",
       "      <td>4802015</td>\n",
       "      <td>174.376395</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>IDS - Test2</th>\n",
       "      <td>17</td>\n",
       "      <td>3370</td>\n",
       "      <td>37162</td>\n",
       "      <td>1.144594</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>IDS - Test3</th>\n",
       "      <td>20</td>\n",
       "      <td>2598</td>\n",
       "      <td>45496</td>\n",
       "      <td>1.352961</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>IDS - Test4</th>\n",
       "      <td>17</td>\n",
       "      <td>10938</td>\n",
       "      <td>98737</td>\n",
       "      <td>4.004460</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>IDS - Test5</th>\n",
       "      <td>13</td>\n",
       "      <td>264</td>\n",
       "      <td>2451</td>\n",
       "      <td>0.073286</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>A* - Test1</th>\n",
       "      <td>33</td>\n",
       "      <td>84842</td>\n",
       "      <td>84842</td>\n",
       "      <td>7.376521</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>A* - Test2</th>\n",
       "      <td>17</td>\n",
       "      <td>2025</td>\n",
       "      <td>2025</td>\n",
       "      <td>0.133705</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>A* - Test3</th>\n",
       "      <td>20</td>\n",
       "      <td>968</td>\n",
       "      <td>968</td>\n",
       "      <td>0.061281</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>A* - Test4</th>\n",
       "      <td>17</td>\n",
       "      <td>1585</td>\n",
       "      <td>1585</td>\n",
       "      <td>0.090620</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>A* - Test5</th>\n",
       "      <td>13</td>\n",
       "      <td>271</td>\n",
       "      <td>271</td>\n",
       "      <td>0.013446</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "             Solution Depth  Distinct States Viewed  All States Viewed  \\\n",
       "BFS - Test1              33                  148557             148557   \n",
       "BFS - Test2              17                    3706               3706   \n",
       "BFS - Test3              20                    2672               2672   \n",
       "BFS - Test4              17                   10744              10744   \n",
       "BFS - Test5              13                     308                308   \n",
       "IDS - Test1              33                  142137            4802015   \n",
       "IDS - Test2              17                    3370              37162   \n",
       "IDS - Test3              20                    2598              45496   \n",
       "IDS - Test4              17                   10938              98737   \n",
       "IDS - Test5              13                     264               2451   \n",
       "A* - Test1               33                   84842              84842   \n",
       "A* - Test2               17                    2025               2025   \n",
       "A* - Test3               20                     968                968   \n",
       "A* - Test4               17                    1585               1585   \n",
       "A* - Test5               13                     271                271   \n",
       "\n",
       "             Exec. Time (sec)  \n",
       "BFS - Test1          6.155249  \n",
       "BFS - Test2          0.143780  \n",
       "BFS - Test3          0.098720  \n",
       "BFS - Test4          0.443167  \n",
       "BFS - Test5          0.007908  \n",
       "IDS - Test1        174.376395  \n",
       "IDS - Test2          1.144594  \n",
       "IDS - Test3          1.352961  \n",
       "IDS - Test4          4.004460  \n",
       "IDS - Test5          0.073286  \n",
       "A* - Test1           7.376521  \n",
       "A* - Test2           0.133705  \n",
       "A* - Test3           0.061281  \n",
       "A* - Test4           0.090620  \n",
       "A* - Test5           0.013446  "
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = {'Solution Depth':[level_bfs_1, level_bfs_2, level_bfs_3, level_bfs_4, level_bfs_5, \n",
    "                          level_ids_1, level_ids_2, level_ids_3, level_ids_4, level_ids_5,\n",
    "                          level_a_star_1, level_a_star_2, level_a_star_3, level_a_star_4, level_a_star_5], \n",
    "        'Distinct States Viewed':[distinct_bfs_1, distinct_bfs_2, distinct_bfs_3, distinct_bfs_4, distinct_bfs_5,\n",
    "                                 distinct_ids_1, distinct_ids_2, distinct_ids_3, distinct_ids_4, distinct_ids_5, \n",
    "                                 distinct_a_star_1, distinct_a_star_2, distinct_a_star_3, distinct_a_star_4, distinct_a_star_5],\n",
    "        'All States Viewed': [all_node_bfs_1, all_node_bfs_2, all_node_bfs_3, all_node_bfs_4, all_node_bfs_5,\n",
    "                              all_node_ids_1, all_node_ids_2, all_node_ids_3, all_node_ids_4, all_node_ids_5,\n",
    "                              all_node_a_star_1, all_node_a_star_2, all_node_a_star_3, all_node_a_star_4, all_node_a_star_5],\n",
    "        'Exec. Time (sec)': [time_bfs_1, time_bfs_2, time_bfs_3, time_bfs_4, time_bfs_5,\n",
    "                              time_ids_1, time_ids_2, time_ids_3, time_ids_4, time_ids_5,\n",
    "                              time_a_star_1, time_a_star_2, time_a_star_3, time_a_star_4, time_a_star_5]} \n",
    "  \n",
    "df = pd.DataFrame(data, index =['BFS - Test1', 'BFS - Test2', 'BFS - Test3', 'BFS - Test4', 'BFS - Test5', 'IDS - Test1', 'IDS - Test2', 'IDS - Test3', 'IDS - Test4', 'IDS - Test5', 'A* - Test1', 'A* - Test2', 'A* - Test3', 'A* - Test4', 'A* - Test5'])  \n",
    "  \n",
    "df"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Execution Time and Solution Depth Plots"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.rcParams[\"figure.figsize\"][0] = 16\n",
    "plt.rcParams[\"figure.figsize\"][1] = 16"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA6YAAAE9CAYAAAAYvH9CAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nOzdd3xV9f3H8deHJOwNYYNhD5EZhsy4RXHXgSDEtmp/ba221lbrIDiqrbbV2tZWrQKCqAi4FyoJe4W9ZW8II4SRkPX9/ZFLS5URICffm5v38/G4D+4991zOG8FPzuee7/l+zTmHiIiIiIiIiC9lfAcQERERERGR0k2NqYiIiIiIiHilxlRERERERES8UmMqIiIiIiIiXqkxFREREREREa/UmIqIiIiIiIhXakxFRERERETEKzWmUqzMbKOZZZrZITPbb2afmFnj0HsjzSw79N6xx62h9/qY2UwzO2Bm+8xshpl18/unERE5uVC9u9TMEs0s77i6tsHM3jCzVt/Z/0dmtsrMDprZLjP71Myq+MovInK2zCw5dJ5X7jvb48wsyVMsCXNqTMWHa5xzlYH6wC7gpePe+6NzrvJxj3fMrCrwcWi/mkBDYARwtLiDi4icpVmhulcNuBTIBFLNrD2AmfUHfg8Mcs5VAdoC7/gKKyJytswsDugLOODa0LaeZvYIEB163S/0WuQ/on0HkNLLOZdlZu8BL5xm11ah/ceFXmcCXwaZTUQkCM65PGAd8FMzawIkAT8AulHQvC4M7bcPGOUrp4jIORgKzAbmAMOA8c652WZWF3gZaAyUA572F1HCka6YijdmVhG4lYLidSprgDwzG2VmA8ysRvDpREQCN5GCqwpQcAJ3hZmNMLPe3x3+JiJSggwFxoYeV4QaUii4gnpM3ndei6gxFS/eN7N04ABwGfDcce/92szSQ489AM65DKAPBQXsVSDNzD48rtCJiJRE2ym4PQHn3DTgRqAL8Amw18z+bGZRHvOJiJwRM+sDnAe865xLpWCEyO1m1hPoAPwf8DYwGbjPW1AJS2pMxYfrnXPVgfLAz4EUM6sXeu9551z10KP2sQ8451Y65xKdc42A9kADTj8EWEQknDUE9h174Zz7zDl3DQXN6nVAIvBjP9FERM7KMOBL59ye0Ou3gGHOudnOuaeAXADnXIpz7ve+Qkp40j2m4k3oXquJZvYvCq6IFvZzq8xsJHBPUNlERIrBDcC07250zuUDX5vZNxR8ESciEvbMrAJwCxBlZjtDm8sB1c2so3NusXNuIwX31ot8j66YijdW4DqgBrDyFPu1MbMHzKxR6HVjYBCnvzdVRCSsmFmUmTU1s5eABApmGMfMrjOz28ysRqg2dgf6ozonIiXH9RTcO9oO6BR6tKXgC7ihHnNJCaHGVHz4yMwOARkUzMg2zDm3/BT7HwR6AHPM7DAFJ2rLgAcCTyoiUjQuPK7uJQNVgW7OuaWh9/cDdwHfhvYZAzznnBvrIauIyNkYBrzhnNvsnNt57AH8DRhsZhqpKadkzmlCLBEREREREfFHV0xFRERERETEKzWmIiIiIiIi4pUaUxEREREREfFKjamIiIiIiIh4pcZUREREREREvAqraZtr167t4uLifMcQkTCSmpq6xzkX6ztHUVKtE5HvUq0TkdLgVLUurBrTuLg45s+f7zuGiIQRM9vkO0NRU60Tke9SrROR0uBUtU5DeUVERERERMQrNaYiIiIiIiLilRpTERERERER8UqNqYiIiIiIiHilxlRERERERES8UmMqIiIiIiIiXqkxFREREREREa/UmIqIiIiIiIhXakxFRI5jZq+b2W4zW3bctnfMbFHosdHMFoW2x5lZ5nHv/dNfchEREZGSK9p3ABGRMDMS+Bsw+tgG59ytx56b2Z+AA8ftv84516nY0omIiIhEIDWmIhKY9xdu47kvVrM9PZMG1Svw4BWtub5zQ9+xTsk5N9XM4k70npkZcAtwcXFmEpHwVhJrnYjI2Qiy3qkxFZFAvL9wGw9PXEp2Vg7VDuawDXh44lKAknzC1hfY5Zz79rhtTc1sIZABPOqcm+Ynmoj4cKzWZR3NpUZ6dqTUOhGR73l/4TYenrCEiruO4GqWY1t6ZpHWO91jKiKBeO6L1WTm5NHq2wy6pe6hQmYumTl5PPfFat/RzsUgYNxxr3cATZxznYFfAW+ZWdUTfdDM7jaz+WY2Py0trRiiikhxOFbr4jYdotuCPVQ7kB0JtU5E5Hue+2I1NTYfIn7hXuruzgIo0nqnxlREArE9PZOa+7JosvUwmxtXIrNC9H+2l0RmFg3cCLxzbJtz7qhzbm/oeSqwDmh1os87515xzsU75+JjY2OLI7KIFIPt6ZlUPpRDi/UZ7KxTgQPVyv5nu4hIJNm78xBt1qSzv3pZdtUp/5/tRVXvAm1Mzay6mb1nZqvMbKWZXRjk8UQkfDSqVJb2K9I5VDGab5tX+8/2BtUreEx1Ti4FVjnnth7bYGaxZhYVet4MaAms95RPRDxoULU87ZfvJye6DCvaREStExH5HuccXdZmUCYflrWrAWb/ea+o6l3QV0xfBD53zrUBOgIrAz6eiISJy/fkUD4rj2Xn1yA/qqB4VYiJ4sErWntOdmpmNg6YBbQ2s61m9qPQW7fxv8N4AfoBS0LLx7wH/MQ5t6/40oqIbzfkRVHtYA4r21Qnp2wUUDJqnYjImZj54Wqq7DzChtbVOVLxv9MUFWW9C2zyIzOrRsFJWyKAcy4byA7qeCISPpZO38zWGVtpPqA5yysZGSVopkrn3KCTbE88wbYJwISgM4lIeNqyeg/rPv6W+t0bsKxJRawE1ToRkcLat/MQ7/55Fq261OfKezrz/OQ1JW5W3qZAGvCGmXUEUoH7nHOHAzymiHh2+EAWo59MoWGLmvzqsQR+G7qCICISSXJz8hiZlEzl6uX59e8vJal6+dN/SESkhHHOMfrJFFy+Y+jj/YltVJUbujYK5FhBDuWNBroAL4dmrDwMPPTdnTRTpUhkefu5mRxKzyIxKYEYNaUiEqE+/fdCtn67jyG/60tlNaUiEqGmTVrFyjnbuOm+nsQ2OuHCA0UmyMZ0K7DVOTcn9Po9ChrV/6GZKkUix4Kv1zP387Vc/eMuNGlT23ccEZFAbFqZxmdvLKTn1S3p2D/OdxwRkUDs2X6Q916YTZvuDel7Y9vAjxdYY+qc2wlsMbNjd8NeAqwI6ngi4lfGvkzGPjOdJm1rM+DOzr7jiIgEIic7j5HDk6laswK3PNDLd5xiY2atzWzRcY8MM7vfdy4RCUZ+fsEQXoChj/WjTBk7zSfOXZD3mALcC4w1s7IULKFwZ8DHExEPnHOMfWYaWYezuTMpgahoLZEsIpHp41dT2b5+P/e+eCWVqpbzHafYOOdWA50AQstkbQMmeQ0lIoGZOmEFq+dtZ8gjfalVv0qxHDPQxtQ5twiID/IYIuLf3M/XsmjKRm78RQ8aNK/pO46ISCA2LNvNF6MW0/u61rTv3cR3HJ8uAdY55zb5DiIiRS9tawYTXpxDu56N6HN9m2I7ri5riMg52b/7MG//cQbNO9TlssEX+I4jIhKI7KxcRiYlUz22Ijf/8kLfcXw70brOIhIB8vMdo55IoUyUccej/TALfgjvMWpMReSsOecY89RUcrLzGJaUQJkolRQRiUwf/ms+OzemM/Sx/lSoXNZ3HG9Ct2ddC4w/yftabUGkBEt+dznfLtjBLQ/0oma9ysV6bJ1FishZm/HBapbN3MKN9/agbpNqvuOIiARi3eKdfDVmCf1ubEu7nsGs31eCDAAWOOd2nehNrbYgUnLt2nyAiS/NoX3vxvS6plWxH1+NqYiclb07DjL+L7NoHd+AhFvO9x1HRCQQ2Vm5jByRQs16lbnpvh6+44SDQWgYr0jEyc/LZ9SIZGLKRjHkkeIdwnuMGlMROWPH7j9wDoY+3r9YphAXEfFh0t/nsnvzAYYNT6B8pdI7hBfAzCoBlwETfWcRkaL19bhlrFu8i1t/3YsadSp5yaDGVETOWMr45ayet51bfnUhtRsUzxTiIiLFbU3qdr4Zt4yEW86ndXwD33G8c84dds7Vcs4d8J1FRIrOzo3pfPDyPDr2O48eV7X0lkONqYickYL7D+bSvldjel/X2nccEZFAZB3JYdQTKdRuWIUb7+3uO46ISCDy8/IZmZRM2fLRDP5dXy9DeI9RYyoihZafl8+opGSiY8owpJinEBcRKU6TXprD3u0HSUxKoFyFGN9xREQCMXnMEjYs281tD/amWu2KXrOoMRWRQvvqraWsW7KLWx/s7e3+AxGRoK2at43k8Su4+Lb2tOxc33ccEZFAbF+/nw//OZ/OF8XR7YrmvuOoMRWRwtm+fj8fvDyfThfF0WNAC99xREQCkXU4m9FPpFCnSTWu/5mG8IpIZMrLLRjCW75SWW5/2O8Q3mPUmIrIaf2neFWMYXCYFC8RkSC898Js9u06TGJSAmXLR/uOIyISiC9GL2bTijRuf6gPVWtW8B0HUGMqIoXw+chFYVe8RESK2orZW5k2aRWXDb6A5h3q+o4jIhKIbWv38fErqcRf1oyulzbzHec/1JiKyCltWb2Hj19NpdsVzcOqeImIFKXMQ9mMfjKFenHVufYn8b7jiIgEIi83nzeGT6Fi1XIM+m0f33H+hxpTETmpnOw83hieTOXq5Rn0m96+44iIBGb8n2eRnnaExKQEYsppCK+IRKbP3ljIltV7GfxwHypXL+87zv9QYyoiJ/XJq6lsW7uPoY/1p1K18CpeIiJFZen0zcz4cDVXDOtI0/Z1fMcREQnEltV7+OS1BXQf0ILOFzX1Hed71JiKyAltWLabz0ctpve1rbmgTxPfcUREAnE44yhjnp5Kg+Y1GHhXV99xREQCkZuTx8ikglFwt/26l+84J6TGVES+JzsrlzeGT6F6bEVu/tWFvuOIiATm3ednkrEvkztHXERM2SjfcUREAvHJawvY+u0+hjzSL2xHwakxFZHvef8f89i16QDDHu9PhcplfccpVmb2upntNrNlx21LMrNtZrYo9LjquPceNrO1ZrbazK7wk1pEzsai5I3M/vRbBvywM03a1PYdR0QkEBtXpPH5yEVcOLAVHfud5zvOSakxFZH/sWbBDr4Zt5T+N7ejbY9GvuP4MBK48gTb/+Kc6xR6fApgZu2A24DzQ5/5h5npkotICXAoPYuxz0yjUataXPXDzr7jiIgEIie7YAhv1ZoVuOWB8B4Fp8ZURP4j60gOo0YkU7thVW68t4fvOF4456YC+wq5+3XA2865o865DcBaoHtg4USkyLz93AwOpWeRmJRAdIy+TxKRyPTxK6nsWL+fOx7tR8Uq5XzHOSU1piLyHxP/Ooe92w+SmJRA+YoxvuOEm5+b2ZLQUN8aoW0NgS3H7bM1tE1EwtiCr9cz74t1DLyrK41b1fIdR0QkEBuW7eaL0YvpfV1r2vcO/4ks1ZiKCAArZm8l5b0VXDq4Ay061fMdJ9y8DDQHOgE7gD+d6W9gZneb2Xwzm5+WllbU+USkkDL2ZTL2mek0aVubKxM7+Y4jIhKI7KxcRiYlF0xk+cvwHsJ7jBpTESHzUDajn0yhXlx1rv1JvO84Ycc5t8s5l+ecywde5b/DdbcBjY/btVFo24l+j1ecc/HOufjY2NhgA4vICTnnGPfsdLIOZ5M4PIGoaJ0GiUhk+vBf89m5MZ2hj5WciSxVkUWEd/40k/S0IyQmJVC2fLTvOGHHzOof9/IG4NiMvR8Ct5lZOTNrCrQE5hZ3PhEpnPmT17Pgmw1cc088DVvU9B1HRCQQ6xbv5KsxS+h3Y1va9Sw5E1nqDFSklFs8dROzPlrDgB92pmn7Or7jeGdm44AEoLaZbQWGAwlm1glwwEbgHgDn3HIzexdYAeQCP3PO5fnILSKndmDPEcb9YTpx58dy2ZAOvuOIiAQiOyuXkSNSqFmvMjfdV7ImslRjKlKKHUrPYszTU2nUsiYD7+riO05YcM4NOsHmf59i/6eBp4NLJCLnyjnH2GemcTQzl8QkDeEVkcj1/t/nsnvzAX758tWUr1QyhvAeo8osUoq9/ccZHD5wlMQRF2m5BBGJWHM+W8vilE1c/9Nu1G9a4/QfEBEpgdYs2ME3by8j4eZ2tOlW8hYJUGMqUkqlfrWeeV+u4+ofd9FyCSISsdLTDvPOczNo3qEulwxq7zuOiEggjmYWrEVfq0EVbiiha9EHOpTXzDYCB4E8INc5p+k+RcJAxt4jjH1mGnHtYrVcgohELOccY56eRk52HsOG96dMlL6PPxdmVh14DWhPwT33P3TOzfKbSkQAJr40lz3bDvLAK9eU2LXoi+Me04ucc3uK4TgiUgjOOcb8PnSv1QjdayUikWvWx2tYOn0ztzxwIXXPq+47TiR4EfjcOfcDMysLVPQdSERg9fztJL+7nIsHtadVl/qn/0CY0uRHIqXMnE+/ZXHKJn5wf0/dayUiEWv/rkO88/xMWnSux0W3agjvuTKzakA/IBHAOZcNZPvMJCKQdTibUU+kUKdxVW74WffTfyCMBX2pxAFfmlmqmd0d8LFE5DT27zrE28/NpHlH3WslIpHLOcfoJ6eSn+dIHJ5AmTLmO1IkaAqkAW+Y2UIze83MKvkOJVLaTfjrHPbtOMiw4SV/LfqgG9M+zrkuwADgZ2bW77s7mNndZjbfzOanpaUFHEek9HLOMfqpqeTl5pOYlKB7rUQkYk1/fxUrZm/lpvt6ENuoqu84kSIa6AK87JzrDBwGHvruTjqvEyk+K2ZvZeqElVw6uAMtOtXzHeecBXpm6pzbFvp1NzAJ+N71ZefcK865eOdcfGxsbJBxREq16e+vYsWsrdz4ix7UaVzNdxwRkUDs3XGQ8X+ZTetuDeh3UzvfcSLJVmCrc25O6PV7FDSq/0PndSLFI/NQNqOfTKHuedW49ieRMb9sYI2pmVUysyrHngOXA8uCOp6InNye7QUnam26N6T/D3SiJiKRKT/fMeqJFACGPtZfQ3iLkHNuJ7DFzFqHNl0CrPAYSaRUe++F2aSnHeHOEReV+CG8xwT5p6gLTDKzY8d5yzn3eYDHE5ETyM93jBqRjBkMe1wnaiISuaZNXMnqedsZ/Lu+1G5QxXecSHQvMDY0I+964E7PeURKpWUztzD9/VVcmdiJpu3r+I5TZAJrTJ1z64GOQf3+IlI4ye8uZ03qDoY+1o+a9Sr7jiMiEoi0rRlMeHE27Xo2ou8NbXzHiUjOuUVAZIwZFCmhjhw8yptPTaVBsxoMvLur7zhFSrOfiESwXZvSmfjSHNr3bkyva1uf/gMiIiVQfr5j9BMpWBnjjkf7ERqtJSIScd798ywy9h5hWFICMWWjfMcpUmpMRSJUfl4+I0ekEFMuWidqIhLRkt9dzpoFO7jlgV4aGSIiEWvJtE3M+mgNVyZ2Iq5d5E0upsZUJEJNHrOE9Ut2Meg3vakeq6XmRCQy7dp84L8jQ65p5TuOiEggDh/IYszT02jUsiZX//h7E2JHBDWmIhFo29p9fPjP+XS5uCndrmjuO46ISCDy8/IZNSKZmLJRDHlEI0NEJHK98/xMDu7PZNjwBKJjImsI7zFqTEUiTF5uPiOTkqlQuSy3P9xHJ2oiErG+HreMdYt3ceuve1GjjkaGiEhkWpS8kTmfreWqH3WhSZvavuMERo2pSIT59PWFbF61h9sf7kuVGhV8xxERCcTOjem8/495dOx3Hj2uauk7johIIA6lZzHm99No3KoWV/2ws+84gVJjKhJBNq/aw6f/XkD3AS3ocnFT33FERAKRl5vPG8OnUK5CNIN/11cjQ0QkYo37w3SOZBwlcUQCUdGR3bpF9p9OpBTJyc7jjcenULVmBW57sLfvOCIigZk8Zgkbl6cx6De9qVa7ou84IiKBSP1qPfMnr2fgXV1o1LKW7ziBU2MqEiE+fiWV7ev3c8ej/ahUtZzvOCIigdi+bh8f/atgcrf4yzW5m4hEpox9mbz17HSatK3NFcM6+Y5TLNSYikSA9Ut38cXoxfS5vg3tezfxHUdEJBB5ufm8kZRM+UplGfSQJncTkcjknGPcs9PJOpzNnUmRP4T3mNLxpxSJYNlZuYwcnkyNOpX4wf09fccREQnMF6MWsXnlHm5/qA9Va2pyNxGJTPO/XMeCbzZwzT3xNGhe03ecYqPGVKSEm/T3uezafIBhw/tToXJZ33FERAKxZc1ePn51Ad0ub07XS5v5jiMiEogDe44w7o8zaNq+DpcN6eA7TrFSYypSgq2ev51vxi0j4ZbzadOtoe84IiKByM3JY1RSMpWqleO232hyNxGJTM45xj4zjaOZuSSWoiG8x5SuP61IBMk6nM2oJ1Ko07gqN97b3XeciGFmr5vZbjNbdty258xslZktMbNJZlY9tD3OzDLNbFHo8U9/yUUi12evL2TLmr0MfrgvlauX9x1HRCQQcz5by+KUTVz/027Ui6vuO06xU2MqUkJNeHEO+3YcZNjwBMpViPEdJ5KMBK78zrbJQHvnXAdgDfDwce+tc851Cj1+UkwZRUqNzav28OnrC+kxoAWdEuJ8xxERCUR62mHeeW4GzTvU5ZJB7X3H8UKNqUgJtHzWFqZOXMllQzrQolM933EiinNuKrDvO9u+dM7lhl7OBhoVezCRUignO4+RSclUqVGBW7U+s4hEKOccY56eRk52HsOG96dMVOls0Urnn1qkBDty8Cijn5xK/WY1uPYn8b7jlEY/BD477nVTM1toZilm1tdXKJFI9MmrqWxbu0/rM4tIRJv18RqWTt/MDT/vTt3zSt8Q3mOifQcQkTPzzvMzydh7hP97/nJiyul/4eJkZo8AucDY0KYdQBPn3F4z6wq8b2bnO+cyTvDZu4G7AZo00VqzIqezcfluPh+1mF7XtOKCPvp/RkQi0/5dh3jn+Zm06FyPi24tnUN4j9EVU5ESZFHyRmZ/8i0D7uxMXLtY33FKFTNLBAYCg51zDsA5d9Q5tzf0PBVYB7Q60eedc6845+Kdc/Gxsfq7EzmVnKO5jExKpnpsRW7+1YW+44iIBMI5x+inppKf50gcnkCZMuY7kldqTEVKiEPpWYz5/TQat6rFVT/q7DtOqWJmVwK/Aa51zh05bnusmUWFnjcDWgLr/aQUiRwf/iuVHRvSuePRflSsoiG8IhKZZnywmhWztnLjL3oQ26iq7zjeaRygSAnx1h+mcyTjKPf//SqiY6J8x4lYZjYOSABqm9lWYDgFs/CWAyabGcDs0Ay8/YAnzCwHyAd+4pzbd8LfWEQKZd2SXUwes4Q+N7Th/Asb+44jIhKIvTsOMv4vs2gd34D+P2jnO05YUGMqUgLM+3IdqZPXc91Pu9GoZS3fcSKac27QCTb/+yT7TgAmBJtIpPTIzsplVFIyNepU4gf39fQdR0QkEM45Rj85Fedg6OP9S/0Q3mPUmIqEuQN7jjDuD9OJOz+WK4Z29B1HRCQw7/9jHrs2H+D+f1xNhcplfceR7zCzjcBBIA/Idc5paniRszB1wkpWzd3G4If7ULtBFd9xwoYaU5EwVrCu1VSys3K5c8RFREXrtnARiUzfLtzBN+OW0v/mdrTt3tB3HDm5i5xze3yHECmp9mzLYMKLs2nboyF9b2zrO05Y0VmuSBib/cm3LJm2met/2o16caV3XSsRiWxHM3MYNSKFWg2qcOO9PXzHEREJRH6+Y9QTKVgZY+hj/QnNWyEhakxFwtS+nf9d1+riQRf4jiMiEphJf5tL2tYMhj3en/IVY3zHkZNzwJdmlhpam1lEzkDK+OWsSd3BLb+6kJr1KvuOE3Y0lFckDDnnePOpqeTn5WtdKxGJaKvnb2fKO8u5+Lb2tOrawHccObU+zrltZlaHglnKVznnph6/Q6hhvRugSZMmPjKKhKXdWw4w8aW5tO/VmF7XtvYdJyzpiqlIGJo2cSUrZm/lpvt6al0rEYlYWYezGfVECnUaV+WGn3f3HUdOwzm3LfTrbmAS8L2/NOfcK865eOdcfGxsbHFHFAlL+fmOUSNSiIouw5BH+2kI70kE3piaWZSZLTSzj4M+lkgkSNuawXsvFNwU3+8m3RQvIpFrwl/nsG/HQYYNT6BseQ3iCmdmVsnMqhx7DlwOLPObSqRk+ObtZaxdtJNbf92LGnUq+Y4Ttorjp8B9wEpAl31ETkM3xYtIabFi9lamTljJZUM60KJTPd9x5PTqApNCP5eigbecc5/7jSQS/nZtSuf9v8+lQ98m9Ly6pe84YS3QxtTMGgFXA08DvwryWCKR4Ju3l/Htgh0MG95fN8WLSMTKPJTN6CdTqHteNa79iZbCLAmcc+sBLaYtcgby8/IZOSKFmHLRDHlEQ3hPJ+ihvC8AvwHyAz6OSIm3c2PBN2oX9G3ChQNb+Y4jIhKY916YTXraERKTNIRXRCLXV28tZf2SXQz6TW+q1a7oO07YC6wxNbOBwG7nXOpp9rvbzOab2fy0tLSg4oiEtbzcfEYmJVO2fDR36Bs1EYlgy2ZsZvr7q7j8jg40u6Cu7zgiIoHYvn4/H7w8n04XxdHtiua+45QIQV4x7Q1ca2YbgbeBi81szHd30uxtIjB5zBI2LNutb9REJKIdzjjKm09NpUGzGlxzj4bwikhkysvNZ1RSMuUqRDP4oT664FBIgTWmzrmHnXONnHNxwG3AN865IUEdT6Sk2rZ2Hx/+cz5dL21G/OX6Rk1EItf4P88iY18mw5ISiCkb5TuOiEggvnxzMRtXpHH7Q32oWksXHApL65iKeJSbk8cbw6dQsWo5btc3aiISwRZP3cSsj9dwZWIn4tpphJSIRKZta/fx0b9SCy44XKYLDmeiWBpT51yyc25gcRxLpCT59PWFbFm9lyG/60vl6uV9xxERCcThA1mMeXoqjVrW5Oofd/EdR0QkEMfmDKlYpSyDftvbd5wSR1dMRTzZtDKNz15fSM+rWtIpIc53HBGRwLz9/EwOpWeRmJRAdIyG8IpIZPp85CI2r9rD7Q/1oUqNCr7jlDhqTEU8yDmayxvDk6laqyK3/LqX7zgiIoFZOGUDcz9by9U/7kLj1rV9xxERCcSW1Xv4+NVUul3RnC6XNPMdp0QqVPVYSosAACAASURBVGNqZhXMrHXQYURKiw//lcqO9fu549F+VKpazneciKXaJeLXwf2ZjP39NBq3rsWAOzv7jiMhqo0iRSs3J4+RI1KoXL08tz2oIbxn67SNqZldAywCPg+97mRmHwYdTCRSrVu8k8lvLqbvDW1o36ux7zgRS7VLxL9xf5zBkYPZ3DniIqKiNUgrHKg2ihS9T19fyNY1exn8sOYMOReF+SmRBHQH0gGcc4uApgFmEolYRzNzGJmUTM36VfjB/T19x4l0Sah2iXgzf/I6UievZ+DdXWnYoqbvOPJfSag2ihSZzav2aM6QIlKYxjTHOXfgO9tcEGFEIt2kv81l95YMhj3en/KVyvqOE+lUu0Q8ydh7hLeenU5cu1iuGNrRdxz5X6qNIkUkJ7tg2b8qNSpozpAiUJjGdLmZ3Q5EmVlLM3sJmBlwLpGIs3r+dqa8s5yLb2tP6/gGvuOUBqpdIh445xj77HSOZuYyLClBQ3jDj2qjSBH55NVUtq/TnCFFpTA/Le4FzgeOAuOADOD+IEOJRJrMQ9mMGpFMnSbVuOHn3X3HKS1Uu0Q8mPfFOhZN2ci1P4mnQbMavuPI96k2ihSBjct38/moxfS6phUX9GniO05EiD7dDs65I8AjoYeInIX3XpzNvl2HefC1aylb/rT/20kRONvaZWavAwOB3c659qFtNYF3gDhgI3CLc26/mRnwInAVcARIdM4tKKo/g0hJc2DPEcb9cQZNL6jDZYMv8B1HTkDndSLnLudoLiOTkqkeW5Gbf3Wh7zgRozCz8sab2UQzW2BmS449iiOcSCRYNmMz0yet4vI7OtC8Q13fcUqNc6hdI4Erv7PtIeBr51xL4OvQa4ABQMvQ427g5aJJL1LyOOcY8/RUco7mkjg8gTJRGsIbjnReJ3LuPvxXKjs2pHPHo/2oWEVDeItKYS7djAUeBJYC+cHGEYkshzOO8uZTU2nQrAbX3BPvO05pc1a1yzk31czivrP5OiAh9HwUkAz8NrR9tHPOAbPNrLqZ1XfO7Tin5CIl0OxPvmXJtM3c/Mue1Iur7juOnJzO60TOwbolu5g8Zgl9bmjD+Rdq2b+iVJjGNM05p/WtRM7CO8/NIGNfJj/98xXElI3yHae0KcraVfe4ZnMncOzSd0Ngy3H7bQ1tU2Mqpcr+XYd45/mZtOhUj4tva+87jpyazutEzlJ2Vi6jkpKpUacSP7hPy/4VtcI0psPN7DUKhq8dPbbROTcxsFQiEWDhlA3M+WwtA+/qwnltY33HKY0CqV3OOWdmZ7y0gpndTcFwX5o00SQJEjmcc7z59DTycvMZNry/hvCGP53XiZylD16ex67NB7j/H1dTobKW/StqhWlM7wTaADH8d8iHA1TARE7i4P5Mxv5+Go1b1+KqH3XxHae0KsratevYEF0zqw/sDm3fBhw/jqdRaNv3OOdeAV4BiI+P15qBEjFmfLCa5TO3cNuDvajTuJrvOHJ6Oq8TOQtrF+3k67eW0v/mdrTt3tB3nIhUmMa0m3OudeBJRCKEc463np1O5qFsfvnyQK3h509R1q4PgWHAs6FfPzhu+8/N7G2gB3BA95dKabJv5yHG/2UWrbrWp//N5/uOI4Wj8zqRM3Q0M4dRI5Kp1aAKN97bw3eciFWYM+aZZtYu8CQiEWL+l+tY8PUGrrknnoYtavqOU5qdVe0ys3HALKC1mW01sx9R0JBeZmbfApeGXgN8CqwH1gKvAj8tkuQiJYBzjtFPpODyHcMe70+ZMuY7khSOzutEztD7f5/H7i0ZDHu8P+UrxviOE7EKc8W0J7DIzDZQcC+CUXCbVYdAk4mUQAf2HOGtP4TW8Bui/0U8O6va5ZwbdJK3LjnBvg742bkGFSmJpk1cycq527j9oT7UbljVdxwpvHM6rzOzKGA+sM05NzC4mCLhYU3qdr55exkX39aeVl0b+I4T0QrTmH53PT8ROYGCCUD+u4afhvB6p9olEpA92zJ474XZtO3ekH43tfUdR87MudbG+4CVgL6NkIiXdSSHUU+kUKdxVa7/WTffcSLeSc+czexYwTl4koeIHGfmR2tYOm0zN/y8u9bw80i1SyRY+fmOUU+kYGWMoY/3x0xDeEuCoqiNZtYIuBp4LYiMIuFm4ktz2Lv9IMOGJ1CugobwBu1UV0zfAgYCqRTM1nb8Tx4HNAswl0iJsm/nId7900xadanPRbdqDT/PVLtEApQyfjlrUndwx6P9qFmvsu84UnhFURtfAH4DVCnydCJhZuXcbaSMX8Glgy+gRad6vuOUCqdqTH8G4JxrWkxZREqk/5kAZLgmAAkDql0iAdm95QATX5rL+b0a0/s6TexawpxTbTSzgcBu51yqmSWcYj+t2SwlXuahbEY/kULdJtW47v80hLe4nOomuEnFlkKkBJs6oWACkB/c31MTgIQH1S6RAOTnO0aNSCEqugx3PNJXQ3hLnnOtjb2Ba81sI/A2cLGZjfnuTs65V5xz8c65+NjY2HM8pIgfE16czf7dh0kckUDZ8oWZkkeKwqkaU/3EETmNtK0FE4C069mIvjdqApAwodolEoBvxi1l7aKd3PrrXtSoqyG8JdA51Ubn3MPOuUbOuTjgNuAb59yQIkkmEkZWzN7KtEmruGxIB5pdUNd3nFLlVF8BNDSzv57sTefcLwLII1Ji5OflM3JEMlHRZRj6WD9dPQgfql0iRWznxnTe/8c8OvRtQs+rW/qOI2dHtVHkNI4cPMroJ1Oo37Q6197T1XecUudUjWkmBTfIi8gJfD1uGWsX7iQxKUFXD8KLapdIETr2JVxMuWiGPKIv4UqwIquNzrlkILkofi+RcDL+z7M4sOcIP3n9OmLKaQhvcTvVf/G9zrlRxZZEpATZsWE/7/9jHh37naerB+FHtUukCE0eu5QNS3fzo6cuplrtir7jyNlTbRQ5haXTNzPzozUMuLMTcefX8R2nVDrVPabZxZZCpATJy81n5PBkylWIZvDvNAFIGFLtEiki29fv58N/zqfTRXF0u6K57zhyblQbRU7icMZR3nxqKg2a1+DquzSE15eTNqbOuZ7FGUSkpPhi9GI2rkjj9of66OpBGFLtEikaebn5jEoKfQn3UB99CVfCqTaKnNy7z8/k4P5M7hxxETFlo3zHKbVOdcX0nJhZeTOba2aLzWy5mY0I6lgixWXLmr18/Eoq8Zc1I/4yXT0Qkch17Eu4wQ/3pWotfQknIpFpUfJGZn/6LQN+2JkmbWr7jlOqBXlX71HgYufcITOLAaab2WfOudkBHlMkMLk5eYxMSqZStXIM+m0f33FERAKzbe0+Pn4lla6XNaPrpc18xxERCcSh9CzGPjONRq1qcdUPO/uOU+oFdsXUFTgUehkTerigjicStE9eW8DWNXsZ8ru+VK5e3nccEZFA5OXm88bwKVSsWo7b9SWciESwt5+bwaH0LBKTEoiO0RBe386qMTWzjwu5X5SZLQJ2A5Odc3PO5ngivm1cvpvPRy7iwoGt6Ng/znccOUuFrV0ipdlnbyxky+q9DH64j76EKyVUG6U0WvD1euZ9sY6Bd3WlcatavuMIZ3/F9K7C7OScy3POdQIaAd3NrP139zGzu81svpnNT0tLO8s4IsHJOZrLyKRkqtWuyC0PXOg7jpybQtUukdJqy+o9fPLaArpf2YLOFzX1HUeKj2qjlCoH92fy1rPTadKmNlcmdvIdR0JO25iaWSUzK3Pc6zLAgTM5iHMuHZgCXHmC915xzsU75+JjY2PP5LcVKRYf/HM+OzakM/Sx/lSsUs53HCmkoqhdIqXJsfvoK1cvz20P9vIdRwKi2igC4/4wgyMHs0lMSiAqOrA7G+UMFeZv4mvg+On4KgJfne5DZhZrZtVDzysAlwGrziakiC9rF+3kqzFL6HdTW9r1bOQ7jpyZs6pdIqXVJ68tYOu3+xjySD8qVdMQ3gim2iil2vzJ60j9aj3X3NOVhi1q+o4jxynMrLzlj5vEiNAsu4WZN74+MMrMoihogN91zukeBikxjmbmMDIpmVoNqnDTfVr+rQQ629olUupsXJH23/vo+53nO44ES7VRSq2MvUd469npxLWL5fI7OvqOI99RmMb0sJl1cc4tADCzrkDm6T7knFsCaN5lKbEm/nUOe7Zl8Kt/DqR8xRjfceTMnVXtEiltcrILhvBWrVlB99GXDqqNUio55xj77HSOZuYyTEN4w1JhGtP7gfFmth0woB5wa6CpRDxbOXcbyeNXcMmg9rTq2sB3HDk7ql0ihfDxK6nsWL+fe1+8UvfRlw6qjVIqzftiHYumbOTGX/SgQbMavuPICZy2MXXOzTOzNkDr0KbVzrmcYGOJ+JN5KJvRT6RQ97xqXP+z7r7jyFlS7RI5vQ3LdvPF6MX0vq417Xs38R1HioFqo5RGB/YcYdwfZ9CsQ10uG3yB7zhyEoWZlbci8FvgPufcMiDOzAYGnkzEk/F/mcX+3Ye5c8RFlC1fmEEFEo5Uu0ROLTsrlzeGT6F6bEVu/qWG8JYWqo1S2jjnGPP0VHKO5pI4vD9lojSEN1wV5m/mDSAbOPZTaxvwVGCJRDxaOn0zMz5YzRXDOtK0fR3fceTcqHaJnMKH/5zPrk0HGPZ4fypULus7jhQf1UYpVWZ/8i1Lpm3m+p91p+551X3HkVMoTGPa3Dn3RyAHwDl3hIJ7EkQiyuEDWbz51FQatqjJwLu6+o4j565Ia5eZtTazRcc9MszsfjNLMrNtx22/qqj+ACJBWbtoJ1+NLVgKq20PLYVVyui8TkqN/bsP887zM2nRuR4X39bedxw5jcKMU8wOrUPqAMysOXA00FQiHrz93EwO7s/k5y9cSUzZKN9x5NwVae1yzq0GOoV+rygKrjJMAu4E/uKce/6cE4sUg+ysXEaNSKZm/Src9IsevuNI8dN5nZQKzjnGPDWVvNx8hj3enzJl9P1LuCtMYzoc+BxobGZjgd5AYpChRIrbgm82MPfztVxzT1eatKntO44UjSBr1yXAOufcJjP9oJOSZdLf57J7S2gprEoawlsK6bxOSoWZH65m2cwt3PZgL+o0ruY7jhRCYWblnWxmC4CeFAz1uM85tyfwZCLFJGNfJm89M40mbWsz4E4tvRspAq5dtwHjjnv9czMbCswHHnDO7S+i44gUqTWp2/lm3DIuuvV8WsdrKazSSOd1Uhrs23mId/88i1Zd69P/5vN9x5FCKsysvD9yzu11zn3inPsY2G9mw4shm0jgnHO89cw0Mg9lc6cWW44oQdUuMysLXAuMD216GWhOwTDfHcCfTvK5u81svpnNT0tLO9cYImcs60gOo55IIbZRVW74uZbCKq10XieRzjnH6CdTcPlOQ3hLmMKchV9iZp+aWX0zOx+YDVQJOJdIsZj3xToWTtnItT+Jp0Hzmr7jSNEKqnYNABY453YBOOd2OefynHP5wKvACc/4nXOvOOfinXPxsbGxRRBD5MxMfGkOe7cfZNjw/pSrEOM7jvij8zqJaNMmrWLlnG3cdF9Pajes6juOnIHCDOW93cxuBZYCh4HbnXMzAk8mErD0tMOM+8P0gsWWh3TwHUeKWIC1axDHDeM1s/rOuR2hlzcAy4rgGCJFauXcbaSMX8Elt19Ay871fccRj862NppZeWAqUI6C88f3nHO60iphZc/2g7z3wmzadm9Iv5va+o4jZ6gwQ3lbAvcBE4BNwB2hxZlFSiznHG8+NZWc7DwSkxK02HIECqJ2mVkl4DJg4nGb/2hmS81sCXAR8MtzOYZIUcs8lM3oJ1Ko26Qa1/+0m+844tk51MajwMXOuY4U3LpwpZn1DC6pyJnJzy8YwmsGdzzWD01OWPIUZlbej4CfOee+toK/4V8B8wDdSSwl1owPVrNsxhZu/XUv6jbRTG0Rqshrl3PuMFDrO9vuOKeUIgF778XZ7N99mAdfu5ay5QvzY18i3FnVRuecAw6FXsaEHi7IoCJnYuqEFayet507Hu1HrfoanV4SFeYnVHfnXAb8pyj9ycw+CjaWSHD27jjI+L/MonV8AxJu0fcrEUy1S0q95bO2MH3SKi4f2pHmHer6jiPh4axrY2gN51SgBfB359ycE+xzN3A3QJMmTYostMippG3NYMKLc2h3YSN6X9fadxw5Sycdv2hmvwFwzmWY2c3feTsxyFAiQcnPd4x6IgXnYKhmaotIql0iBY4cPMroJ6dSv2l1rr2nq+844llR1MbQRG+dgEZAdzNrf4J9NNGbFKv8fMfIEclERZdh6KMawluSnerGutuOe/7wd967MoAsIoFLea9gmMfNv+xJ7QYa5hGhVLtEgPF/nkXG3iMkJiUQU05DeKXoaqNzLh2YcqafEwnClHeWsXbhTm554EJq1K3sO46cg1M1pnaS5yd6LRL2dm85wMS/zuH8Xo3pc30b33EkOKpdUuotnb6ZmR+t4YqhHYk7v47vOBIezqk2mlmsmVUPPa9AwURwq4ounsiZ27UpnUl/m8sFfZpw4cBWvuPIOTrVV6juJM9P9FokrOXn5TMyKZnomDLcoWEekU61S0q1wxlHefOpqTRsUZOr79IQXvmPc62N9YFRoftMywDvOuc+LqpwImcqPy+fUSNSiCkbxZBH+urcLgKcqjHtaGYZFHyLViH0nNDr8oEnEylCX721lHWLd3HnExdRo04l33EkWKpdUqq989wMDu7P5OcvXElM2SjfcSR8nFNtdM4tAToHmE/kjHw9bhnrlhSc21WP1bldJDhpY+qc008ziQjb1+/ng5fn0ykhjh4DWviOIwFT7ZLSbFHyRuZ8tpaBd3WhSZvavuNIGFFtlEiyc2M67/9jHh37n6dzuwhyqntMRUq8vNyCIbzlK8Yw+OE+GuYhIhHrUHoWY34/jcatajHgh7qwJSKRKS83nzeGT6FchWgGP6whvJFEjalEtM9HLmLTijRuf6gPVWtV9B1HRCQwb/9xBkcyjjIsKYHoGF0cE5HINHnMEjYuT2PQb3pTrbbO7SKJGlOJWFtW7+HjV1PpdkVzul7azHccEZHApH61nnlfruPqH3ehcatavuOIiARi+7p9fPSv+XS5uCnxlzf3HUeKmBpTiUg52XmMTEqmcvXyDPpNb99xREQCk7Evk7eenU6TtrW5MrGT7zgiIoHIy83njaRkylcqy6CHdHtWJFJjKhHpk1dT2frtPu54tB+VqmkiVhGJTM45xj07nazD2dyZlEBUtH6si0hk+mLUIjav3FNwe1bNCr7jSAD0E0wizoZlu/l81GJ6XdOKDn3P8x1HRCQw879cx4JvNnDNPfE0aF7TdxwRkUBs/XYvH7+6gPjLmun2rAimxlQiSnZWLm8Mn0L12Irc8kAv33FERAJzYM8Rxv1xBk3b1+GyIR18xxERCURebj4jhydTqVo5Bv22j+84EiA1phJRPnh5Hrs2HWDY4/2pULms7zgiIoFwzjH2mWkczcwlUUN4RSSCffr6Qras2cvgh/tSubpuz4pkgf0kM7PGZjbFzFaY2XIzuy+oY4kAfLtwB1+/tZT+N7ejbY9GvuOIiARmzmdrWZyyiet/2o16cdV9xxERCcTmVXv49N8L6DGgBZ0S4nzHkYBFB/h75wIPOOcWmFkVINXMJjvnVgR4TCmlso7kMDIpmVoNqnDjvT18xxERCcz+3Yd557kZNO9Yl0sGtfcdR0QkELk5BSssVKlRgVt/rduzSoPArpg653Y45xaEnh8EVgINgzqelG4T/zqHvdsPkpiUQPmKMb7jiIgEwjnHmKenkpOdx7DhCZSJ0hBeEYlMn7y2gG1r9zHkkb5aYaGUKJafaGYWB3QG5hTH8aR0WTF7KynvreCS2y+gZef6vuOIiARm5kdrWDZjCzfe24O6Tar5jiMiEoiNK9L4fOQiLtQKC6VK4I2pmVUGJgD3O+cyTvD+3WY238zmp6WlBR1HIkzmoWxGP5lCvbjqXPd/3XzHEREJzL6dh3j3TzNp2aU+Cbec7zuOiEggcrILhvBWrVWRW351oe84UowCbUzNLIaCpnSsc27iifZxzr3inIt3zsXHxsYGGUci0Lt/mkl62hESkxIoWz7IW6ZFRPxxzvHmU1Nx+Y5hj/enTBnzHUlEJBAfv5LKjvX7uePRflSsUs53HClGQc7Ka8C/gZXOuT8HdRwpvZZM28TMj9ZwZWInmrav4zuOiEhgpk1axYrZW7npvp7ENqrqO46ISCA2LNvNF6MX0+f6NrTv1dh3HClmQV4x7Q3cAVxsZotCj6sCPJ6UIofSs3jzqak0almTgXd18R1HRCQwe7Yf5L0XZtOme0P63tjWdxwRkUBkZ+UyMimZ6rEV+cH9PX3HEQ8CG/vonJsOaKyRBOLt52ZwKD2LX/x1ANExUb7jiIgEIj/fMfrJFACGPtZPQ3hFJGJ9+K/57NyYzv1/v4oKlcv6jiMeaJ55KXFSv1rPvC/WMfCurjRuXdt3HClFzGyjmS0NjQCZH9pW08wmm9m3oV9r+M4pkWPqhBWsnredm3/Zk1r1q/iOIyISiHWLd/LVmCX0u6ktbXs08h1HPFFjKiVKxt4jvPXsdM5rF8uViZ18x5HS6SLnXCfnXHzo9UPA1865lsDXodci5yxtawYTXpxDu56N6HN9G99xREQCkZ2Vy8gRKdSsX4WbftHDdxzxSI2plBjOOcY+M52sIzkkJiUQFa1/vhIWrgNGhZ6PAq73mEUiRH6+Y9QTKZSJMu54tB8F8wmKiESe9/8+l92bDzDs8f6Ur6QhvKWZzuylxJjz2VoWJW/kuv+Lp0EzjZYULxzwpZmlmtndoW11nXM7Qs93AnVP9EGt2SxnYso7y/h2wQ5u/XUvatar7DuOCGbW2MymmNkKM1tuZvf5ziQl35oFO/jm7WUk3HI+reMb+I4jnmnhRykR9u8+zNt/nEHzjnW59PYLfMeR0quPc26bmdUBJpvZquPfdM45M3Mn+qBz7hXgFYD4+PgT7iMCsGtTOpP+NpcL+jThwoGtfMcROSYXeMA5t8DMqgCpZjbZObfCdzApmbKO5DBqRDK1GlThxnu7+44jYUBXTCXsHVtYPi83n8SkBMpE6Z+t+OGc2xb6dTcwCegO7DKz+gChX3f7SyglXX5ePqNGpBBTNoohj/TVEF4JG865Hc65BaHnB4GVQEO/qaQkm/TSHPZuP0hiUgLlKsT4jiNhQGf4Evamv7+K5TO3cOMvelCncTXfcaSUMrNKoasEmFkl4HJgGfAhMCy02zDgAz8JJRJ8PW4Z65bs4tYHe1M9tpLvOCInZGZxQGdgjt8kUlKtmreN5PEruPi29rTsXN93HAkTGsorYW3P9oOM/8tsWndrQP8ftPMdR0q3usCk0BWsaOAt59znZjYPeNfMfgRsAm7xmFFKsJ0b03n/H/Po2P88egxo4TuOyAmZWWVgAnC/cy7jBO/fDdwN0KRJk2JOJyVB1uFsRj+RQp0m1bj+ZxrCK/+lxlTCVn6+Y9SIZMxg2OP9tbC8eOWcWw90PMH2vcAlxZ9IIklebj5vDJ9CuQrRDPmdhvBKeDKzGAqa0rHOuYkn2kf308vpTHhxDvt2HuLB166lbHm1IvJfGsorYSv53eWsSd3Bzb+8UAvLi0hEmzxmCRuXpzHot32oWqui7zgi32MF35b8G1jpnPuz7zxSMq2YvZWpE1dy6ZAONO9Yz3ccCTNqTCUs7dqUzsSX5tC+d2N6X9fadxwRkcBsW7uPj/41ny6XNCX+sma+44icTG/gDuBiM1sUelzlO5SUHJmHshn9ZAr14qpz7T3xvuNIGNL1cwk7+Xn5jByRQky5aC0sLyIRLS83n5EjkqlQuSy3P9RH9U7ClnNuOqB/oHLWxv9lFulpR/jt69dpCK+ckK6YStiZPGYJ65fsYtBvNCuliES2z0cuYvPKPdz+UB+q1KjgO46ISCCWzdjMjA9Wc8XQjjRtX8d3HAlTakwlrGxft48P/zmfzhfF0e2K5r7jiIgEZsuavXzy2gK6XdGcLpdoCK+IRKbDGUd586mpNGhWg4F3d/UdR8KYGlMJGwWzUoaGtD2sWSlFJHLl5uQxMimZStXKcduDvX3HEREJzPg/zyJjXyaJIxKIKRvlO46EMTWmEjY+e2Mhm1ft4faH+1K1poa0iUjk+vT1hWxds5fBD/elcvXyvuOIiARi8dRNzPp4DQPu7Mx5bWN9x5Ewp8ZUwsLmVXv45LUFdB/Qgi4XN/UdR0QkMJtX7eGz1xfS86qWdEqI8x1HRCQQhw9kMebpqTRqWZOrftTZdxwpAdSYinc52Xm8MXwKVWpU0JA2EYlox9e7W37dy3ccEZHAvP38TA6lZ5GYlEB0jIbwyumpMRXvPn4lle3r9nPHo/2oVLWc7zgiIoH55FXVOxGJfAunbGDuZ2u5+sddaNy6tu84UkKoMRWv1i/dxRejF9P7utZc0KeJ7zgiIoHZsGw3n49aTO9rVe9EJHIdSs9i7DPTady6FgPu1BBeKTw1puJNdlYuI4cnU6NOJW7+5YW+44iIBCbnaC4jk5KpHluRm3+leicikWvcH6ZzJOMod464iKhotRpSePrXIt68//e57Np8gGHD+1OhclnfcUREAvPhP+ezc2M6Qx9TvRORyJX61Xr+v707j5OquvM+/jlVXb3QDd0NNEs3q4AIqIAiEmULiaJo3GIWjSHklWc0yejESeLjkkeBJJMwUbNMjDqaGNy3iGgSI+EZWUVAVkEUZFNotgZ6X6urzvxR1W2zyVa3T/Wt7/v1qlfdvrX9Drfqx/3dc+65K+Zu5cqbz6eof0fX4Ugbo8JUnNi0chf/8/x6xn91CGddUOQ6HBERz2xZu4e5z7zHmGvPYvCoHq7DERHxRMXBWp6bsZjegwuYOHmo63CkDVJhKq2urrqBJ3+6gC49O3DdbSNdhyMi4pmGukZmTl9Ax245XH/7KNfhiIh4wlrL8zMWU1fdwJRpFJRoRAAAG4lJREFU4zWEV06JvjXS6l753TIO7KrkW1PHk5EVch2OiIhnZv9hOfs+KWfyfePIzNYQXhHxpxX/3MKqt7Zx1XdHUHhGvutwpI1SYSqt6v13drBw1gd88aZz6T+sm+twREQ8s2nVbt56YT3jvzJYpyyIiG+V76/h+V+9Td9zunDJTee6DkfaMBWm0mpqKut56mcL6d43j6u/O8J1OCIinqmvDfPk9Pl0KmzPtbdd6DocERFPWGt59peLaKhrZMrU8QSCKi3k1OnbI63mpQffoeJADVOmf55QRprrcEREPDPr98vZXxw7ZSGznU5ZEBF/WvaPzaxd8DFXf+8CuvXJcx2OtHGeFabGmCeMMfuMMeu9+gxpO9Yu2M47f9vE5d8eTp/BBa7DERHxzMYVu5j/0vtMuOFszjyvu+twREQ8UVZSzYv3v02/oV35wg1nuw5HfMDLHtOZwGUevr+0EVVldTzzi0X0PLMTk74z3HU4IiKeaZ51vFcu1/6rZh0XEX+y1vLMfywi3BDhWxrCKwni2bfIWrsQOOjV+0vb8fx/Lqa6vJ4p08eTFgq6DkdExDOv/G4ZB3dXMmXqONIzdcqCiPjTkr9uYt3iT7jutgvp2ivXdTjiEzq8IZ5aMXcLK+Zu5cqbz6fHgE6uwxER8cyGpTubZx3vN1SzjouIPx3cU8VLDy5hwHndGf/VIa7DER9xXpgaY242xqwwxqwoKSlxHY4kUPn+Gp6bsZg+QwqYOHmo63BETosxpqcxZp4xZoMx5n1jzA/i66cZY4qNMWvit0muY5XWV1vVwFM/W0C3PnlcdYtmHRcRf7LW8vTPF2Kjlm/dN45AwLgOSXzE+Tgja+1jwGMAI0aMsI7DkQSx1vLsL2LTh397+ucJpjk/BiJyuhqBH1lrVxlj2gMrjTFz44/9xlr7gMPYxLGXf/MOZSU13PnE1RrCKyK+tXj2h2xYupMb7ryYgh4dXIcjPqNqQTyx9O8fsXahpg8X/7DW7rbWroovVwIfAEVuo5JksP7tT3j7tY1MnDyUvmd3cR2OiGd0xYXUdmB3JS//ZikDLyhk7JcHuw5HfMjLy8U8D7wDDDTG7DTGfMerz5LkUrq3ihcfWEL/4d00fbj4kjGmDzAcWBZfdasx5r34Tlu+s8Ck1VVX1PP0zxdSeEY+V958vutwRLw2E11xISVFo5Ynf7oAgMn3agiveMPLWXlvsNZ2t9aGrLU9rLV/8uqzJHlYa3nqZwuJNEaZounDxYeMMTnAK8Dt1toK4BGgHzAM2A08eIzX6Xx6H3rpwSVUHKxlyvTxhNI167j4m664kLoWzfqAje/u4vrbR9G5sL3rcMSnVDVIQi2a9QEblu7k+ttH6dwD8R1jTIhYUfqstXYWgLV2r7U2Yq2NAo8DR714pbX2MWvtCGvtiIKCgtYLWjyzdsF2lv79Iy7/9nB6D9I2FRF/KtlZwSu/W8qgC4sYc+1ZrsMRH1NhKglTsrOCv/x2KYNGFjH2y4NchyOSUMYYA/wJ+MBa++sW67u3eNq1gM69SgFVZXU884tF9BjQkUnfGe46HJGkodEh/hKNWp766QJMwDD53nHE/isU8YamDpSEOCRx3afEJb50MfBNYJ0xZk183T3ADcaYYYAFtgO3uAlPWtOLDyyhqqyOf/uvy0kLaQivSBNdbcFf5r/0PptW7WbyvWPp2C3HdTjicypMJSHmvbg+lrjuG6fEJb5krV0MHO2IyxutHYu4teqtbSx/czNXfXcEPQd2dh2OiIgn9u0oZ9bvl3H2xT256KqBrsORFKChvHLa9mwv49WHlnPOmF5c9KUzXYcjIuKZytJanvvlInqd1ZnLpgxzHY5Iq9IVF1JHNBJl5rT5hNKD3PSTsRoJJ61CPaZyWiKNUWZOn08oI41vKnGJiM89/59vU1PZwL8/Mp5gmo7tSmqx1t7gOgZpHW+9sJ4ta/fy7enjye+S7TocSRH6X1VOy9xn3mPbun3ceOfF5HZu5zocERHPrJi7hZX/fytfuuV8ivp3dB2OiIgn9mwvY/bD7zJ0bG8unDTAdTiSQlSYyikr3nyQv/73Cs77Ql9GXNrPdTgiIp6pOFDDczMW02dwAZd+c6jrcEREPBGNxEbCpWem8Y17xmgknLQqFaZySiKNUf48dR5Z7TO48a7RSlwi4lvWWp6dsZj62kamTNcQXhHxr7nPrmPbun18/Q6NhJPWp/9d5ZS88adV7Nh4gJvuGUP7/CzX4YiIeGb5m5tZM287V39vBN375rsOR0TEE7u2lvL6oysY/vk+XDBRI+Gk9akwlZP28QclvPHEakZNGsCw8X1chyMi4pmykmpeuH8JZ5zblS/eeI7rcEREPBFpjPLktPlktgtx490awituqDCVkxKub2Tm1Pl06JjFV398ketwREQ8Y63lmV8sIlzfyJSp4wgE9V+miPjTP59ey/YNJdx412g6dNRIOHFDl4txZPbqYu6fs5FdZbUU5mVxx8SBXDO8yHVYx/X6f69k19ZSbvuvy8nukOE6HBERzyz9+0esW/QJX/nh5+jaO891OCIinohNZrmS8y85g/O/eIbrcCSFqTB1YPbqYu6etY7acASA4rJa7p61DiCpi9Mta/cw95n3GH3tWZx9UU/X4YiIeKZ0bxUvPrCE/sO7MeHrZ7sOR0TEE5HGKDOnzaddhwxuvHO063AkxWlckgP3z9lIbThCXmk9PXZWE2qIUBuOcP+cja5DO6aGukZmTl9Ax245fOX2Ua7DERHxjLWWp36+kEhjlClTxxMI6FwrEfGnN2eu4ZMP9/ONu0eTk5fpOhxJceoxdWBXWS0A/bZV0vlgPYM2wv5OmezunkW4vpFQRvJtllcfWs6+T8r54aNXkpmd7jocERHPvP3aRja8s5Ov/9+LKejRwXU4IiKe2LFxP397fCUjL+vP8M/3dR2OiHpMXSjMi51UbixUZafxca8cOlQ2MHRdKT++9Gme/vlCNq3aTTRqHUcas3HFLt56YT0Tvn42A0cUug5HRMQzB3ZX8vJv3mHgiELGXT/YdTgiIp5oDEeYOX0BOXmZfE2TWUqSSL6uuRRwx8SBzeeUhkMBNg3IZcegfH40uJC0TaW8+88tLJ79IZ265zDy8gGMmjSAbn3cTLxRV93Ak9Pn06VXLtfeOtJJDCIircFay1M/W4i1MPm+cRrCKyK+9cYTq9m56QDff/BSDeGVpKHC1IGmCY5eXlFCOByh6LBZeW+482LWzN/O0jc+4s2Za/jHE6vpM7iACycN4IKJ/Wif33rTeL/826Uc3FvNHY9/ifRMfV1ExL8WvvIBHy4v5ht3j6ZzYXvX4YiIeOKTD/fzjydWM+qKAQwd18d1OCLNVGk4cs3wIrb2yScSjvLSXRMOeSwjK8SFlw/gwssHUL6/huVvbmbZGx/x4gNLePk37zDkop6MmjSAc8f09rRYXL9kB4tf/ZBLJw+l39Bunn2OiIhr+4sreOV3Sxl0YRFjrhvkOhwREU+EGyL8eeq82PXof6QhvJJcVJgmudzO7bjkpnO55KZzKd58kKVvfMTyNzezbtEnZGaHOP+LZzBq0gD6D++e0GFn1RX1PP3zhRSekc9Vt5yfsPcVEUk20ajlyekLMAHD5HvHYYyG8IqIP/3t8ZXs2lLKrb+9TNejl6SjwrQNKerfkS//24Vc+68XsHHlbpa98REr5m7l7dc2xs5Hvaw/o644MyHno770wBIqDtTw/QcvTcpZgkVEEmX+S++zadVuJt87lo7dclyHIyLiiW3r9zHnybVcfNVAzhndy3U4IkdQxdEGBYIBBo0sYtDIokPPR31yLf/485rTPh+16f2u/Jfz6D2owIMWiIgkh307ypn1+2WcfVFPLrpqoOtwREQ8Ea5vZOa0+eQVtOMrP/yc63BEjkqFqSOzVxezcnsp4XCEi2e8dcjkRycj0eejVpXV8cwvFtFzYCcmfee8U2maiEiz2auLuX/ORnaV1VJ42ERvrkUjUWZOm09aKMhN/2+shvCKiG+9/ugK9mwv4wcPTSIrR9ejl+SkwtSB2auLuXvWOoY0RgkAxWW1zZePOZ0dttM9H9Vay7O/XERNRT3//vAVBNN0mVsROXVNua42HAESl+sS5a0X1rNl7V6mTBtPfpds1+GIiHhiy9o9zH3mPcZcexaDR/VwHY7IMakwbUUNdY2U7qvm4adXk3eglsz6RhrSgwDUhiPcP2djwnbWTuZ81KYejeiHBzh3fSlnXjeQov4dExKHiKSu++dspDYcIa+snu57aqlPD1CfEeSRmas4LyuD3M7taJ+fSSDY+gfB9mwvY/bD7zJ0bG9GXTGg1T9fRPwlWUeHNNQ1MnP6Ajp2y+H620e5DkfkM6kwTQBrLTWVDZTtq6Z0X/Uh903LpfuqqamoB6Bvi9cezP90RrRdZbUJj+1456Pm9s5lZbsA5R1CXLCxjLIOIf5YXUO/1cVJkVBFpO1qymk9dlZTtKdlfivjP96eBUAgaOjQMYsOnduR17kduS1vBdnNyx06ZiVsFEfTEN70zDS+cc8YDeEVkdPy6sqd3PP8akx9hFBagOKyWu54eS3gfnTI7IffZd8n5dz+8BVkZmsIryQ3FabHEY1EqSyto3RvFWUlNZTurTq0+IyvC9dHjnhth05Z5BVk07mwPf2HdSOvSzb5XbKZ+j+b2NnYSH1GkEiLHa3CvJOfqOhkHO181KdnrqL/xw30ByIBWDckn9pINKG9tyKSmgrzsiiOF6c1WUEWf64rGfUReqSH+NXlgyjfXxO7lVRTfqCWg3ur2fZ+CZUHjzxIZwy075hFbqd25BYcWsDmtSxgO2WRFgoeNZ6mHo30Nfs4c3MFQ//PMHI7t/P030BE2p6GukYqS2upKqujqqyOytK65uWqpvXl9c3LFaV1jI2/tj49wPyx3QlHLdNef9/JvlRTrqvZVsYFK/fTe3xvBo3UPp0kP08LU2PMZcDvgCDwR2vtjES+/+kOmwg3RCgvifdo7q2mrOTIHs/y/TVEI/aQ1wWChvwu2eQVZNNzYCfOHdOLvIJs8rtmN9/ndm53zJ2j7xdlc/esdUTCnxazWaEgd0xsvRkhm85HvXn9DrKrwnTbU0NFh3RqskOAN723In7lda6D5B0m9lk+f1YBzyz9pPlvGzDUZaUxalRPzpvQ95ivizRGqThQ01y4lpXUUN70d0nsfsfGA1QcrMVG7RGvz8nLbNHrGrv/uLaBVzbuIxyJMnhLBXsLMvn9zgMUanSIyAlri7ku0hiluqL+0KKyqdgsr6OqRdHZVIwerbMBYvt/2bmZtM/LJCcvk+5988nJz+TPq3bSEArQ6WAdXfbXM3rJXqIGogHDrz5+jWAoQFp6kLS0+P2xlkNB0kInthwMBQmlH7n8jw17ue9vG6hvaOSiDaXUZgV5LhRhiHKdtAGeFabGmCDwB+ASYCfwrjHmdWvthkS8//Em1aitajj6sNqSasriRWhlad0R75uRlRbr2eyaw8ARhbECNN7T2XSfk5911MmDTlRTYkiGnczCvCyKgc39c49YLyLH53Wug8ROIhRpjNIYjhCujzTfhxsiNDYc5b6+kcZwlHB94yGPHfK8+gjhcPz+sOfsKC5ndDhCRn2UhvRPR4fM+7DkM2MMpgXI75pDftfPvqZo04iW5p7X/TWUlVS36ImtYfe20uYDjIPjr2sIBdgwKI+GRo0OETlRyZDrrLXUVYc/7b0sO7KojBWg8fvyOmoq6rFHHr8CIDM7RE68yMzt3I6i/h3Jyc8kJze2rn1+ZvPjOflZZOWkH3X/7yd3/R2InZ4VDlURiNrmW3pmGuFwhNrKBhobYnm3MRzLw7G/P10+Vpwna0yL5eXnd6baWuU6aRO87DEdCWy21m4FMMa8AFwNJCSBNU2qkV0VpvueWjLrI2TUR3h18W7mRaGuOnzEa3LyMpuLyz5DCsjvmkNeQbtD7jOzQ61yvtE1w4uSIkHcMXHgIf8JQOv33oq0cZ7mOojlu2hlA/2Kqwm22OF5bsNCSs4siBWPhxWSRy00GyJHjAA5FYGgiR2dTw8SykgjLRQglJH26br0IJntQpSXVBLNDBLNNZ6cTx8IBpp7Rj9LNGo568d/JaM+SkZ9hMqcUPPEcxodInLCWiXXhWvC9NtRRaghSno4dpu1ZA/vpKdRVVZHYzh61NcG0wLNxWR2XiY9BnZq7tnMyc9qLjCbis3s3ExC6Ucf2Xay8tuFKK0JU9U+xPoh+Yesn3XfpSf8Pk0HDhvDURobIkQao835+2jLkfhzWy7/9LX1BKIQiFoq2ocojede5TppC7wsTIuAHS3+3glcmKg3b/qBZdVF6PtxJfXpQeozApRnBZk0of8RvZx5Be0IZeiU2sMlU++tSBt1QrnOGHMzcDNAr169TuoDdpXV0r4hQv9tlUQCseFhTbcd9kBzMZiWESQjM43s3IxDisRDllsUkmmHPXb4fSgjNmwslPHp+rRQ8IQnIXphxlvN55i21NojMgIBQ0GXHIrLaqlsH3Iai0gb5ul+HcRyXcha+m+tJJxmaEgP0BAKUhkK8MXP9SS7RWHZvkWxmZOX2WodC0cz9UtDuOMvawm3OPAXChqmfmnISb1PMC1AMC1AxmmkpXu370uKvCtyKpxXaqe6s9Y0qcaBjhnMnVAYmxkDKMrL4ms/vsiTWP0qWXpvRfzMWvsY8BjAiBEjTqrbsjAvi2JrmfOFT3MdxPLdU3dNSGygCZRMIzKSKRYRPzudg3CFeVkUl9bwzwmF2MChuW7yXeMSGmciJdNBfuU6acu8vHhcMdCzxd894usOYa19zFo7wlo7oqCg4ITf/I6JA8kKBWOJK76jph+eiDhwQrnudNwxcSBZ6WmHFKVtId9dM7yIX153DkV5WRhiO5e/vO4cJztryRSLSBvl6X4dfJrrWhalbSHXQSzHvH3XBLbNuIK375rgLLco10lb5mWP6bvAAGNMX2KJ6+vAjYl682Q6OiUiKc3TXAdtO98l04iMZIpFpA1SrmsjlOukrfKsMLXWNhpjbgXmEJtW/Alr7fuJ/Az98ETEtdbIdaB8JyJuKdeJiNc8PcfUWvsG8IaXnyEi4ppynYikAuU6EfGSl+eYioiIiIiIiByXClMRERERERFxSoWpiIiIiIiIOKXCVERERERERJxSYSoiIiIiIiJOqTAVERERERERp1SYioiIiIiIiFMqTEVERERERMQpFaYiIiIiIiLilLHWuo6hmTGmBPjYdRxH0RnY7zqIVqB2+otf2tnbWlvgOohEUq5zTu30F7+0U7mu9fjlO3M8aqf/+KGtx8x1SVWYJitjzApr7QjXcXhN7fSXVGmnJE6qfGfUTn9JlXZK4qTKd0bt9B+/t1VDeUVERERERMQpFaYiIiIiIiLilArTE/OY6wBaidrpL6nSTkmcVPnOqJ3+kirtlMRJle+M2uk/vm6rzjEVERERERERp9RjKiIiIiIiIk6pMG3BGPOEMWafMWZ9i3XTjDHFxpg18dsklzEmgjGmpzFmnjFmgzHmfWPMD+LrOxpj5hpjPorf57uO9XR9Rlt9tV2NMZnGmOXGmLXxdk6Pr+9rjFlmjNlsjHnRGJPuOlZJDqmQ75TrfLlNlevkpKRCroPUyXfKdf7OdRrK24IxZixQBTxlrT07vm4aUGWtfcBlbIlkjOkOdLfWrjLGtAdWAtcAU4CD1toZxpi7gHxr7Z0OQz1tn9HWr+Kj7WqMMUC2tbbKGBMCFgM/AH4IzLLWvmCMeRRYa619xGWskhxSId8p1ynXuYxVkkMq5DpInXynXOfvXKce0xastQuBg67j8Jq1dre1dlV8uRL4ACgCrgaejD/tSWI/9DbtM9rqKzamKv5nKH6zwATgL/H1vtimkhipkO+U65TrRFIh10Hq5DvlOn/nOhWmJ+ZWY8x78eEgbXoIxOGMMX2A4cAyoKu1dnf8oT1AV0dheeKwtoLPtqsxJmiMWQPsA+YCW4Aya21j/Ck78WHyloTz1e+iiXKdf7apcp0kiK9+Fy2lSr5TrvNfrlNhenyPAP2AYcBu4EG34SSOMSYHeAW43Vpb0fIxGxvj7Ztx3kdpq++2q7U2Yq0dBvQARgJnOQ5J2h7f/S5AuQ6fbVPlOkkA3/0umqRKvlOu8ycVpsdhrd0b/2JEgceJfTHavPh49VeAZ621s+Kr98bH7jeN4d/nKr5EOlpb/bpdAay1ZcA84HNAnjEmLf5QD6DYWWCS9Pz4u1Cu8982baJcJ6fKr7+LVMl3ynX+zXUqTI+j6cccdy2w/ljPbSviJ1T/CfjAWvvrFg+9Dnwrvvwt4LXWji3RjtVWv21XY0yBMSYvvpwFXELsvIt5wPXxp/lim4p3fPi7UK7z3zZVrpPT5rffBaROvlOu83eu06y8LRhjngfGA52BvcDU+N/DiA192A7c0mKsfptkjBkNLALWAdH46nuIjdF/CegFfAx81VrbpicM+Iy23oCPtqsx5lxiJ8EHiR1wesla+1NjzBnAC0BHYDVwk7W23l2kkixSId8p1ynXuYtUkkUq5DpInXynXOfvXKfCVERERERERJzSUF4RERERERFxSoWpiIiIiIiIOKXCVERERERERJxSYSoiIiIiIiJOqTAVERERERERp1SYiqeMMRFjzBpjzPvGmLXGmB8ZY075e2eMuafFch9jTJu+TpWI+INynYikAuU68ZIKU/FarbV2mLV2CLGLA19O7Bpip+qe4z9FRKTVKdeJSCpQrhPPqDCVVmOt3QfcDNxqYoLGmPuNMe8aY94zxtwCYIwZb4xZaIz5uzFmozHmUWNMwBgzA8iKH6l7Nv62QWPM4/Ejd/80xmS5ap+ICCjXiUhqUK6TRFNhKq3KWrsVCAJdgO8A5dbaC4ALgH8xxvSNP3UkcBswGOgHXGetvYtPj9R9I/68AcAf4kfuyoAvt15rRESOTrlORFKBcp0kkgpTcelSYLIxZg2wDOhELCEBLLfWbrXWRoDngdHHeI9t1to18eWVQB8P4xURORXKdSKSCpTr5LSkuQ5AUosx5gwgAuwDDHCbtXbOYc8ZD9jDXnr4303qWyxHAA35EBHnlOtEJBUo10kiqcdUWo0xpgB4FHjIWmuBOcD3jDGh+ONnGmOy408faYzpG5/p7WvA4vj6cNPzRUSSkXKdiKQC5TpJNPWYitey4kM6QkAj8DTw6/hjfyQ2RGOVMcYAJcA18cfeBR4C+gPzgFfj6x8D3jPGrAJ+0hoNEBE5Acp1IpIKlOvEMyZ2gEMkecSHfPzYWnul61hERLyiXCciqUC5Tk6UhvKKiIiIiIiIU+oxFREREREREafUYyoiIiIiIiJOqTAVERERERERp1SYioiIiIiIiFMqTEVERERERMQpFaYiIiIiIiLilApTERERERERcep/AQZ5b+0ps3bUAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 1152x1152 with 3 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "for i in range(3):\n",
    "    data_for_alg = (df[i*5:i*5+5]).sort_values(by='Solution Depth', axis=0, ascending=True, inplace=False, kind='quicksort', na_position='last')\n",
    "    plt.subplot(3, 3, i+1, xlabel='Depth', ylabel='Exec. Time')\n",
    "    plt.plot(data_for_alg['Solution Depth'], data_for_alg['Exec. Time (sec)'], 'rebeccapurple')\n",
    "    plt.scatter(data_for_alg['Solution Depth'], data_for_alg['Exec. Time (sec)'])\n",
    "    title = 'BFS' if i == 0 else 'IDS' if i == 1 else 'A*'\n",
    "    plt.title(title)"
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}