HA_03_04_Schmidt - Kopie.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# HA 04 und 04 Schmidt "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## 0 Initialization and Helper Functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pathlib   # for handling file system\n",
    "import random\n",
    "import time \n",
    "import copy      # for copy objects \n",
    "import itertools # use products for iterations\n",
    "\n",
    "from matplotlib import pyplot as plt\n",
    "from matplotlib import animation as animation\n",
    "from matplotlib.colors import ListedColormap\n",
    "\n",
    "from IPython.display import HTML\n",
    "\n",
    "from collections import deque  # properties of a linked list to left and right\n",
    "from queue import Queue, PriorityQueue\n",
    "import numpy as np\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_puzzle_config(ax, config):\n",
    "    \"\"\"Visualise a given configuration of the 8-puzzle.\"\"\"\n",
    "    cmap = ListedColormap([\"lightgray\", \"lightblue\"])\n",
    "    ax.matshow(config == 0, cmap=cmap)\n",
    "    ax.set_xticks([x - 0.5 for x in ax.get_xticks()][1:], minor='true')\n",
    "    ax.set_yticks([y - 0.5 for y in ax.get_yticks()][1:], minor='true')\n",
    "    ax.grid(which='minor')\n",
    "    for row in range(3):\n",
    "        for col in range(3):\n",
    "            value =  config[row, col]\n",
    "            ax.text(col, row, str(value), \n",
    "                    va=\"center\", ha=\"center\", \n",
    "                    font={'weight': 'bold' if value == 0 else 'normal'})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def animate_moves(solution_path, output_path = None, delay = 2000, video_inplace = True, filename = \"8puzzle_steps.mp4\"):\n",
    "    \"\"\"Given a initial configuration of the 8 puzzle animate all movesments that lead to the target configuration.\"\"\"\n",
    "\n",
    "    def add_text(ax, config):\n",
    "        for row in range(3):\n",
    "            for col in range(3):\n",
    "                value: np.unit8 = config[row, col]\n",
    "                ax.text(col, row, str(value), \n",
    "                        va=\"center\", ha=\"center\", \n",
    "                        font={'weight': 'bold' if value == 0 else 'normal'})\n",
    "\n",
    "    def animate(img, ax, config):\n",
    "        ax.clear()\n",
    "        img = ax.matshow(root.state == 0, cmap=cmap)\n",
    "        ax.set_xticks([x - 0.5 for x in ax.get_xticks()][1:], minor='true')\n",
    "        ax.set_yticks([y - 0.5 for y in ax.get_yticks()][1:], minor='true')\n",
    "        ax.grid(which='minor')\n",
    "        img.set_array(config == 0)\n",
    "        add_text(ax, config)\n",
    "        return (ax,)\n",
    "\n",
    "    fig, ax = plt.subplots()\n",
    "\n",
    "    cmap = ListedColormap([\"lightgray\", \"lightblue\"])\n",
    "    root = solution_path[0]\n",
    "    img_mat = ax.matshow(root.state == 0, cmap=cmap)\n",
    "    ax.set_xticks([x - 0.5 for x in ax.get_xticks()][1:], minor='true')\n",
    "    ax.set_yticks([y - 0.5 for y in ax.get_yticks()][1:], minor='true')\n",
    "    ax.grid(which='minor')\n",
    "    add_text(ax, root.state)\n",
    "\n",
    "    anim = animation.FuncAnimation(\n",
    "        fig, lambda p: animate(img_mat, ax, p.state), solution_path, interval=delay\n",
    "    )\n",
    "    plt.close(fig)\n",
    "    \n",
    "    if not video_inplace and output_path is not None:\n",
    "        output_path.mkdir(parents=True, exist_ok=True)\n",
    "        anim.save(output_path / filename ) \n",
    "    return anim"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    \"\"\"Base class that implements commonly-used methods for the tree search algorithms\"\"\"\n",
    "    \n",
    "    def __init__(self, state):\n",
    "        \"\"\"Initialiser of the base class.\n",
    "        \n",
    "        Parameters:\n",
    "            state: np.ndarray\n",
    "                State array representing a certain digit arrangement of the 8 puzzle.\n",
    "                \n",
    "        Output:\n",
    "            No output. Sets attribute variables of the class.\n",
    "        \"\"\"\n",
    "        self.state = state\n",
    "        self.empty_pos = self._get_empty_pos()\n",
    "        self.hash_value = hash(repr(self))\n",
    "\n",
    "\n",
    "    def _get_empty_pos(self):\n",
    "        \"\"\"Locate the position of the empty spot in the puzzle\"\"\"\n",
    "        row, col = np.where(self.state == 0)\n",
    "        return row[0], col[0]\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"Node({self.state})\"\n",
    "    \n",
    "    def __hash__(self):\n",
    "        return self.hash_value\n",
    "\n",
    "    def __eq__(self, rhs): \n",
    "        return self.hash_value == rhs.hash_value\n",
    "\n",
    "    def __ne__(self, rhs):\n",
    "        return not (self == rhs)\n",
    "    \n",
    "    def _next_positions(self):\n",
    "        \"\"\"Given a tuple of the current position of the 0 yield tuples of possible next positions.\n",
    "        \n",
    "        Parameters:\n",
    "            No parameters.\n",
    "        \n",
    "        Returns:\n",
    "            Generator[Tuple[int, int], None, None].  (See: https://docs.python.org/3/library/typing.html#typing.Generator)\n",
    "                When calling `next` on this generator a tuple with ints is returned which represents the \n",
    "                next position of the 0 in the array.\n",
    "        \"\"\"\n",
    "        # Values for the indices should be in the range 0 <= x < 2\n",
    "        idx0, idx1 = self.empty_pos\n",
    "        assert idx0 in range(3), \"idx0 must be in range(3)\"\n",
    "        assert idx1 in range(3), \"idx1 must be in range(3)\"\n",
    "\n",
    "        # Can we move up?\n",
    "        if idx0 > 0:\n",
    "            yield (idx0 - 1, idx1)\n",
    "        # Can we move left?\n",
    "        if idx1 > 0:\n",
    "            yield (idx0, idx1 - 1)\n",
    "        # Can we move down?\n",
    "        if idx0 < 2:\n",
    "            yield (idx0 + 1, idx1)\n",
    "        # Can we move right?\n",
    "        if idx1 < 2:\n",
    "            yield (idx0, idx1 + 1)\n",
    "\n",
    "    def _make_new_state(self, empty_pos_new):\n",
    "        \"\"\"Move the empty spot in the puzzle and thus make a new state but leave the state as is\n",
    "        \n",
    "        Parameters:\n",
    "            empty_pos_new: tuple\n",
    "                Pair of integer values that represent the next position of the empty spot of the puzzle.\n",
    "            buffer: np.ndarray\n",
    "                State array that will hold the new state of the puzzle after having moved the empty spot.\n",
    "        Output:\n",
    "            buffer, which is the new state.\n",
    "        \"\"\"\n",
    "        buffer = self.state.copy()  # very important to leave the state unchanged\n",
    "        buffer[empty_pos_new] = self.state[self.empty_pos]\n",
    "        buffer[self.empty_pos] = self.state[empty_pos_new]\n",
    "\n",
    "        return buffer    \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class NodeRandom(Node):\n",
    "    \n",
    "    def randomise_state(self, num_moves):\n",
    "        \"\"\"Randomly change the current state of the puzzle\n",
    "        \n",
    "        Parameters:\n",
    "            num_moves: int\n",
    "                Number of times to randomly change the state of the puzzle.\n",
    "        \n",
    "        Output: Node\n",
    "            The (modified) version of the class instance. If `num_moves == 0` the instance of the class is returned unchanged. \n",
    "        \"\"\"\n",
    "        if num_moves > 0:\n",
    "            for _ in range(num_moves):\n",
    "                pos_new_random = random.choice(tuple(self._next_positions()))\n",
    "                self.state[:, :] = self._make_new_state(pos_new_random)\n",
    "                self.empty_pos = pos_new_random\n",
    "                \n",
    "        self.hash_value = hash(repr(self))        \n",
    "        return self\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class NodeBFS(Node):\n",
    "    \"\"\"Node for the BFS tree search algorithm\"\"\"\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return f\"NodeBFS({self.state})\"\n",
    "\n",
    "    \n",
    "    def next_nodes(self):\n",
    "        \"\"\"Generate other state nodes that from the current node.\n",
    "        \n",
    "        Parameters:\n",
    "            No parameters.\n",
    "        \n",
    "        Output:\n",
    "            Generator[NodeBFS, None, None]. \n",
    "            Yields a node representing a state of the the puzzle that can be generated through\n",
    "            a single move of the empty spot in the current state.\n",
    "        \"\"\"\n",
    "        for pos_new in self._next_positions():\n",
    "            yield type(self)(self._make_new_state(pos_new))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reconstruct_path(to_node, parent):\n",
    "    \"\"\"Reconstruct all nodes on the path root_node --> to_node.\n",
    "\n",
    "    Parameters:\n",
    "        to_node: Node\n",
    "            Node at the end of the path.\n",
    "        parent: dict\n",
    "            Child - parent relationship between nodes in the search tree.\n",
    "    \n",
    "    Output:\n",
    "        path: deque\n",
    "            List with all the nodes along the path root_node --> to_node.\n",
    "    \"\"\"\n",
    "    path = deque()\n",
    "    current = to_node\n",
    "    while current is not None:\n",
    "        path.appendleft(current)\n",
    "        current = parent[current]\n",
    "    return path\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_target_bfs(initial, final):\n",
    "    \"\"\"Find a solutions of the 8-puzzle when given an initial configuration by using the BFS algorithm.\n",
    "    \n",
    "    Parameters:\n",
    "        initial: NodeBFS\n",
    "            Initial state of the 8-puzzle.\n",
    "        final: NodeBFS\n",
    "            Final state of the 8-puzzle.\n",
    "\n",
    "    Output:\n",
    "        n: number of visited nodes\n",
    "        deque: All nodes that lie on the path from the root node to the final node.\n",
    "    \"\"\"\n",
    "    q = Queue()  # FIFO queue\n",
    "    q.put(initial)\n",
    "    parent = {initial: None}  # dictionary \n",
    "    \n",
    "    n = 1 # Counter for number of nodes that have been put into the queue.\n",
    "\n",
    "    if initial == final:\n",
    "        return n, reconstruct_path(initial, parent)\n",
    "    \n",
    "    \n",
    "    while not q.empty():\n",
    "        node = q.get()\n",
    "        for child in node.next_nodes():\n",
    "            if child not in parent:\n",
    "                n += 1\n",
    "                q.put(child)\n",
    "                parent[child] = node \n",
    "                if child == final:\n",
    "                    return n, reconstruct_path(child, parent)\n",
    "\n",
    "                \n",
    "    return -1, []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def state_difference(state, final_state):\n",
    "    \"\"\"Compute the difference of two states of the 8 puzzle.\n",
    "\n",
    "    Parameters:\n",
    "         state: np.ndarray\n",
    "            State of the 8 puzzle for which to compute the distance to the final state.\n",
    "        final_state: np.ndarray\n",
    "            Solved state of the 8 puzzle.\n",
    "    \n",
    "    Output:\n",
    "        int: The difference of the two states. The difference is computed by the number digits in state\n",
    "             that are *not* in the same position in final_state.\n",
    "    \"\"\"\n",
    "    return np.sum((state != 0) & (state != final_state))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class NodeGreedy(Node):   \n",
    "    def __init__(self, state, estimated_cost):\n",
    "        \"\"\"Initialiser of the class\n",
    "        \n",
    "        Parameters:\n",
    "            state: np.ndarray\n",
    "                State array representing a certain digit arrangement of the 8 puzzle. The state is\n",
    "                forwarded to the base class.\n",
    "            estimated_cost: int\n",
    "                An estimate of the cost of getting from the current state to the solved state.\n",
    "                \n",
    "        Output:\n",
    "            No output. Initialises the attribute variables of the class.\n",
    "        \"\"\"\n",
    "        self.estimated_cost = estimated_cost\n",
    "        super().__init__(state)\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"NodeGreedy({self.state}, {self.estimated_cost})\"\n",
    "\n",
    "    \n",
    "    def __lt__(self, rhs):\n",
    "        \"\"\"Test if a node instance is 'smaller' than another instance.\n",
    "        \n",
    "        Parameters:\n",
    "            rhs: NodeAstar\n",
    "                Other node instance.\n",
    "                \n",
    "        Output: bool\n",
    "            True in case the node has a smaller estimated cost to reach the final state as the other node else False.\n",
    "            \n",
    "        The < binary operator is needed to be able to use instances of this class with PriorityQueue.    \n",
    "        \"\"\"\n",
    "        return self.estimated_cost < rhs.estimated_cost\n",
    "\n",
    "    def next_nodes(self, final, cost_estimator: callable):\n",
    "        \"\"\"Generate other state nodes from the current node.\n",
    "        \n",
    "        Parameters:\n",
    "            final: NodeGreedy\n",
    "                A node representing the solved state of the puzzle.\n",
    "            estimator: callable\n",
    "                Cost function to estimated the cost from getting the generated state to the solved state.\n",
    "            \n",
    "            Output:\n",
    "                Generator[NodeGreedy, None, None]. \n",
    "                Yields a node representing a state of the puzzle that can be generated through \n",
    "                a single move of the empty spot in the current state.\n",
    "        \"\"\"\n",
    "        for pos_new in self._next_positions():\n",
    "            buffer = self._make_new_state(pos_new)\n",
    "            yield type(self)(buffer.copy(), cost_estimator(buffer, \n",
    "                                                           final.state))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "def informed_search(initial, final, cost_estimator: callable):\n",
    "    \"\"\"Find path from initial to final node.\n",
    "    \n",
    "    Parameters:\n",
    "        initial: Node[Greedy, Astar]\n",
    "            Node representing the initial state of the 8 puzzle.\n",
    "        final: Node[Greedy, Astar]\n",
    "            Node representing the solved state of the 8 puzzle.\n",
    "        cost_estimator: callable\n",
    "            Function to estimate the cost to get from some node to the solved state.\n",
    "    \n",
    "    Output:\n",
    "        deque: All nodes that lie on the path from the root node to the final node.\n",
    "    \"\"\"\n",
    "    pq = PriorityQueue()\n",
    "    pq.put(initial)\n",
    "    parent = {initial: None}  # dictionary\n",
    "    \n",
    "    n = 1 # Counter for the number of nodes that have been put into the queue.\n",
    "\n",
    "    if np.array_equal(initial.state, final.state):  # == is not possible because == includes cost functions also\n",
    "        return n, reconstruct_path(initial, parent)\n",
    "\n",
    "    \n",
    "    while not pq.empty():\n",
    "        current = pq.get()\n",
    "        for child in current.next_nodes(final, cost_estimator):\n",
    "            if child not in parent:\n",
    "                n += 1\n",
    "                pq.put(child)\n",
    "                parent[child] = current\n",
    "                if np.array_equal(child.state, final.state):  # == is not possible because == includes cost functions also\n",
    "                    return n, reconstruct_path(child, parent)\n",
    "                \n",
    "    return -1, []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "class NodeAstar(Node):\n",
    "    def __init__(self, state, accumulated_cost, estimated_cost):\n",
    "        \"\"\"Initialiser of the class.\n",
    "            \n",
    "        Parameters:\n",
    "            state: np.ndarray                 \n",
    "                State array representing a certain digit arrangement of the 8 puzzle. The state is \n",
    "                forwarded to the base class.\n",
    "            accumulated_cost: int\n",
    "                Number of steps executed so far.\n",
    "            estimated_cost: int>\n",
    "                Estimated cost for getting from the current state to the solved state of the puzzle.\n",
    "            \n",
    "        Output:\n",
    "            No output. Initialises the attribute variables of the class.\n",
    "        \"\"\"\n",
    "        self.accumulated_cost, self.estimated_cost = accumulated_cost, \\\n",
    "                                                        estimated_cost\n",
    "        self.total_estimated_cost = accumulated_cost + estimated_cost\n",
    "        super().__init__(state)\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"NodeAstar({self.state}, {self.accumulated_cost}, \\\n",
    "                {self.estimated_cost})\"\n",
    "    \n",
    "    def __lt__(self, rhs):\n",
    "        \"\"\"Test if a node instance is 'smaller' than another instance.\n",
    "        \n",
    "        Parameters:\n",
    "            rhs: NodeAstar\n",
    "                Other node instance.\n",
    "                \n",
    "        Output: bool\n",
    "            True in case the node has a smaller *total estimated cost* to reach the final state as the other node else False.\n",
    "            >\n",
    "        The < binary operator is needed to be able to use instances of this class with PriorityQueue.    \n",
    "        \"\"\"\n",
    "        return self.total_estimated_cost < rhs.total_estimated_cost\n",
    "\n",
    "    def next_nodes(self, final, estimator):\n",
    "        for pos_new in self._next_positions():\n",
    "            buffer = self._make_new_state(pos_new)\n",
    "            yield type(self)(buffer.copy(), self.accumulated_cost + 1, \n",
    "                             estimator(buffer, final.state))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Meine Bearbeitung"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aufgabe 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Summe der euklidischen/manhatten Abstände ist keine zulässige Heuristik. Auch hier muss die 0 ausgeschlossen werden."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math as m\n",
    "\n",
    "def manhatten_distance(state, final_state):\n",
    "    \"\"\"Compute the manhattan distance between two arrays of identical shape\"\"\"\n",
    "    distance = 0\n",
    "    for i, row in enumerate(state):\n",
    "        for j, value in enumerate(row):\n",
    "            if value != 0:\n",
    "                x, y = np.where(final_state == value)\n",
    "                distance += abs(x[0]-i) + abs(y[0]-j)\n",
    "                #print(f\"Distance for value {value} is {abs(x[0]-i) + abs(y[0]-j)}\")\n",
    "    return distance\n",
    "\n",
    "def euclidian_distance(state, final_state):\n",
    "    \"\"\"Compute the euclidian distance between two arrays of identical shape\"\"\"\n",
    "    distance = 0\n",
    "    for i, row in enumerate(state):\n",
    "        for j, value in enumerate(row):\n",
    "            if value != 0:\n",
    "                x, y = np.where(final_state == value)\n",
    "                distance += m.sqrt(pow((x[0]-i), 2) + pow((y[0]-j),2))\n",
    "                #print(f\"Distance for value {value} is {m.sqrt(pow((x[0]-i), 2) + pow((y[0]-j),2))}\")\n",
    "    return distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "ARRAY_INITIAL = np.array(((4, 8, 3),\n",
    "                          (7, 6, 2),\n",
    "                          (5, 1, 0)), dtype=int)\n",
    " \n",
    "ARRAY_FINAl   = np.array(((1, 3, 6),\n",
    "                          (8, 0, 2),\n",
    "                          (7, 4, 5)), dtype=int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Anzahl falscher Positionen: 7 \n",
      "         Manhattan Abstand: 14 \n",
      "      Euklidischer Abstand: 11.30056307974577\n"
     ]
    }
   ],
   "source": [
    "print(f\"Anzahl falscher Positionen: {state_difference(ARRAY_INITIAL, ARRAY_FINAl)} \\n \\\n",
    "        Manhattan Abstand: {manhatten_distance(ARRAY_INITIAL, ARRAY_FINAl)} \\n \\\n",
    "     Euklidischer Abstand: {euclidian_distance(ARRAY_INITIAL, ARRAY_FINAl)}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "###### Greedy Suche mit Anzahl falscher Positionen\n",
      " Besuchte Knoten: 490 \n",
      " Länge des Pfades: 27\n",
      "###### Greedy Suche mit Manhattan-Abstand\n",
      " Besuchte Knoten: 83 \n",
      " Länge des Pfades: 33\n",
      "###### Greedy Suche mit Euklidischem-Abstand\n",
      " Besuchte Knoten: 333 \n",
      " Länge des Pfades: 41\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "###### Astar Suche mit Anzahl falscher Positionen\n",
      " Besuchte Knoten: 1048 \n",
      " Länge des Pfades: 17\n",
      "###### Astar Suche mit Manhattan-Abstand\n",
      " Besuchte Knoten: 107 \n",
      " Länge des Pfades: 17\n",
      "###### Astar Suche mit Euklidischem-Abstand\n",
      " Besuchte Knoten: 143 \n",
      " Länge des Pfades: 17\n"
     ]
    }
   ],
   "source": [
    "manhattan_greedy_start = NodeGreedy(ARRAY_INITIAL, manhatten_distance(ARRAY_INITIAL, ARRAY_FINAl))\n",
    "manhattan_greedy_final = NodeGreedy(ARRAY_FINAl, 0)\n",
    "euclidian_greedy_start = NodeGreedy(ARRAY_INITIAL, euclidian_distance(ARRAY_INITIAL, ARRAY_FINAl))\n",
    "eucilidan_greedy_final = NodeGreedy(ARRAY_FINAl, 0)\n",
    "difference_greedy_start = NodeGreedy(ARRAY_INITIAL, state_difference(ARRAY_INITIAL, ARRAY_FINAl))\n",
    "difference_greedy_final = NodeGreedy(ARRAY_FINAl, 0)\n",
    "difference_greedy_n, difference_greedy_path = informed_search(difference_greedy_start, difference_greedy_final, state_difference)\n",
    "print(f\"###### Greedy Suche mit Anzahl falscher Positionen\\n \\\n",
    "Besuchte Knoten: {difference_greedy_n} \\n \\\n",
    "Länge des Pfades: {len(difference_greedy_path)}\")\n",
    "manhatten_greedy_n, manhattan_greedy_path = informed_search(manhattan_greedy_start, manhattan_greedy_final, manhatten_distance)\n",
    "print(f\"###### Greedy Suche mit Manhattan-Abstand\\n \\\n",
    "Besuchte Knoten: {manhatten_greedy_n} \\n \\\n",
    "Länge des Pfades: {len(manhattan_greedy_path)}\")\n",
    "euclidian_greedy_n, euclidian_greedy_path = informed_search(euclidian_greedy_start, eucilidan_greedy_final, euclidian_distance)\n",
    "print(f\"###### Greedy Suche mit Euklidischem-Abstand\\n \\\n",
    "Besuchte Knoten: {euclidian_greedy_n} \\n \\\n",
    "Länge des Pfades: {len(euclidian_greedy_path)}\")\n",
    "\n",
    "manhattan_Astar_start = NodeAstar(ARRAY_INITIAL, 0, manhatten_distance(ARRAY_INITIAL, ARRAY_FINAl))\n",
    "manhattan_Astar_final = NodeAstar(ARRAY_FINAl, -1, 0)\n",
    "euclidian_Astar_start = NodeAstar(ARRAY_INITIAL, 0, euclidian_distance(ARRAY_INITIAL, ARRAY_FINAl))\n",
    "eucilidan_Astar_final = NodeAstar(ARRAY_FINAl, -1, 0)\n",
    "difference_Astar_start = NodeAstar(ARRAY_INITIAL, 0, state_difference(ARRAY_INITIAL, ARRAY_FINAl))\n",
    "difference_Astar_final = NodeAstar(ARRAY_FINAl, -1, 0)\n",
    "difference_Astar_n, difference_Astar_path = informed_search(difference_Astar_start, difference_Astar_final, state_difference)\n",
    "print(f\"###### Astar Suche mit Anzahl falscher Positionen\\n \\\n",
    "Besuchte Knoten: {difference_Astar_n} \\n \\\n",
    "Länge des Pfades: {len(difference_Astar_path)}\")\n",
    "manhatten_Astar_n, manhattan_Astar_path = informed_search(manhattan_Astar_start, manhattan_Astar_final, manhatten_distance)\n",
    "print(f\"###### Astar Suche mit Manhattan-Abstand\\n \\\n",
    "Besuchte Knoten: {manhatten_Astar_n} \\n \\\n",
    "Länge des Pfades: {len(manhattan_Astar_path)}\")\n",
    "euclidian_Astar_n, euclidian_Astar_path = informed_search(euclidian_Astar_start, eucilidan_Astar_final, euclidian_distance)\n",
    "print(f\"###### Astar Suche mit Euklidischem-Abstand\\n \\\n",
    "Besuchte Knoten: {euclidian_Astar_n} \\n \\\n",
    "Länge des Pfades: {len(euclidian_Astar_path)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aufgabe 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tiefe:   2 - Anzahl Anfangszustände:   12\n",
      "Tiefe:   4 - Anzahl Anfangszustände:   32\n",
      "Tiefe:   6 - Anzahl Anfangszustände:   98\n",
      "Tiefe:   8 - Anzahl Anfangszustände:  201\n",
      "Tiefe:  10 - Anzahl Anfangszustände:  344\n",
      "Tiefe:  12 - Anzahl Anfangszustände:  386\n",
      "Tiefe:  14 - Anzahl Anfangszustände:  384\n",
      "Tiefe:  16 - Anzahl Anfangszustände:  273\n",
      "Tiefe:  18 - Anzahl Anfangszustände:  166\n",
      "Tiefe:  20 - Anzahl Anfangszustände:   73\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "time.perf_counter_ns()\n",
    "import yaml\n",
    "with open(\"initial_states.yaml\", \"r\") as f:\n",
    "    intial_states = yaml.safe_load(f)\n",
    "for d, states in intial_states.items():\n",
    "        print(f\"Tiefe: {d:3d} - Anzahl Anfangszustände: {len(states):4d}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def time_algorithm(intial_states, node_type_names, heuristics, heuristic_names):\n",
    "    algorithm = []\n",
    "    used_heuristic = []\n",
    "    depth = []\n",
    "    runtime = []\n",
    "    visited_node = []\n",
    "    path_length = []\n",
    "    for node_type_name in node_type_names:\n",
    "        print(f\"Beginning measurement of {node_type_name}...\")\n",
    "        if node_type_name == \"BFS\":\n",
    "            heuristic_helper = [(None, \"Keine\")]\n",
    "        else:\n",
    "            heuristic_helper = zip(heuristics, heuristic_names)\n",
    "        for heuristic, heuristic_name in heuristic_helper:\n",
    "            print(f\"For heuristic: {heuristic_name} ...\")\n",
    "            for current_depth, problems in intial_states.items():\n",
    "                print(f\"In depth: {current_depth} ...\")\n",
    "                for problem in problems:\n",
    "                    start_array = np.asarray(problem[0], dtype=int)\n",
    "                    final_array = np.asarray(problem[1], dtype=int)\n",
    "                    if node_type_name == \"BFS\":\n",
    "                        start = NodeBFS(start_array)\n",
    "                        final = NodeBFS(final_array)\n",
    "                        start_time = time.perf_counter_ns()\n",
    "                        n, path = find_target_bfs(start, final)\n",
    "                        final_time = time.perf_counter_ns()\n",
    "                    if node_type_name == \"Greedy\":\n",
    "                        start = NodeGreedy(start_array, heuristic(start_array, final_array))\n",
    "                        final = NodeGreedy(final_array, 0)\n",
    "                        start_time = time.perf_counter_ns()\n",
    "                        n, path = informed_search(start, final, heuristic)\n",
    "                        final_time = time.perf_counter_ns()\n",
    "                    if node_type_name == \"A*\":\n",
    "                        start = NodeAstar(start_array, 0, heuristic(start_array, final_array))\n",
    "                        final = NodeAstar(final_array, -1, 0)\n",
    "                        start_time = time.perf_counter_ns()\n",
    "                        n, path = informed_search(start, final, heuristic)\n",
    "                        final_time = time.perf_counter_ns()\n",
    "                    algorithm.append(node_type_name)\n",
    "                    used_heuristic.append(heuristic_name)\n",
    "                    depth.append(current_depth)\n",
    "                    runtime.append(final_time - start_time)\n",
    "                    visited_node.append(n)\n",
    "                    path_length.append(len(path))\n",
    "                print(f\"Finished depth: {current_depth}.\")\n",
    "            print(f\"Finished heuristic: {heuristic_name}.\")\n",
    "        print(f\"Finished {node_type_name}.\")\n",
    "    return algorithm, used_heuristic, depth, visited_node, path_length, runtime\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Beginning measurement of BFS...\n",
      "For heuristic: Keine ...\n",
      "In depth: 2 ...\n",
      "Finished depth: 2.\n",
      "In depth: 4 ...\n",
      "Finished depth: 4.\n",
      "In depth: 6 ...\n",
      "Finished depth: 6.\n",
      "In depth: 8 ...\n",
      "Finished depth: 8.\n",
      "In depth: 10 ...\n",
      "Finished depth: 10.\n",
      "In depth: 12 ...\n",
      "Finished depth: 12.\n",
      "In depth: 14 ...\n",
      "Finished depth: 14.\n",
      "In depth: 16 ...\n",
      "Finished depth: 16.\n",
      "In depth: 18 ...\n",
      "Finished depth: 18.\n",
      "In depth: 20 ...\n",
      "Finished depth: 20.\n",
      "Finished heuristic: Keine.\n",
      "Finished BFS.\n",
      "Beginning measurement of Greedy...\n",
      "For heuristic: Difference ...\n",
      "In depth: 2 ...\n",
      "Finished depth: 2.\n",
      "In depth: 4 ...\n",
      "Finished depth: 4.\n",
      "In depth: 6 ...\n",
      "Finished depth: 6.\n",
      "In depth: 8 ...\n",
      "Finished depth: 8.\n",
      "In depth: 10 ...\n",
      "Finished depth: 10.\n",
      "In depth: 12 ...\n",
      "Finished depth: 12.\n",
      "In depth: 14 ...\n",
      "Finished depth: 14.\n",
      "In depth: 16 ...\n",
      "Finished depth: 16.\n",
      "In depth: 18 ...\n",
      "Finished depth: 18.\n",
      "In depth: 20 ...\n",
      "Finished depth: 20.\n",
      "Finished heuristic: Difference.\n",
      "For heuristic: Euklidisch ...\n",
      "In depth: 2 ...\n",
      "Finished depth: 2.\n",
      "In depth: 4 ...\n",
      "Finished depth: 4.\n",
      "In depth: 6 ...\n",
      "Finished depth: 6.\n",
      "In depth: 8 ...\n",
      "Finished depth: 8.\n",
      "In depth: 10 ...\n",
      "Finished depth: 10.\n",
      "In depth: 12 ...\n",
      "Finished depth: 12.\n",
      "In depth: 14 ...\n",
      "Finished depth: 14.\n",
      "In depth: 16 ...\n",
      "Finished depth: 16.\n",
      "In depth: 18 ...\n",
      "Finished depth: 18.\n",
      "In depth: 20 ...\n",
      "Finished depth: 20.\n",
      "Finished heuristic: Euklidisch.\n",
      "For heuristic: Manhattan ...\n",
      "In depth: 2 ...\n",
      "Finished depth: 2.\n",
      "In depth: 4 ...\n",
      "Finished depth: 4.\n",
      "In depth: 6 ...\n",
      "Finished depth: 6.\n",
      "In depth: 8 ...\n",
      "Finished depth: 8.\n",
      "In depth: 10 ...\n",
      "Finished depth: 10.\n",
      "In depth: 12 ...\n",
      "Finished depth: 12.\n",
      "In depth: 14 ...\n",
      "Finished depth: 14.\n",
      "In depth: 16 ...\n",
      "Finished depth: 16.\n",
      "In depth: 18 ...\n",
      "Finished depth: 18.\n",
      "In depth: 20 ...\n",
      "Finished depth: 20.\n",
      "Finished heuristic: Manhattan.\n",
      "Finished Greedy.\n",
      "Beginning measurement of A*...\n",
      "For heuristic: Difference ...\n",
      "In depth: 2 ...\n",
      "Finished depth: 2.\n",
      "In depth: 4 ...\n",
      "Finished depth: 4.\n",
      "In depth: 6 ...\n",
      "Finished depth: 6.\n",
      "In depth: 8 ...\n",
      "Finished depth: 8.\n",
      "In depth: 10 ...\n",
      "Finished depth: 10.\n",
      "In depth: 12 ...\n",
      "Finished depth: 12.\n",
      "In depth: 14 ...\n",
      "Finished depth: 14.\n",
      "In depth: 16 ...\n",
      "Finished depth: 16.\n",
      "In depth: 18 ...\n",
      "Finished depth: 18.\n",
      "In depth: 20 ...\n",
      "Finished depth: 20.\n",
      "Finished heuristic: Difference.\n",
      "For heuristic: Euklidisch ...\n",
      "In depth: 2 ...\n",
      "Finished depth: 2.\n",
      "In depth: 4 ...\n",
      "Finished depth: 4.\n",
      "In depth: 6 ...\n",
      "Finished depth: 6.\n",
      "In depth: 8 ...\n",
      "Finished depth: 8.\n",
      "In depth: 10 ...\n",
      "Finished depth: 10.\n",
      "In depth: 12 ...\n",
      "Finished depth: 12.\n",
      "In depth: 14 ...\n",
      "Finished depth: 14.\n",
      "In depth: 16 ...\n",
      "Finished depth: 16.\n",
      "In depth: 18 ...\n",
      "Finished depth: 18.\n",
      "In depth: 20 ...\n",
      "Finished depth: 20.\n",
      "Finished heuristic: Euklidisch.\n",
      "For heuristic: Manhattan ...\n",
      "In depth: 2 ...\n",
      "Finished depth: 2.\n",
      "In depth: 4 ...\n",
      "Finished depth: 4.\n",
      "In depth: 6 ...\n",
      "Finished depth: 6.\n",
      "In depth: 8 ...\n",
      "Finished depth: 8.\n",
      "In depth: 10 ...\n",
      "Finished depth: 10.\n",
      "In depth: 12 ...\n",
      "Finished depth: 12.\n",
      "In depth: 14 ...\n",
      "Finished depth: 14.\n",
      "In depth: 16 ...\n",
      "Finished depth: 16.\n",
      "In depth: 18 ...\n",
      "Finished depth: 18.\n",
      "In depth: 20 ...\n",
      "Finished depth: 20.\n",
      "Finished heuristic: Manhattan.\n",
      "Finished A*.\n"
     ]
    }
   ],
   "source": [
    "node_type_names = [\"BFS\", \"Greedy\", \"A*\"]\n",
    "heuristics = [state_difference, manhatten_distance, euclidian_distance]\n",
    "heuristic_names = [\"Difference\", \"Euklidisch\", \"Manhattan\"]\n",
    "\n",
    "algorithm, used_heuristic, depth, visited_node, path_length, runtime = time_algorithm(intial_states, node_type_names, heuristics, heuristic_names)\n",
    "\n",
    "\n",
    "\n",
    "results = pd.DataFrame({\n",
    "    \"Algorithmus\": algorithm,\n",
    "    \"Heuristik\": used_heuristic,\n",
    "    \"Tiefe\": depth,\n",
    "    \"Besuchte Knoten\": visited_node,\n",
    "    \"Pfadlaenge\": path_length,\n",
    "    \"Zeit\": runtime,\n",
    "})\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "mask1 = results[\"Heuristik\"] == \"Euklidisch\"\n",
    "mask2 = results[\"Heuristik\"] == \"Manhattan\"\n",
    "\n",
    "results.loc[mask1, \"Heuristik\"] = \"Manhattan\"\n",
    "results.loc[mask2, \"Heuristik\"] = \"Euklidisch\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'pandas.core.frame.DataFrame'>\n",
      "RangeIndex: 13783 entries, 0 to 13782\n",
      "Data columns (total 6 columns):\n",
      " #   Column           Non-Null Count  Dtype \n",
      "---  ------           --------------  ----- \n",
      " 0   Algorithmus      13783 non-null  object\n",
      " 1   Heuristik        13783 non-null  object\n",
      " 2   Tiefe            13783 non-null  int64 \n",
      " 3   Besuchte Knoten  13783 non-null  int64 \n",
      " 4   Pfadlaenge       13783 non-null  int64 \n",
      " 5   Zeit             13783 non-null  int64 \n",
      "dtypes: int64(4), object(2)\n",
      "memory usage: 646.2+ KB\n"
     ]
    }
   ],
   "source": [
    "results = pd.read_csv(\"results.csv\").iloc[:, 1:]\n",
    "results.info()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,