14-Loesung.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Labyrinthgenerator\n",
    "### - Lösung - "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Links, rechts, geradeaus, du kommst hier nicht mehr raus, ...\n",
    "aus Oomph! - Labyrinth\n",
    "\n",
    "In dieser Aufgabe geht es darum, einen Labyrinthgenerator zu schreiben. Aber zunächst zu unserer Motivation, bevor du dich noch im Labyrinth verlierst...\n",
    "\n",
    "### Labyrinth als Graph\n",
    "Ein Labyrinth kann auch als sogenannter Graph betrachtet werden. Graphen kann man wie Netze veranschaulichen; sie haben Kanten (Linien) und Knoten (Punkte). An Knoten können sich mehrere Kanten treffen. Wenn man die Pfade eines Labyrinths als Kanten versteht und die Kreuzungen und Kurven als Knoten, wird aus dem Labyrinth (in schwarz-weiß) ein Graph (in rot). Das folgende Bild veranschaulicht diese Idee:\n",
    "\n",
    "<img src=\"http://caeze.bplaced.net/bwki/labyrinth1.png\" alt=\"labyrinth_1\" width=\"300\"/>\n",
    "\n",
    "An Graphen wird schon lange geforscht, daher gibt es eine Vielzahl an Verfahren und Algorithmen um verschiedenste Werte und Eigenschaften in einem Graphen zu bestimmen. In der nächsten Aufgabe wollen wir uns einen der klassichen Graphen-Algorithmen anschauen, aber dazu benötigen wir Testgraphen, um die Implementierung zu validieren.\n",
    "\n",
    "Daher ist die Aufgabe heute, einen Labyrinthgenerator zu entwickeln. Dazu sollst du Prim's Algorithmus implementieren. Wie dieser Algorithmus funktioniert, ist weiter unten in der Aufgabe beschrieben.\n",
    "\n",
    "Zunächst geben wir eine Funktion vor, mit der sich Labyrinthe (als Liste von Listen, die Zellen enthalten) als Bild anzeigen lassen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# importiere die nötigen Module, um Labyrinthe anzeigen zu können\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.cm as cm\n",
    "import numpy as np\n",
    "\n",
    "# mit dieser Funktion kannst du ein Labyrinth als Bild anzeigen\n",
    "def zeige_labyrinth_an(feld, breite=10, höhe=10):\n",
    "    labyrinth = np.zeros([len(feld), len(feld[0])])\n",
    "    for y in range(len(feld)):\n",
    "        for x in range(len(feld[y])):\n",
    "            if labyrinth[x, y] == 0:\n",
    "                zelle = feld[x][y]\n",
    "                # die verschiedenen Typen von Zellen werden weiter\n",
    "                # unten definiert\n",
    "                if zelle.typ == 'p':\n",
    "                    labyrinth[x, y] = 1.0\n",
    "                if zelle.typ == 'w':\n",
    "                    labyrinth[x, y] = 0.0\n",
    "                if zelle.typ == 's':\n",
    "                    labyrinth[x, y] = 1.0\n",
    "                    labyrinth[x - 1, y] = 0.75\n",
    "                if zelle.typ == 'z':\n",
    "                    labyrinth[x, y] = 1.0\n",
    "                    labyrinth[x + 1, y] = 0.75\n",
    "    \n",
    "    fig = plt.figure(figsize = (breite, höhe)) \n",
    "    ax = fig.add_subplot(111)\n",
    "    ax.imshow(labyrinth, cmap='gray', clim=(0, 1))\n",
    "    ax.axis('off')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zudem geben wir eine Funktion vor, die ein Labyrinth-Feld generiert, bei dem alle Zwischenwände noch \"zugemauert\" sind. Durch geeignetes Entfernen dieser Zwischenwände können wir ein Labyrinth erzeugen. Das ist die Idee von Prim's Algorithmus.\n",
    "\n",
    "Schau dir an wie die Datenstruktur für das Labyrinth implementiert ist.\n",
    "\n",
    "Der Start unserer Labyrinthe ist immer am oberen und das Ziel am unteren Rand."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAR4AAAEeCAYAAABcyXrWAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAAEu0lEQVR4nO3dQW4VMRBAQQZxsBw9OdnnAmAix36xTNU2qNVsnixl1Hler9cPgNLP714A+P8ID5ATHiAnPEBOeICc8AC5X6MfPs/jd+0QeH9//+e/eXt7277HSq/X6/nbz7x4gJzwADnhAXLCA+SEB8gJD5ATHiAnPEDuGd3j+cwHhJ+55/M8f/2OaNkMu3z/HLvMz7l0Fx8QAucQHiAnPEBOeICc8AA54QFywgPkhAfIffkDQoA/8QEhcBThAXLCA+SEB8gJD5ATHiAnPEBu+JdEP+Oww0N2+cY5dpmfc+MuI148QE54gJzwADnhAXLCA+SEB8gJD5ATHiDnEBiwhUNgwFGEB8gJD5ATHiAnPEBOeICc8AA54QFyLhDaZdkcu8zPuXGXES8eICc8QE54gJzwADnhAXLCA+SEB8gJD5BzgRDYwgVC4CjCA+SEB8gJD5ATHiAnPEBOeICcQ2B2WTbHLvNzbtxlxIsHyAkPkBMeICc8QE54gJzwADnhAXLCA+QcAgO2cAgMOIrwADnhAXLCA+SEB8gJD5ATHiAnPEDOBUK7LJtjl/k5N+4y4sUD5IQHyAkPkBMeICc8QE54gJzwADnhAXIuEAJbuEAIHEV4gJzwADnhAXLCA+SEB8gJD5BzCMwuy+bYZX7OjbuMePEAOeEBcsID5IQHyAkPkBMeICc8QE54gJxDYMAWDoEBRxEeICc8QE54gJzwADnhAXLCA+SEB8i5QGiXZXPsMj/nxl1GvHiAnPAAOeEBcsID5IQHyAkPkBMeICc8QM4FQmALFwiBowgPkBMeICc8QE54gJzwADnhAXLCA+RcILTLsjl2mZ9z4y4jXjxATniAnPAAOeEBcsID5IQHyAkPkHMIDNjCITDgKMID5IQHyAkPkBMeICc8QE54gJzwADmHwOyybI5d5ufcuMuIFw+QEx4gJzxATniAnPAAOeEBcsID5IQHyLlACGzhAiFwFOEBcsID5IQHyAkPkBMeICc8QE54gJwLhHZZNscu83Nu3GXEiwfICQ+QEx4gJzxATniAnPAAOeEBcg6BAVs4BAYcRXiAnPAAOeEBcsID5IQHyAkPkBMeIOcQmF2WzbHL/Jwbdxnx4gFywgPkhAfICQ+QEx4gJzxATniAnPAAORcIgS1cIASOIjxATniAnPAAOeEBcsID5IQHyAkPkHOB0C7L5thlfs6Nu4x48QA54QFywgPkhAfICQ+QEx4gJzxATniAnAuEwBYuEAJHER4gJzxATniAnPAAOeEBcsID5BwCs8uyOXaZn3PjLiNePEBOeICc8AA54QFywgPkhAfICQ+QEx4g5xAYsIVDYMBRhAfICQ+QEx4gJzxATniAnPAAOeEBci4Q2mXZHLvMz7lxlxEvHiAnPEBOeICc8AA54QFywgPkhAfICQ+Qc4EQ2MIFQuAowgPkhAfICQ+QEx4gJzxATniAnENgdlk2xy7zc27cZcSLB8gJD5ATHiAnPEBOeICc8AA54QFywgPkvvwB4Vc/JFo1Y9Wck3b5+PhYsMlZ/ye77Juxas6qXUa8eICc8AA54QFywgPkhAfICQ+QEx4gJzxAbviXRAF28OIBcsID5IQHyAkPkBMeICc8QO43kj0ds7h4S88AAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 360x360 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# importiere das Modul \"random\", da der Start und das Ziel im Labyrinth\n",
    "# zufällig festgelegt werden sollen\n",
    "import random\n",
    "\n",
    "# um die Wände und Wege im Labyrinth darzustellen, verwenden wir Objekte\n",
    "# der folgenden Klassen\n",
    "class Wand():\n",
    "    def __init__(self, x, y):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.typ = 'w'\n",
    "    def __str__(self):\n",
    "        return self.typ + ': ' + str(self.x) + '|' + str(self.y)\n",
    "\n",
    "class Pfad():\n",
    "    def __init__(self, x, y):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.ist_in_labyrinth = False\n",
    "        self.typ = 'p'\n",
    "    def __str__(self):\n",
    "        return self.typ + ': ' + str(self.x) + '|' + str(self.y)\n",
    "\n",
    "class Start():\n",
    "    def __init__(self, x, y):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.ist_in_labyrinth = True\n",
    "        self.typ = 's'\n",
    "    def __str__(self):\n",
    "        return self.typ + ': ' + str(self.x) + '|' + str(self.y)\n",
    "\n",
    "class Ziel():\n",
    "    def __init__(self, x, y):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.ist_in_labyrinth = False\n",
    "        self.typ = 'z'\n",
    "    def __str__(self):\n",
    "        return self.typ + ': ' + str(self.x) + '|' + str(self.y)\n",
    "\n",
    "# In dieser Funktion wird ein Labyrinth-Feld erzeugt, das einen zufälligen\n",
    "# Startpunkt und ein zufälliges Ziel hat. Der Start ist immer am oberen\n",
    "# und das Ziel am unteren Rand.\n",
    "# Dieses Labyrinth-Feld hat noch keine Wege, da diese erst vom Algorithmus\n",
    "# hinzugefügt werden sollen.\n",
    "def erstelle_feld(größe):\n",
    "    # zu kleine Labyrinthe sind nicht zulässig\n",
    "    größe = max(5, größe)\n",
    "    \n",
    "    # ein Labyrinth muss immer eine ungerade Anzahl an Wegen und Wänden haben,\n",
    "    # da es rundum umrandet ist\n",
    "    if größe % 2 == 0:\n",
    "        größe += 1\n",
    "    \n",
    "    höhe = größe\n",
    "    breite = größe\n",
    "    \n",
    "    # erzeuge das Labyrinth-Feld, gebe auch das Start- und Zielfeld zurück\n",
    "    feld = []\n",
    "    for y in range(höhe):\n",
    "        zeile = []\n",
    "        for x in range(breite):\n",
    "            if x % 2 == 0 or y % 2 == 0:\n",
    "                zeile.append(Wand(x, y))\n",
    "            else:\n",
    "                zeile.append(Pfad(x, y))\n",
    "        feld.append(zeile)\n",
    "    \n",
    "    # setze den Start und das Ziel zufällig fest\n",
    "    start_index = random.randint(0, (breite - 3) / 2) * 2 + 1\n",
    "    ziel_index = random.randint(0, (breite - 3) / 2) * 2 + 1\n",
    "    start = Start(start_index, 1)\n",
    "    ziel = Ziel(ziel_index, höhe - 2)\n",
    "    feld[1][start_index] = start\n",
    "    feld[höhe - 2][ziel_index] = ziel\n",
    "    return feld, start, ziel\n",
    "\n",
    "# erstelle testweise ein Labyrinth und zeige es an\n",
    "feld, start, ziel = erstelle_feld(30)\n",
    "zeige_labyrinth_an(feld, 5, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prim's Algorithmus\n",
    "\n",
    "Der folgende Pseudocode ist dieser Wikipedia-Seite entnommen (übersetzt und etwas angepasst):\n",
    "\n",
    "https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Prim's_algorithm\n",
    "\n",
    "Hier kannst du dir auch eine Animation anschauen, wie der Algorithmus arbeitet;\n",
    "\n",
    "https://upload.wikimedia.org/wikipedia/commons/b/b1/MAZE_30x20_Prim.ogv\n",
    "\n",
    "Der Algorithmus funktioniert folgendermaßen:\n",
    "\n",
    "<code>1. erzeuge das Labyrinth-Feld, auf dem alle Zwischenwände noch zugemauert sind</code>  \n",
    "<code>2. finde die Zwischenwände der Start-Zelle und schreibe diese in die Liste der Zwischenwände</code>  \n",
    "<code>3. WHILE die Liste der Zwischenwände ist nicht leer:</code>  \n",
    "<code>    3.1 wähle eine zufällige Zwischenwand aus der Liste der Zwischenwände.</code>  \n",
    "<code>    3.2 WENN nur eine der beiden Nachbar-Pfad-Zellen dieser Zwischenwand Teil des Labyrinths ist:</code>  \n",
    "<code>        3.2.1 entferne die Zwischenwand</code>  \n",
    "<code>        3.2.2 markiere die dadurch neu verbundene Zelle als Teil des Labyrinths</code>  \n",
    "<code>        3.2.3 füge die anderen Zwischenwände der neu verbundenen Zelle zur Liste der Zwischenwände hinzu</code>  \n",
    "<code>    3.3 entferne die zufällige Zwischenwand aus der Liste der Zwischenwände.</code>\n",
    "\n",
    "Diesen Pseudocode sollst du im nächsten Codeblock implementieren.\n",
    "\n",
    "Von Prim's Algorithmus werden Labyrinthe zufällig generiert. Dein Labyrinth sollte in etwa so aussehen (Darstellung verkleinert):\n",
    "\n",
    "<img src=\"http://caeze.bplaced.net/bwki/labyrinth2.png\" alt=\"labyrinth_2\" width=\"300\"/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAi0AAAIuCAYAAABzfTjcAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAAerElEQVR4nO3dQZLkOI4FUI+xOVgdvW6Ws5pNtytNNAoEvuK9ZZWHSFGUEkYDwZ8/f/58AACm+5/uDgAA3CFoAQAiCFoAgAiCFgAggqAFAIggaAEAIvzv3/7nz8+P/dDAMf/+++/X//7PP/8c7QfQ68+fPz/f/ruVFgAggqAFAIggaAEAIghaAIAIP387e+hbIu7Us4p+fv47Z+eJvlZdt9O3e/p8vt/X7m+vxqp7XLvny8q4Vvntz2D3mlXXPTlfqt7Zivvq7uuKqvuqMPhbJBEXAMglaAEAIghaAIAIghYAIIKgBQCI8Ncy/iuuMpArVGV2V/z9SsZ8hfSdTp/P/k6EnXauVI1r99zqbv9KxXWT+prU/ludHNcnvkVJ78wKKy0AQARBCwAQQdACAEQQtAAAER5LxP3mZNnk7r+f0NaEJKm7usd7t8x3RZ+u7LZfVRp/tw9Vic/d41XR15VrVr1b3Un9VWNw97dJc/Cpa5xqZ2W8rLQAABEELQBABEELABBB0AIARBC0AAARlncPJZW+rsr2TirNP3VH0cly8xNN6P+EPtw1tYT6Xd1Hj1Q5uaPoN41B1b2mH73x+VhpAQBCCFoAgAiCFgAggqAFAIiwnIj7hhLRFW1NLc1/siR5VVt3S+6fTF574rd3/35qkvfu33cfvfFEQvupPpz8viR9i6tKyE8dg+4jcCYcvWGlBQCIIGgBACIIWgCACIIWACBCaUXcpMqtK0mg3Vb6lFTpt9uERN6pJs6DCc/rbh+qvi8r7+zd+0qvPlx13apk7JPVwSu+8VUxwRUrLQBABEELABBB0AIARBC0AAARBC0AQITHyvhPzIKvUpUtXnHdqccuVGScdx8j8ERbu7/t7sPK3F4Z16rf3nVyJ+TUIyq626860qR7Z1x6Gf/T42qlBQCIIGgBACIIWgCACIIWACDCciLuVFVJWqfar7ruyRLL3X2dWn68u69XJvSh0xP3353IWnWkx293clyn/tsxlZUWACCCoAUAiCBoAQAiCFoAgAiPJeJOqPBZ0c6paqwrprbVXVlxQnXNXbuVoU8mXp9UMQ9PzpcqSZXEv5nQ14pqzxXtT7juhO+LlRYAIIKgBQCIIGgBACIIWgCACIIWACDC8u6hJ7KHT5U9ntDXChP6NLE0fXf7U/pwl77um9qvu5L6P7XcfcWRHm/99+iJHUVWWgCACIIWACCCoAUAiCBoAQAiLCfiViUInSxH3V3Cfbcs+8ozODmuU8uin7yvitLVVe1XHbtQoaKvTxyPMLE0ftV8r5gDVUmc3d/4k6b2teobb6UFAIggaAEAIghaAIAIghYAIIKgBQCIsLx7aIK7Wckns6onlldeVVGOeoLd+XJyZ1y6ql0bSeN1sq+nS6jfVTEG3XPgifbvPoMn2uoerypWWgCACIIWACCCoAUAiCBoAQAiPJaI212+fGpCWlISZvczrLrG7jPoLh/efezD3/pw9+93rll53Yr2p86XbieP0zh53e6/373u1ONyrlhpAQAiCFoAgAiCFgAggqAFAIiwnIh7MuF1N5FnanJukpPPYEVSdc+piZEV3jBWb60MPdEbxuoN93DXhHu10gIARBC0AAARBC0AQARBCwAQQdACAERY3j3UXQL/ykpJ8oo+VJX57i6tX/UMqp7XXVWlt+/e14Sdbd1za+p8qdgRtHs8whNtnfxt5zXfLP27+QQrLQBABEELABBB0AIARBC0AAARlPEv1l3mO6kkedLcOumqr3fHoGpcu5OJu9uf6g1z+64nErcrkuevnPzGVoxt1fNaYaUFAIggaAEAIghaAIAIghYAIIKgBQCI0FLGv6KEelVJ8InlwyfshJiYWd5dknzluhNKb//259XdftV1q/pa8S2q2q12UvoxHd3fgVVWWgCACIIWACCCoAUAiCBoAQAitJTxn5pQddeEJKtvfvu4pt//55OfmHiyLPvudavKsn/z246o2C2NfyqJ9C3X7XT6nqy0AAARBC0AQARBCwAQQdACAERoqYhbcd2T1S1PVkA82dcJVVq/OZWEebKC8skk0CdUVPqteme6k3a7q9xOqJh9yoQK7aeuWWVCRdyVPlhpAQAiCFoAgAiCFgAggqAFAIggaAEAIrSU8a9oK8nK7p3uMdhtv3vXRZqT4z3huqfaSbruyd1mVbvodlW8B1U7/ip+e/I4iytTv0VWWgCACIIWACCCoAUAiCBoAQAiPFbGvyLhcjdp6GR54QnHG5xM2t1NKNtta+d3q79d8dvL3a+YmgT6TXfC6dTvwK633leV7ve76puhjD8A8DqCFgAggqAFAIggaAEAIiwn4j5htwJhRftVf//bE82eGKukcenu629qf3dudSeuX5n63au45krl2N32k36bNAdOs9ICAEQQtAAAEQQtAEAEQQsAEEHQAgBEaNk9tKuipPZu+fCqHUUrujPDu0tMT1VR7v6Jtk7O2anvTEVbJ8unv2Fu7Th57EPVM9jtw9RvYVW/rLQAABEELQBABEELABBB0AIARBiTiFtRCnlqgtJKQld3cu2Kk0liFeNSdYxAd7LjE8+gex7+9vZXnJyvVaYeB7F7zYpvfNVYdSekX7HSAgBEELQAABEELQBABEELABBB0AIARHhs91BFme8JJvarapfLSSvjeve3VWW2u+dAVfsVzyCp/RXdxyNUjdXKjr/d365IOrZhavsVuzlPzsMrVloAgAiCFgAggqAFAIggaAEAIiwn4naXJL+6blUSano56SpTS0/vtDUhwblibp9MljzZ193fTnjfkvq6a+pRLd1Jw93PdvfIgdPfTSstAEAEQQsAEEHQAgBEELQAABGWE3EnVOes+PsJbU0cg+5KoFfXPZn81t3XKyfny8Sk3V0nK5HumtDXt1Yw3q24XaF7/J6gIi4A8KsJWgCACIIWACCCoAUAiCBoAQAiRJbxrzBhl8xuW7uS7uutfa247oTjCe6qKPW++tsKSX29MrFfE+Z2xbN94vu2u5Oxoq9PsNICAEQQtAAAEQQtAEAEQQsAEGF0Gf+rBJ+7v61K0totSV5Vfv3uGKyM6xP9qmhrV1JfV3QnyleN6+77nfQMT6r4Fl5d19Eb+5KOiFihjD8A8DqCFgAggqAFAIggaAEAIghaAIAIY8r4/yZVu3d27T7b7p0IE8uMV7o7X5KOPKh6B7rn9gTd35dvph6R0d1WlZO7j6rGy0oLABBB0AIARBC0AAARBC0AQIQxZfy729o1oa8VZfinJlam9WGHZzD32IXdI0XuSjt64+5v33CUQ8WzTTouZ7f91etaaQEAIghaAIAIghYAIIKgBQCIsJyIe+VkZcMJiYX/6YlEubtjkDRWU6tIViX1nazeWzFfTppaQfnkO9P93Zz6DE6q6MPu3PKNv2alBQCIIGgBACIIWgCACIIWACCCoAUAiPDY7qGKDOaqDOqkkuArKrK4J4zV3fvqzqJfMaGvu7uiKnS3f2VqCfhvqr6bJ5/B7k6jiu9W9/1PaGvCd8tKCwAQQdACAEQQtAAAEQQtAECEMWX8u9uqSgBc+fvuhNOKkuAnEytPlmWveK6fz9xS599UjUGFqX1NGpeJbT2RnJs0Bt1juOuJb7GVFgAggqAFAIggaAEAIghaAIAIghYAIMJju4e+WcnWXtk10V1K+GT7VaWrK/5+14Ts/rsmHLmwu4Nrt61vkt7Zqr6efGd32//mifew4r6qjhxI6utKW1XXvavqu22lBQCIIGgBACIIWgCACIIWACBCaSJulZNl/O+akCw6scRz1bhUlGV/oq+7ibBJJcW735kJc6t7DN46t06qeAZJ979iwjtrpQUAiCBoAQAiCFoAgAiCFgAgwuhE3N0ks+4qnFd9qKrEuVu1tKKtJ3RXYz2ZVNc9Z7urEu9W0b767RN9qPj7ine2ew5d2f0Wds+BqmeQlLRbNbdWxsBKCwAQQdACAEQQtAAAEQQtAEAEQQsAEGH07qHd3SBvyLhPyizX15q2po7r1H7t2v1uJM2t9Paneuu4TLgvKy0AQARBCwAQQdACAEQQtAAAEVoScSuSXqvKJt+9bkXp7qq/r2rrZInnigTIJ/r/1qMUKtqvmlsV72xSUv/J4yxOHvsw4Vu0a+K3f8K4KuMPALyOoAUAiCBoAQAiCFoAgAgtibgVSVonq452V8G8crIPU8egwoQE32/u9utkUuJb58CK7oTVKxPny4qpc2ulX7vPYGVu7fZp6mYHKy0AQARBCwAQQdACAEQQtAAAEQQtAECEx3YPVZQnriqdXZGB/URJ8FPZ2lXtd+86mHCUQnf58qrnVVEan/7x6n6/J5SQ3/Xb+3V6Z5yVFgAggqAFAIggaAEAIghaAIAIjyXiTixHXXXN31TC/kpFOeoq6c+rqq8Tx+CJ8uXdc2vFxGdwpfu7O9XUfztOHm1z8ppWWgCACIIWACCCoAUAiCBoAQAiCFoAgAiP7R76piq7/24G9oTyyif70N1WxXNd0V2SvEpVXyuuu3JERJW7bSX1dYLuMv5V3/iK61Z9C7u/cRPuy0oLABBB0AIARBC0AAARBC0AQITSRNxuVeWRu5O0Tl93x0qfqpLMKsblZPsTn+vnUzMGExIrK+bhhFLvuxsYfvvxCFPfw6n9qmKlBQCIIGgBACIIWgCACIIWACDCz98Snn5+fv7rfyZVcLwytXou5yTNgZXKrelVQ1eSQJ/47V1V1XO7+9r9HiSN6277p/uQ5OJ5fR1EKy0AQARBCwAQQdACAEQQtAAAEQQtAECEx8r4d5d4PlkqvarM9k77E/qw237VfVWUWn+D7ndm95oTjojYbWv37yfsiElv/633tav737krVloAgAiCFgAggqAFAIggaAEAIjyWiPtNd0LbySS1lbaqSjxX3O+EZ1CRxPnWctor97U7Z08mY6841dcrE9/DJ3TfV9U7O/FbMPU9qBqrlT5YaQEAIghaAIAIghYAIIKgBQCIIGgBACKU7h66cqrM9RNZ0Sez9u+2ldTXqmfwxG6tU7rLYSfNl6q/r2qrol9Vc/uNz+Dk0R9P3H/3jtqKtk5/X6y0AAARBC0AQARBCwAQQdACAER4LBG3qnx4t5Olq5PK+N9NVDuZpDVhXu0mr61c82QZ/Yr7WlFx3QlHb5xMGE3/vuw6OberSuNPfQ9221LGHwB4HUELABBB0AIARBC0AAARHkvEPZmE2V1h9KS33tc3VdU9u5OGu59hVfsVz2CC7uTaCc/rru53pirxu/sZTKhiPZWVFgAggqAFAIggaAEAIghaAIAIghYAIMJju4d2nSxJ3q37vqaW+V7JmD+5G6W7fHn3fDl53d05sPrb3X7t/rZibk/YUXO3DxO+Rd3/Tkx9v7+ZsHvJSgsAEEHQAgBEELQAABEELQBAhOVE3AmJOBUloickgU4s/52UJHbl7j1MmNsnTZwvVU4maXePwcn2u8vdr6j6xlfMgQn/nkxr5/9ZaQEAIghaAIAIghYAIIKgBQCIsJyI+0Ri5d1rTEjivGtCX09WKP2muyJtRSXS1d92664EOqH6bkU11u6KtN3PdYK3vocnTe3XCistAEAEQQsAEEHQAgBEELQAABEELQBAhOXdQ1e6S1d/czJT+on7n1gSfFdVOerusdrdTZJU/vxK9zOY4FS5+d82rru6dxqdLPm/e19V7Vc9AystAEAEQQsAEEHQAgBEELQAABEeS8TtLg/cnahWVe6+YlxXksSqnEpgfKL9iutOKHe/e5TBiu7vw66q/nfPlxXdR190f+OrdH+3JhzVssJKCwAQQdACAEQQtAAAEQQtAEAEQQsAEKG0jP9uZvlupvLK359sa/caVTs8Tl3zCVNL9u9ec+U96C73XvF+ndy99JtKrV/1ofv9TvrGV123qtx995z95olnYKUFAIggaAEAIghaAIAIghYAIMJjibgVppau/qa7zHdVH956Xyu621/RXRL8pJMJ6d2lzt/6XE9+X3bb6p4Dq+72t6qvVeNlpQUAiCBoAQAiCFoAgAiCFgAgwuhE3AnJTHdN6OtupeGJFTOf6MPd+zqZ2HnlZJXZFRPmwY6qyqunkh1323+iDxUm9Gni+32ywvru359+hlZaAIAIghYAIIKgBQCIIGgBACIIWgCACKN3D105WXr61M6Vq992m9CnpHLUFarmy8rfd4/Bru6dcSfHL+lZ7e5+euJeK8ar6p1NOqKhaoemlRYAIIKgBQCIIGgBACIIWgCACMuJuFXJa6dKDj9h6hhU2C35P6E0/q7d+6pKxt4t43/yeVXMl+5Ew8+nv9R5xXWT3tmJfVo19d++7uT1K1ZaAIAIghYAIIKgBQCIIGgBACIIWgCACMu7h6aWTZ6wk+Cuqr5OyOy+62Tp7HQVO4qq+uAZZEkqC/9W3UcZpM0BKy0AQARBCwAQQdACAEQQtAAAEZYTca9MLAm+e82r61aVN94tdT7RE0lep8pcr7TzhmMjTvYh6Rm8tTR+RTL1hPuq8IZv/MTjAZ64LystAEAEQQsAEEHQAgBEELQAABEeS8RdcTIhbPe6Ke1PUDUG3YnH3cnQE+ZW9zM4aSUJc3dcuitDJ72z3Qmrb3gPT77HVWNgpQUAiCBoAQAiCFoAgAiCFgAggqAFAIjQsnvoVHnhN2RKn1TxXCaUo75r6k6K3Z0rE0rj33Xy6I8ndI/XrpOl3k/uyqp4LlV9XWmrwtR364qVFgAggqAFAIggaAEAIghaAIAIo8v4r5iaEDex/PmEctQrdhNOVxIAn+7TaScTTtOPMli5Zve4Vs3tpATlpBL2K7r7lfbvgZUWACCCoAUAiCBoAQAiCFoAgAiRFXG7E5dWTEiK+09TKzt2j1VSX68kVdL8pqoi7qlrXpnwzdpNUJ44t9KSSLv7ULEp4XTFbSstAEAEQQsAEEHQAgBEELQAABEELQBAhJbdQ99MyK6v8Nb7+mY3k/9kme7uvlZRbr5m58mKivt6oq8Tj7Oo2v3Tvbtwwvfh1A6sJ+51ZWyttAAAEQQtAEAEQQsAEEHQAgBEGJOI+81uufnukslXTt7XyRLLu0lau4luu0mgby0JvlKWfUIC4TcVfU16hiedPM6i6v67E4ynHhEx8SiGVVZaAIAIghYAIIKgBQCIIGgBACIIWgCACKN3D62YmkG9q3s3x9Qs+JOSSoJXPa+T5ea7ndw50j1e3SXcJ5Txr3hnqsa1e1dUVVvK+AMAryNoAQAiCFoAgAiCFgAgQmQiblIi7cnS+BNLNJ8sCb573QnzqmIMTh7lcKW7rxXv4RPuvt+7R1SctntfO+1cOZmcO/FbvPr3Fc/riURgKy0AQARBCwAQQdACAEQQtAAAEUYn4nZXa1zRXYHxym5S34qqZ3B3vLqri66oSn6rGoOKxMqk5zX1/f7m5BzYNaGvFUniVfc18Z05vTHESgsAEEHQAgBEELQAABEELQBABEELABBh9O6hk6Wzq66ZtOvgmzc8g7fa3VU1sdT4hL52l8Y/efTFyXL1SX3tvm7VezBx99EqKy0AQARBCwAQQdACAEQQtAAAEUYn4p5MYp2QoLTbh7t//8S9ViTK7SafTXiGFareg4rxmtDX7iMHTpaQ736GV7qfwYqK40fSntfEtq5YaQEAIghaAIAIghYAIIKgBQCIIGgBACKU7h6qKru8m3H/RB8qnCoH/YZy90mls3f7MLV8+UpfK97Zk7tJqpx8tlU7YipM/EadPKpl6vEvE75FVloAgAiCFgAggqAFAIggaAEAIjyWiNudOJRU8r+iJHlV+1XXrfjtSqJc9xyY2taVU8l+U5OhV3SX8T+ZeH2l+/2q+G6u6D72YUV3+6t9sNICAEQQtAAAEQQtAEAEQQsAEGE5EXdCpcKJVQVPJsrtJk5NeIbfrCRhdiekTa0yuzJWu+PaPV5JlUBPX7eire7vxsn52r2xpKqtqfe1wkoLABBB0AIARBC0AAARBC0AQARBCwAQYXn30ISS4rs7YqZmUHeP7cmdKxWqjhGoMDUz/0r3eHW3f+XUERETvm8Vz2Dq92H3ulW7SSue7cnS/E8c02GlBQCIIGgBACIIWgCACIIWACDCciLulZPlhXd1J4xeqUjO7L6vpBLXKyaUxq+QdERE97EPK97wHnTPzW+e6NNb7+vkdU+y0gIARBC0AAARBC0AQARBCwAQ4bFE3G92k9+6k+dOS7/f7v6frOy4a0Jybnp1zV1VFZS7x/Vk5dcrFcnQVQnW3ZV+u8d1RVWV2xVWWgCACIIWACCCoAUAiCBoAQAiCFoAgAilu4euTCwlPKFs8u5Ogu5xPZlZvlJC/u5vk3a+PHHdUzs8rq5b0f8nflvR16px3e1D926Qk+/G7rEPJ5/BE7rnbBUrLQBABEELABBB0AIARBC0AAARWhJx7yb4rCT1VbT/tz7stNV9X7tJiVWmJn6tqLiHk8mtJ3U/76r34OT7NfX97D72ocLUObB73aRvxudjpQUACCFoAQAiCFoAgAiCFgAggqAFAIiwvHvoiUzjk+W7K3SXXa4qs909rldOlty/q6os/MndR92m9uubqueV9M5OLONftaOne2fZyeNPrkx9P620AAARBC0AQARBCwAQQdACAERYTsR9IlGwu4x/t+6yzSve+gxWdCevrbTf3dcVVXNoYuL2laR3tqKvSaXxu5Nzq66b9O/R52OlBQAIIWgBACIIWgCACIIWACDCciLulZXkt1NVIKvar7JSObXzmk9d41T73VVHq/7+7rOdkJzbnaDcncR55e7zOvlcVr6bEyq3VrS/a2oF5VPXvPLEu2WlBQCIIGgBACIIWgCACIIWACCCoAUAiPDY7qEVFWX8q7LVu0uCJ5VtXnFyV9TufOkuCX7SxFLvn0//bpSpku7r5K6o3e/m1HFN+veg6tlaaQEAIghaAIAIghYAIIKgBQCI0JKIeyoJcUJJ8oqE0apS0CcTnL+ZmpxqDPbLzVfMraqjHJKeV3dCeZWKuXHyu1nl5DvT/c5esdICAEQQtAAAEQQtAEAEQQsAEEHQAgBEaNk99M3U8uFJGfcVqnZSVIzr1OMVJlx3ou57TdpR1N3+qorv+YT7mugN372VZ2ulBQCIIGgBACIIWgCACIIWACBCaSJuVZntu66Shk4mdFUkLp0c193S1VVjvVtC/psn+tpdZnv3mietlFrvvoeT7b/hXivK6L/B3bHt/rfz8+k/1uWKlRYAIIKgBQCIIGgBACIIWgCACI8l4p5MOE2vprqiO5F3xW7Vzu5n8EQS6MTnNTW5dcXEcf18Zlbyfmul3yRV38KK7+aE5NoVVloAgAiCFgAggqAFAIggaAEAIghaAIAIj+0eOlmSu7ukdkV54932K/twqq2kXQ8Tdt5M6MNdFeXLq3ZYdH+fqr4v3fMl6YiKCWX0d53q1+ndlVZaAIAIghYAIIKgBQCIIGgBACI8loi7Sznnc22dTHideP+fz9zS/CtJmBPfmao+nUx2nHhMyBNz++7cqnqGE8f1qWucUjGPkjZAfD5WWgCAEIIWACCCoAUAiCBoAQAiCFoAgAjLu4dOljd+YodFhe4y3yvX3c02n1Am+xtHKXzXPTenvofdZdm758WKqc9w9+93j32Y+u/Ryd1P3UdkfD5WWgCAEIIWACCCoAUAiCBoAQAiLCfi/qaSx1UmlEK+62RfT5Y6P6n7vnYTEK9+u9uH3faf+C3/7Ymxujtfko4JWfGG4yx2Vf3bYaUFAIggaAEAIghaAIAIghYAIMJyIu6V7iTMFVOrsd4dg6lViXftVrfcrVhZlThWdV/dpvbrm7c+g6mVoe/+/ZWplbxT2n/C3Xs4fa9WWgCACIIWACCCoAUAiCBoAQAiCFoAgAiP7R76pqokeIWTpdZPZtHvtl/lrUcZJLW/ct2KPpxs/+QYVpSb7/5mrKrYCbnr5LhMKON/tw8T5osy/gDA6whaAIAIghYAIIKgBQCIsJyI250UueINpdZXkvoqEgCvVBwPMCEh7JvdZ7Ciu4T87tyqOkqh6jiKb5KOFKmYGxM2FZwsIZ/+DK5MfGefuC8rLQBABEELABBB0AIARBC0AAARlhNxn0iU666uWZEglFThdcVb7+uk3eTaqcnUJ3UnaVdV7z1Z8frkPLx73Qlze7d678lqx1hpAQBCCFoAgAiCFgAggqAFAIggaAEAIizvHnrC7u6dk5npFWXZk+xmzJ883uBkH05m/L9hDp489qH72IOKUudJ8+2JtirGYMJ9Vfx9929P736y0gIARBC0AAARBC0AQARBCwAQ4bFE3JPJft2Jhd3tJ3lirLrLbHcnib/hKIX070P3uFaN34Qy+nclfXeT+lql6p2x0gIARBC0AAARBC0AQARBCwAQQdACAET4+VuW88/Pz3/9z3///ffrb//555+n+gQA/GJ//vz5uv3ISgsAEEHQAgBEELQAABEELQBAhL8m4gIATGGlBQCIIGgBACIIWgCACIIWACCCoAUAiCBoAQAi/B//zllEY8qOwAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 720x720 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Diese Funktion sucht im Feld nach der Zelle an Position (x, y) und gibt diese zurück.\n",
    "# Wenn die Zelle nicht gefunden wurde, weil (x, y) außerhalb des Felds ist, wird \"None\"\n",
    "# zurückgegeben.\n",
    "def finde_zelle(feld, x, y):\n",
    "    if x < 0 or y < 0 or y >= len(feld) or x >= len(feld[y]):\n",
    "        return None\n",
    "    return feld[x][y]\n",
    "\n",
    "# Diese Funktion gibt alle Wände (schwarz) zurück, die zu der Zelle \"pfad_zelle\" gehören.\n",
    "# Die Zelle \"pfad_zelle\" muss ein Pfad sein (weiß)!\n",
    "def finde_wände_des_pfads(feld, pfad_zelle):\n",
    "    x = pfad_zelle.x\n",
    "    y = pfad_zelle.y\n",
    "    wände = []\n",
    "    wand_oben = finde_zelle(feld, x, y - 1)\n",
    "    wand_unten = finde_zelle(feld, x, y + 1)\n",
    "    wand_links = finde_zelle(feld, x - 1, y)\n",
    "    wand_rechts = finde_zelle(feld, x + 1, y)\n",
    "    if wand_oben != None:\n",
    "        wände.append(wand_oben)\n",
    "    if wand_unten != None:\n",
    "        wände.append(wand_unten)\n",
    "    if wand_links != None:\n",
    "        wände.append(wand_links)\n",
    "    if wand_rechts != None:\n",
    "        wände.append(wand_rechts)\n",
    "    return wände\n",
    "\n",
    "# Diese Funktion gibt die zwei Pfad-Zellen (weiß) auf den beiden Seiten einer Zwischenwand (schwarz) zurück.\n",
    "# Eine Zwischenwand-Zelle hat immer nur maximal zwei Pfad-Zellen als Nachbarn!\n",
    "def finde_pfade_der_wand(feld, wand_zelle):\n",
    "    x = wand_zelle.x\n",
    "    y = wand_zelle.y\n",
    "    pfade = []\n",
    "    pfad_oben = finde_zelle(feld, x, y - 1)\n",
    "    pfad_unten = finde_zelle(feld, x, y + 1)\n",
    "    pfad_links = finde_zelle(feld, x - 1, y)\n",
    "    pfad_rechts = finde_zelle(feld, x + 1, y)\n",
    "    if pfad_oben != None and (pfad_oben.typ == 'p' or pfad_oben.typ == 's' or pfad_oben.typ == 'z'):\n",
    "        pfade.append(pfad_oben)\n",
    "    if pfad_unten != None and (pfad_unten.typ == 'p' or pfad_unten.typ == 's' or pfad_unten.typ == 'z'):\n",
    "        pfade.append(pfad_unten)\n",
    "    if pfad_links != None and (pfad_links.typ == 'p' or pfad_links.typ == 's' or pfad_links.typ == 'z'):\n",
    "        pfade.append(pfad_links)\n",
    "    if pfad_rechts != None and (pfad_rechts.typ == 'p' or pfad_rechts.typ == 's' or pfad_rechts.typ == 'z'):\n",
    "        pfade.append(pfad_rechts)\n",
    "    return pfade\n",
    "\n",
    "# In dieser Funktion wird das Labyrinth erstellt.\n",
    "# Dazu sollst du Prim's Algorithmus implementieren.\n",
    "def prims_algorithmus(größe):\n",
    "    feld, start, ziel = erstelle_feld(größe)\n",
    "    wände = finde_wände_des_pfads(feld, start)\n",
    "    while len(wände) != 0:\n",
    "        wand_index = random.randint(0, len(wände) - 1)\n",
    "        wand = wände[wand_index]\n",
    "        pfade = finde_pfade_der_wand(feld, wand)\n",
    "        if len(pfade) == 2 and pfade[0].ist_in_labyrinth and not pfade[1].ist_in_labyrinth:\n",
    "            wand.typ = 'p'\n",
    "            pfade[1].ist_in_labyrinth = True\n",
    "            wände += finde_wände_des_pfads(feld, pfade[1])\n",
    "        if len(pfade) == 2 and pfade[1].ist_in_labyrinth and not pfade[0].ist_in_labyrinth:\n",
    "            wand.typ = 'p'\n",
    "            pfade[0].ist_in_labyrinth = True\n",
    "            wände += finde_wände_des_pfads(feld, pfade[0])\n",
    "        del wände[wand_index]\n",
    "    return feld\n",
    "\n",
    "labyrinth = prims_algorithmus(100)\n",
    "zeige_labyrinth_an(labyrinth)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wunderbar! Nun haben wir endlos viele Testmöglichkeiten für die nächste Aufgabe. In dieser Aufgabe werden wir Graphen aus den Labyrinthen machen und dann den Weg vom Start zum Ziel suchen."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fragen & Feedback:\n",
    "\n",
    "**Wenn ihr Fragen oder Anregungen zu der Aufgabe (oder Lösung) habt, dann tauscht euch gerne im [Chat](https://spectrum.chat/bwki/aufgabenarchiv/) darüber aus oder schreibt uns eine E-Mail (an info@bw-ki.de).**\n",
    "\n",
    "Wir freuen uns auch immer über **Feedback** (auch unter info@bw-ki.de):\n",
    "\n",
    "- War diese Aufgabe zu leicht, zu schwer oder genau richtig?\n",
    "- Wie lang hast du für diese Aufgabe ungefähr gebraucht?\n",
    "- Welche Art von Aufgaben wünschst du dir in Zukunft?"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda env:bwki_env]",
   "language": "python",
   "name": "conda-env-bwki_env-py"
  },
  "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.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}