11-Aufgabe.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Landwirt, Ziege, Wolf und Kohl - aber nur ein Boot\n",
    "### - Aufgabe - "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Fährt der Landwirt mit dem Kohl, frisst der Wolf die Ziege wohl\n",
    "\n",
    "So könnte eine Bauernregel lauten. Jedenfalls wenn es eine Regel für unsere heutige Aufgabe gäbe: es geht um einen Landwirt, eine Ziege, einen Wolf und einen Kohl.\n",
    "\n",
    "Der Landwirt will nun mit allen diesen einen Fluss überqueren, aber er kann nicht schwimmen. Auch seine Begleiter sind nicht gut im Nassen: der Kohl treibt im Wasser ab, der Wolf nimmt allein im Strom reißaus und die Ziege hat eine Wasserphobie. Jedoch findet sich ein Boot am Ufer, das aber nur Platz für den Landwirt und eines der anderen bietet. Nimmt der Landwirt also z. B. den Wolf und den Kohl zugleich mit, kentert er.\n",
    "\n",
    "![landwirt_ziege_wolf_kohl_1.png](http://caeze.bplaced.net/bwki/landwirt_ziege_wolf_kohl_1.png)\n",
    "\n",
    "Auf der anderen Seite kann er seine Begleiter nicht unbewacht lassen: ist die Ziege allein mit dem Kohl an einem Ufer, so frisst sie diesen. Und wenn der Wolf alleine mit der Ziege an einem Ufer ist, so bleiben nachher nur die Hörner übrig.\n",
    "\n",
    "Die Frage ist nun, wie kann der Landwirt mit den drei anderen den Fluss überqueren? Er muss also mehrfach fahren.\n",
    "\n",
    "Du kannst nun das Problem zuächst auf einem Blatt Papier lösen. Gib deine Lösung im nächsten Textfeld an."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lösung:\n",
    " - Landwirt fährt ... zum Zielufer\n",
    " - Landwirt fährt ... zum Startufer\n",
    " - ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Wenn alle Ideen im Fehlschlag enden, muss man brutale Kraft verwenden\n",
    "\n",
    "Jetzt wollen wir das Problem mit einer Methode lösen, die einen ungestümen Namen trägt: wir wenden die Brute-Force-Methode an. Diese wird auch erschöpfende Suche genannt. Die Idee ist dabei einfach folgende: man testet alle möglichen Kombinationen von Lösungsmöglichkeiten zu einem Problem durch und gibt das Ergebnis zurück, sobald es dabei gefunden wurde. Wenn es kein Ergebnis gibt, wird die Suche danach erst abgebrochen, wenn alle Möglichkeiten durchprobiert wurden.\n",
    "\n",
    "Hier findest du weitere Informationen zu diesem Verfahren: https://de.wikipedia.org/wiki/Brute-Force-Methode.\n",
    "\n",
    "Für die Brute-Force-Methode brauchen wir zwei Hauptbestandteile: man muss alle Lösungsmöglichkeiten aufzählen können und es muss möglich sein, zu erkennen, ob eine Lösungsmöglichkeit das richtige Ergebnis geliefert hat.\n",
    "\n",
    "Wollen wir uns zuerst um zweiteres kümmern."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# unsere Datenstrukturen sind folgende:\n",
    "# es gibt zwei Listen, in denen enthalten ist, wer sich gerade an welchem Ufer befindet\n",
    "# am Anfang sind alle vier am Startufer und niemand ist am Zielufer\n",
    "landwirt = \"Landwirt\"\n",
    "ziege = \"Ziege\"\n",
    "wolf = \"Wolf\"\n",
    "kohl = \"Kohl\"\n",
    "\n",
    "start_ufer = [landwirt, ziege, wolf, kohl]\n",
    "ziel_ufer = []\n",
    "\n",
    "# außerdem wird festgelegt, wer nicht zusammen an einem Ufer sein darf,\n",
    "# ohne dass der Landwirt dabei ist\n",
    "nicht_zusammen = [[ziege, wolf], [ziege, kohl]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# schreibe hier eine Funktion, die aus dem aktuellen Zustand dieser Datenstrukturen zurückgibt,\n",
    "# ob das Vorhaben noch Erfolg haben kann. Das Vorhaben scheitert, wenn entweder die Ziege oder\n",
    "# der Kohl gefressen wurden\n",
    "def erfolg_noch_möglich(aktueller_zustand_start_ufer, aktueller_zustand_ziel_ufer):\n",
    "    alle_ufer = [aktueller_zustand_start_ufer, aktueller_zustand_ziel_ufer]\n",
    "    for ufer in alle_ufer:\n",
    "        for lebewesen in nicht_zusammen:\n",
    "            if ...:\n",
    "                return False\n",
    "    return True\n",
    "\n",
    "# beim Ausgangszustand sollte das Vorhaben noch möglich sein, der Landwirt ist ja schließlich dabei\n",
    "print(erfolg_noch_möglich(start_ufer, ziel_ufer))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mit dieser Funktion können wir jetzt überprüfen, ob eine Lösungsmöglichkeit zum Fehlschlag des Vorhabens führt. Wir müssen nun noch eine Funktion schreiben, mit der wir überprüfen, ob das Vorhaben erfolgreich war, also ob alle vier an das andere Ufer gelangt sind."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# schreibe hier eine Funktion, die zurückgibt, ob das Vorhaben Erfolg hatte,\n",
    "# d. h. dass alle vier am Zielufer angekommen sind\n",
    "# Hierbei ist wichtig, dass die Reihenfolge, in der die Begleiter und der \n",
    "# Landwirt am Zielufer stehen egal ist. Beim Vergleichen von Listen wird in Python\n",
    "# aber auch die Reihenfolge der Elemente geprüft. Du kannst mit der Funktion \"set()\"\n",
    "# eine Menge aus der Liste erzeugen; in Mengen ist die Reihenfolge der Elemente unerheblich.\n",
    "def erfolg(aktueller_zustand_ziel_ufer):\n",
    "    return ...\n",
    "\n",
    "# beim Ausgangszustand sollte das Vorhaben noch nicht erfolgreich sein, da noch niemand gefahren ist\n",
    "print(erfolg(ziel_ufer))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nun fehlt noch der Kernbestandteil des Brute-Force-Verfahren: wir müssen alle Lösungsmöglichkeiten durchprobieren, also in der Lage sein, alle möglichen Lösungen aufzuzählen. Das ist oftmals aber gar nicht trivial oder überhaupt möglich, auch in diesem Beispiel nicht.\n",
    "\n",
    "Dazu ein Beispiel: der Landwirt könnte einmal mit der Ziege hin- und her fahren; Wolf und Kohl würden dabei einfach am Startufer verbleiben. Er könnte aber auch zweimal hin- und her fahren, oder dreimal, oder n-mal. Das bringt den Landwirt zwar nicht so recht weiter, aber es ist eine valide Möglichkeit, bei der das Vorhaben jeweils noch nicht gescheitert ist. Und wir müssten für eine vollständige Aufzählung aller Möglichkeiten auch alle diese Fahrten mit einbeziehen. Aber unendlich viele Elemente aufzählen ist in endlicher Zeit schlicht nicht möglich. Was können wir also tun? Erst schauen wir uns noch ein paar Grundlagen an.\n",
    "\n",
    "Wir beschreiben das Vorhaben des Landwirts als Suchproblem in einem Suchbaum. Den Suchbaum kann man auch Graphen nennen. Dabei ist jede Überfahrtmöglichkeit des Landwirts ein Ast im Baum. Jedoch bedeuten viele Äste den Fehlschlag des Vorhabens. Sobal Ziege und Wolf oder Ziege und Kohl zusammen sind, muss der Ast nicht weiter betrachtet werden.\n",
    "\n",
    "![landwirt_ziege_wolf_kohl_2.png](http://caeze.bplaced.net/bwki/landwirt_ziege_wolf_kohl_2.png)\n",
    "\n",
    "Der Landwirt kann also alleine fahren, er kann mit dem Kohl fahren, mit dem Wolf oder mit der Ziege. Nur die letzte Option ist valide.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Von dort aus kann der Landwirt wieder mit der Ziege zurück fahren oder alleine (\"leer\").\n",
    "\n",
    "![landwirt_ziege_wolf_kohl_3.png](http://caeze.bplaced.net/bwki/landwirt_ziege_wolf_kohl_3.png)\n",
    "\n",
    "Fährt der Landwirt alleine wieder zurück, so kann er daraufhin den Kohl oder den Wolf mitnehmen. Es gibt also weitere Äste im Baum, die wir untersuchen müssen, und jeweils deren Äste wieder.\n",
    " \n",
    "Fährt der Landwirt allerdings mit der Ziege wieder zurück, ergibt sich eine Situation, die bereits vorhanden war, was in diesem Fall die Ausgangssituation ist. Man nennt dies einen Zyklus im Graphen. Das ist schlecht, da wir nun genau das Problem im Beispiel von oben mit der unendlichen Aufzählung erhalten.\n",
    "\n",
    "Dagegen können wir allerdings etwas unternehmen: wir speichern uns alle vorgekommenen Situationen und verwerfen auch solche, die valide wären, aber bereits vorgekommen sind.\n",
    "\n",
    "Schreibe dazu eine Funktion, die überprüft, ob die aktuelle Situation schon einmal vorhanden war. Dazu brauchen wir noch eine Funktion, die den aktuellen Zustand speichern kann."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# in dieser Liste werden alle bereits vorgekommenen Situationen abgelegt\n",
    "# das Format ist folgendes:\n",
    "# [[start_ufer, ziel_ufer], [start_ufer, ziel_ufer], [start_ufer, ziel_ufer], ...]\n",
    "#        Situation 1              Situation 2             Situation 3\n",
    "situationen = []\n",
    "\n",
    "# überprüfe, ob die aktuelle Situation von \"start_ufer\" und \"ziel_ufer\" schon einmal vorhanden war\n",
    "# du kannst Listen in Python mit \"==\" vergleichen. Beim Vergleichen von Listen wird in Python\n",
    "# aber auch die Reihenfolge der Elemente geprüft. Du kannst mit der Funktion \"set()\"\n",
    "# eine Menge aus der Liste erzeugen; in Mengen ist die Reihenfolge der Elemente unerheblich.\n",
    "def situation_bereits_vorhanden(aktueller_zustand_start_ufer, aktueller_zustand_ziel_ufer):\n",
    "    for situation in situationen:\n",
    "        if ...:\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "# speichere die aktuelle Situation; die Liste der Situationen soll aber keine Duplikate enthalten\n",
    "# überprüfe daher mit der Funktion \"situation_bereits_vorhanden()\", ob die Situation überhaupt\n",
    "# noch hinzugefügt werden muss\n",
    "# Du musst dabei Kopien der Listen hinzufügen; dazu kannst du die Funktion \"liste.copy()\" verwenden.\n",
    "# Wenn du nur eine Referenz auf eine bestehende Liste hinzufügst, können sich die Inhalte verändern,\n",
    "# was aber bei einem Speicher der vorgekommenen Situationen ungewollt ist.\n",
    "def speichere_situation(aktueller_zustand_start_ufer, aktueller_zustand_ziel_ufer):\n",
    "    bereits_vorhanden = ...\n",
    "    if not bereits_vorhanden:\n",
    "        situationen.append([....copy(), ....copy()])\n",
    "    return bereits_vorhanden"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Jetzt können wir alle invaliden Situationen erkennen: wenn Ziege und Wolf oder Kohl und Ziege zusammen sind oder wenn eine bereits aufgetretene Situation erneut auftritt.\n",
    "\n",
    "Schreibe nun die Funktion, die den gesamten Suchbaum nach der Lösung durchsucht, so dass alle vier am Zielufer ankommen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# In dieser Funktion wird die Funktionalität der Überfahrt von einem Flussufer zum anderen\n",
    "# implementiert. Dazu wird der Funktion das Start- und Zielufer und der Beifahrer des Landwirts\n",
    "# übergeben. Der Beifahrer kann auch 'None' sein, dann fährt der Landwirt alleine.\n",
    "# Nach einem Check, ob die Parameter Sinn ergeben, wird nun der Landwirt und evtl. sein Beifahrer\n",
    "# vom Startufer entfernt und an das Zielufer geschrieben. Damit ist er über den Fluss 'gefahren'.\n",
    "def überfahrt(ablegen_von_ufer, ankommen_an_ufer, beifahrer):\n",
    "    if beifahrer == None:\n",
    "        if landwirt not in ablegen_von_ufer:\n",
    "            print(\"Fehler: der Landwirt ist gar nicht an diesem Ufer!\")\n",
    "            print(\"Also kann er auch nicht leer davon überfahren!\")\n",
    "            return\n",
    "        ablegen_von_ufer.remove(...)\n",
    "        ankommen_an_ufer.append(...)\n",
    "    else:\n",
    "        if landwirt not in ablegen_von_ufer or beifahrer not in ablegen_von_ufer:\n",
    "            print(\"Fehler: der Landwirt oder der Beifahrer sind gar nicht an diesem Ufer!\")\n",
    "            print(\"Also können sie auch nicht davon überfahren!\")\n",
    "            return\n",
    "        ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Suche im Suchbaum wird rekursiv ausgeführt.\n",
    "\n",
    "Bei einem rekursiven Aufruf ruft eine Methode sich selbst auf. Der Zweck, zu dem man Rekursion benutzt ist meistens, dass man ein komplexes Problem hat, das man nicht auf Anhieb lösen kann. Wenn das Problem nun aus kleineren (selbstähnlichen) Teilen aufgebaut ist, kann man es in diese Teilprobleme unterteilen. Diese Teile kann man nun jeweils lösen und dann die Lösungen zur Gesamtlösung zusammenbauen.\n",
    "\n",
    "Du kannst dich hier in die rekursive Programmierung einlesen:\n",
    "\n",
    "https://perlgeek.de/de/artikel/rekursion\n",
    "\n",
    "https://www.python-kurs.eu/python3_rekursive_funktionen.php\n",
    "\n",
    "https://www.freecodecamp.org/news/how-recursion-works-explained-with-flowcharts-and-a-video-de61f40cb7f9/\n",
    "(leider nur auf Englisch und anhand von JavaScript erklärt, aber sehr anschaulich)\n",
    "\n",
    "Dazu im Folgenden ein einfaches Beispiel, das zunächst nichts mit der Aufgabe zu tun hat. In diesem Beispiel wollen wir ausgehend vom angegebenen Verzeichnis rekursiv alle darunterliegenden Verzeichnisse nach der Datei \"Brief_an_Oma.txt\" durchsuchen. Das Dateisystem eines Computers ist nämlich auch als Baum aufgebaut und kann deshalb auf dieselbe Art durchsucht werden, wie der Suchbaum in unserer Aufgabe."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%%script false --no-raise-error\n",
    "# diese Funktion kann nicht laufen, da die benötigten\n",
    "# Aufrufe gar nicht existieren. Führe diese Zelle deshalb nicht aus.\n",
    "\n",
    "# eine Beispielfunktion für eine rekursive Suche im Dateisystem\n",
    "def suche_datei_rekursiv(aktuelles_verzeichnis, zu_findende_datei):\n",
    "    # wir fangen beim aktuellen Verzeichnis an und holen alle\n",
    "    # Dateien und Verzeichnisse, die darin liegen\n",
    "    for element in alle_dateien_und_verzeichnisse(aktuelles_verzeichnis):\n",
    "        # wenn das aktuelle Element eine Datei ist, überprüfen wir den\n",
    "        # Dateinamen, ob die Suche schon erfolgreich war\n",
    "        if element.ist_datei():\n",
    "            if element.name() == zu_findende_datei:\n",
    "                return element\n",
    "        # wenn das aktuelle Element selbst ein Verzeichnis ist,\n",
    "        # so nehmen wir dieses als neuen Startpunkt für eine weitere\n",
    "        # Suche nach der Datei. Wir geben das Ergebnis dieser \"Unter-Suche\"\n",
    "        # dann zurück\n",
    "        if element.ist_verzeichnis():\n",
    "            return suche_datei_rekursiv(element, zu_findende_datei)\n",
    "            \n",
    "suche_datei_rekursiv(\"/home/Benutzer\", \"Brief_an_Oma.txt\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Betrachte nun folgendes Dateisystem:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# /home/Benutzer\n",
    "# ├─Bilder\n",
    "# │ ├─Bild1.jpg\n",
    "# │ └─Bild2.jpg\n",
    "# ├─Musik\n",
    "# │ ├─ABBA\n",
    "# │ │ └─Waterloo.mp3\n",
    "# │ └─Beatles\n",
    "# │   └─Yesterday.mp3\n",
    "# └─Dokumente\n",
    "#   ├─Brief_an_Oma.txt\n",
    "#   └─Brief_an_Mama.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Funktion würde zunächst die Liste \\[\"Bilder\", \"Musik\", \"Dokumente\"\\] vom ersten Aufruf von alle_dateien_und_verzeichnisse(aktuelles_verzeichnis) erhalten.\n",
    "\n",
    "Daraufhin würde 'suche_datei_rekursiv(\"/home/Benutzer/Bilder\", \"Brief_an_Oma.txt\")' aufgerufen, worin nur \"Bild1.jpg\" und \"Bild2.jpg\" betrachtet und verworfen werden.\n",
    "\n",
    "Daraufhin wird im Verzeichnis \"Musik\" zunächst das Verzeichnis \"ABBA\" und darin die Datei \"Waterloo.mp3\" und daraufhin das Verzeichnis \"Beatles\" und die Datei \"Yesterday.mp3\" untersucht.\n",
    "\n",
    "Dann wird das Verzeichnis \"Dokumente\" untersucht und die Datei \"Brief_an_Oma.txt\" betrachtet. Der Vergleich liefert \"True\" und nun wird der Rückgabewert \"/home/Benutzer/Dokumente/Brief_an_Oma.txt\" wieder zurück nach oben gegeben.\n",
    "\n",
    "Die Datei \"Brief_an_Mama.txt\" wird nicht mehr betrachtet."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hat die Ziege plötzlich ein verästeltes Geweih, war wohl Rekursion dabei\n",
    "Jetzt geht es ans Eingemachte. In der folgenden Funktion wird die rekursive Suche im Baum implementiert. Die Idee dabei ist Folgende:\n",
    "\n",
    " - zunächst werden Abbruchbedingungen überprüft:\n",
    "     - erfolg() == True -> wir sind bereits fertig mit der Suche und können das Ergebis zurückgeben\n",
    "     - situation_bereits_vorhanden() == True -> die Situation war bereits vorhanden: breche die Suche dieses Zweigs ab, da wir sonst in eine Endlosschleife kommen\n",
    "     - erfolg_noch_möglich() == False -> die Ziege oder der Kohl wurden gefressen. Breche die Suche ab, da das Vorhaben in diesem Ast des Suchbaums gescheitert ist.\n",
    " - daraufhin wissen wir, dass die aktuelle Situation valide ist und möglicherweise zum Endergebnis führen kann. Speichere diese Situation also ab, um einer Endlosschleife mit dieser Situation entgegenzuwirken.\n",
    " - dann wird die Fahrtrichtung festgestellt: fährt der Landwirt vom Start- zum Zielufer oder zurück?\n",
    " - mit diesen Informationen findet der rekursive Abstieg statt: probiere nacheinander die Überfahrt mit allen Begleiter des Ufers des Landwirts durch (auch den \"leeren\" Begleiter). Schaue dann rekursiv was geschieht, wenn mit diesen dann die Rücküberfahrt und die Rückrück- und die Rückrückrücküberfahrt usw. gemacht wird.\n",
    "\n",
    "Beachte: wenn du die folgende Fehlermeldung bekommst: \"maximum recursion depth exceeded\" (\"maximale Rekursionstiefe überschritten\"), hast du wahrscheinlich eine Endlosschleife in der Rekursion. Dann ist möglicherweise deine Abbruchbedingung oder die Implementierung der Funktionen \"speichere_situation()\" oder \"situation_bereits_vorhanden()\" falsch."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Hier kannst du zum Entwickeln die Textausgabe von hilfreichen Informationen einschalten.\n",
    "# Jedoch kann das recht viel Text sein, daher kannst du mit der Variable \"textausgabe\"\n",
    "# die Funktion immer ein- und ausschalten.\n",
    "textausgabe = False\n",
    "def debug_print(text):\n",
    "    if textausgabe:\n",
    "        print(text)\n",
    "\n",
    "# so tief sollte der Abstieg in dieser Aufgabe niemals sein!\n",
    "import sys\n",
    "print(\"Die maximale Rekursionstiefe dieser Python Installation ist: \" + str(sys.getrecursionlimit()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# In dieser Funktion findet die rekursive Suche im Suchbaum nach der Brute-Force-Methode statt.\n",
    "def abstieg_im_suchbaum(aktueller_zustand_start_ufer, aktueller_zustand_ziel_ufer, rekursionstiefe):\n",
    "    # ------------------------\n",
    "    # Anfang der Debug-Ausgabe\n",
    "    # ------------------------\n",
    "    einrückung = \"\"\n",
    "    for i in range(rekursionstiefe):\n",
    "        einrückung += \"  \"\n",
    "    debug_print(einrückung + \"Aktuell am Startufer: \" + str(aktueller_zustand_start_ufer))\n",
    "    debug_print(einrückung + \"Aktuell am Zielufer:  \" + str(aktueller_zustand_ziel_ufer))\n",
    "    if erfolg(aktueller_zustand_ziel_ufer):\n",
    "        debug_print(einrückung + \"Es wurde eine Lösung gefunden!\\n\")\n",
    "    if situation_bereits_vorhanden(aktueller_zustand_start_ufer, aktueller_zustand_ziel_ufer):\n",
    "        debug_print(einrückung + \"Die aktuelle Situation war bereits vorhanden!\\n\")\n",
    "    if not erfolg_noch_möglich(aktueller_zustand_start_ufer, aktueller_zustand_ziel_ufer):\n",
    "        debug_print(einrückung + \"Die aktuelle Situation lässt das Vorhaben scheitern!\\n\")\n",
    "    debug_print(\"\")\n",
    "    # ------------------------\n",
    "    #  Ende der Debug-Ausgabe\n",
    "    # ------------------------\n",
    "    \n",
    "    # die Suche ist erfolgreich, die Rekursion kann beendet werden\n",
    "    if erfolg(aktueller_zustand_ziel_ufer):\n",
    "        return True, [[aktueller_zustand_start_ufer, aktueller_zustand_ziel_ufer]]\n",
    "\n",
    "    # diese Situation war bereits vorhanden, daher kann dieser Teilbaum verlassen werden\n",
    "    if situation_bereits_vorhanden(aktueller_zustand_start_ufer, aktueller_zustand_ziel_ufer):\n",
    "        return False, []\n",
    "\n",
    "    # es ist eine Situation aufgetreten, in der die Ziege oder der Kohl gefressen wurde\n",
    "    # dieser Teilbaum muss nicht weiter untersucht werden\n",
    "    if not erfolg_noch_möglich(aktueller_zustand_start_ufer, aktueller_zustand_ziel_ufer):\n",
    "        return False, []\n",
    "    \n",
    "    # die aktuelle Situation ist noch nicht aufgetreten und ist valide, speichere\n",
    "    # diese daher ab\n",
    "    speichere_situation(aktueller_zustand_start_ufer, aktueller_zustand_ziel_ufer)\n",
    "\n",
    "    # zunächst muss die Fahrtrichtung festgestellt werden\n",
    "    if landwirt in ...:\n",
    "        ablegen_von_ufer = aktueller_zustand_start_ufer\n",
    "        ankommen_an_ufer = aktueller_zustand_ziel_ufer\n",
    "    else:\n",
    "        ablegen_von_ufer = aktueller_zustand_ziel_ufer\n",
    "        ankommen_an_ufer = aktueller_zustand_start_ufer\n",
    "    \n",
    "    # der Landwirt fährt entweder mit einem Begleiter\n",
    "    # oder auch ohne einen Begleiter (also \"leer\", \"None\") zum anderen Ufer\n",
    "    ablegen_von_ufer_plus_ohne_begleiter = ablegen_von_ufer + [None]\n",
    "    \n",
    "    # iteriere über alle Elemente des Ufers, von dem abgelegt wird\n",
    "    # für alle diese muss der jeweilige Teilbaum untersucht werden\n",
    "    for lebewesen in ablegen_von_ufer_plus_ohne_begleiter:\n",
    "        # der Landwirt fährt mit allen anderen, aber nicht mit sich selbst nochmal\n",
    "        if lebewesen != ...:\n",
    "            # mann muss von den Listen Kopien anfertigen, so dass Änderungen\n",
    "            # der folgenden Aufrufe nicht direkt überschrieben werden\n",
    "            ablegen_von_ufer_kopie = ablegen_von_ufer.copy()\n",
    "            ankommen_an_ufer_kopie = ankommen_an_ufer.copy()\n",
    "            \n",
    "            # dann findet die Überfahrt statt\n",
    "            überfahrt(...)\n",
    "            \n",
    "            # die Ufer müssen wieder zurück getauscht werden, wenn sie oben getauscht wurden.\n",
    "            # Die Reihenfolge der Ufer im rekursiven Aufruf muss gleich bleiben, egal wie die\n",
    "            # Fahrtrichtung des Landwirts ist. Schau dir dazu die Funktionsdefinition noch einmal an:\n",
    "            # abstieg_im_suchbaum(aktueller_zustand_start_ufer, aktueller_zustand_ziel_ufer, rekursionstiefe)\n",
    "            # Dabei ist start_ufer immer das erste Argument und ziel_ufer das zweite. Wenn wir oben das\n",
    "            # \"ablegen\" und \"ankommen\" Ufer herumgekehrt haben (weil der Landwirt zurück fährt), müssen\n",
    "            # wir die beiden wieder zurück tauschen, bevor wir die Funktion \"abstieg_im_suchbaum\" erneut aufrufen.\n",
    "            if landwirt not in aktueller_zustand_start_ufer:\n",
    "                ablegen_von_ufer_kopie, ankommen_an_ufer_kopie = ankommen_an_ufer_kopie, ablegen_von_ufer_kopie\n",
    "            \n",
    "            # nun findet der rekursive Abstieg statt\n",
    "            ergebnis, überfahrten_liste = ...\n",
    "            \n",
    "            # wenn eine Lösung für das Problem gefunden wurde, hänge den Zustand dieses Rekursionsebene an,\n",
    "            # so dass die Lösung am Ende ausgegeben werden kann und kehre mit dem Ergebnis zur Ebene darüber\n",
    "            # zurück\n",
    "            if ergebnis:\n",
    "                return True, überfahrten_liste + [[aktueller_zustand_start_ufer, aktueller_zustand_ziel_ufer]]\n",
    "    \n",
    "    # wenn kein Ergebnis in diesem Teilbaum gefunden wurde, gebe dies zurück\n",
    "    return False, []\n",
    "\n",
    "# schalte die Textausgabe aus - du kannst sie zum Entwickeln einschalten\n",
    "textausgabe = False\n",
    "\n",
    "# damit bei mehrmaligem Starten dieser Zelle die Ergebnisse gleich bleiben,\n",
    "# wird die Liste der Situationen geleert\n",
    "situationen.clear()\n",
    "\n",
    "# führe das Verfahren durch und gebe das Ergebnis aus\n",
    "ergebnis, überfahrten_liste = abstieg_im_suchbaum(start_ufer.copy(), ziel_ufer.copy(), 0)\n",
    "print(\"Anzahl Überfahrten\", len(überfahrten_liste) - 1, \"\\n\\n\")\n",
    "print(*überfahrten_liste[::-1], sep = \"\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Liste, die ausgegeben wurde, beschreibt den Zustand der beiden Ufer nach jeder einzelnen Überfahrt des Landwirts. Wie du siehst, wurde eine Lösung gefunden, bei der der Landwirt insgesamt 7 Überfahrten gebraucht hat."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Zusatzaufgabe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Gibt es mehr als eine mögliche Lösung für das Vorhaben des Landwirts, ohne dass eine bereits aufgetretene Situation erneut auftritt? Das lässt sich folgendermaßen herausfinden: wenn man jetzt von vorneherein eine Situation, die bei der oben gefundenen Lösung auftritt in die \"situationen\" Liste einhängt, so wird diese vom Verfahren ausgeschlossen. Die rekursive Suche findet damit eine alternative Lösung, sofern eine existiert.\n",
    "\n",
    "Wie viele mögliche Lösungen gibt es? Es gibt insgesamt ... mögliche Lösungen, bei denen keine Situation mehrfach auftritt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# schalte die Textausgabe aus - du kannst sie zum Entwickeln einschalten\n",
    "textausgabe = False\n",
    "\n",
    "# damit bei mehrmaligem Starten dieser Zelle die Ergebnisse gleich bleiben,\n",
    "# wird die Liste der Situationen geleert\n",
    "situationen.clear()\n",
    "\n",
    "...\n",
    "\n",
    "# führe das Verfahren durch und gebe das Ergebnis aus\n",
    "ergebnis, überfahrten_liste = abstieg_im_suchbaum(start_ufer.copy(), ziel_ufer.copy(), 0)\n",
    "print(\"Anzahl Überfahrten\", len(überfahrten_liste) - 1, \"\\n\\n\")\n",
    "print(*überfahrten_liste[::-1], sep = \"\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Wenn den Wolf die Lust am Coden packt, schreibt er ein Skript, das Codes knackt\n",
    "\n",
    "Im Folgenden kannst du noch dich noch weiter mit der Thema auseinandersetzen. Sieh es als eine Spielwiese :-)\n",
    "\n",
    "Bekannt ist die Brute-Force-Methode auch dafür, zum Knacken von Passwörtern eingesetzt zu werden. Dazu werden möglichst schnell alle Kombinationsmöglichkeiten von Buchstaben und Zeichen durchprobiert, bis die richtige erraten wurde. Das kann man genau wie das Problem hier als eine Suche in einem Suchbaum auffassen.\n",
    "\n",
    "Jedoch steigt die Anzahl auszuprobierender Kombinationen exponentiell mit der Länge eines Passworts, daher sind lange Passwörter auch sicherer als kurze und komplizierte. (siehe auch https://www.sueddeutsche.de/digital/it-sicherheit-das-sind-die-fuenf-groessten-passwort-mythen-1.3489400)\n",
    "\n",
    "Das kannst du dir auch an unserem Beispiel anschauen: Der Landwirt muss nun zusätzlch zur Ziege, dem Wolf und dem Kohl weitere Elemente über den Fluss bringen. Dazu könnte er einfach die Ziege vom Wolf und dem Kohl trennen und dann alle anderen Elemente übersetzen, woraufhin er mit dem Verfahren von oben weiter macht. Dazu wären nicht wesentlich mehr Schritte nötig, als beim Standardproblem.\n",
    "\n",
    "Jedoch hat die Brute-Force-Methode diese Einsicht nicht und probiert mit steigender Anzahl Elementen im Mittel immer mehr Kombinationsmöglichkeiten durch.\n",
    "\n",
    "Eine Lösung mit den wenigsten Überfahrten zu finden wäre nun ein Optimierungsproblem - aber das ist eine andere Geschichte und wird dir vielleicht in einer anderen Aufgabe noch einmal begegnen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%%time\n",
    "# mit dem time-Befehl wird die Zeit gemessen,\n",
    "# die diese Jupyter-Zelle zur Ausführung benötigt\n",
    "\n",
    "# schalte die Textausgabe aus - du kannst sie zum Entwickeln einschalten\n",
    "textausgabe = False\n",
    "\n",
    "# setze die beiden Ufer zurück, so dass das Ergebnis nicht von\n",
    "# vorherigen Ausführungen beeinflusst wird\n",
    "start_ufer = [landwirt, ziege, wolf, kohl]\n",
    "ziel_ufer = []\n",
    "\n",
    "# füge weitere Begleiter hinzu, die der Landwirt über den Fluss bringen muss\n",
    "# du kannst diese Zahl ändern, um zu sehen, wie das Verfahren reagiert\n",
    "# Aber Vorsicht! Bei höheren Werten kann das länger dauern, bis die Suche im Baum abgeschlossen ist.\n",
    "# Da kann sich sogar der Browsertab \"aufhängen\".\n",
    "# Speichere daher deine Arbeit, bevor du den Wert änderst!\n",
    "anzahl_weiterer_begleiter = 5\n",
    "start_ufer += [\"Element_\" + str(i) for i in range(anzahl_weiterer_begleiter)]\n",
    "\n",
    "# gebe die Begleiter aus\n",
    "print(start_ufer, \"\\n\\n\")\n",
    "\n",
    "# damit bei mehrmaligem Starten dieser Zelle die Ergebnisse gleich bleiben,\n",
    "# wird die Liste der Situationen geleert\n",
    "situationen.clear()\n",
    "\n",
    "# führe das Verfahren erneut durch und gebe das Ergebnis aus\n",
    "ergebnis, überfahrten_liste = abstieg_im_suchbaum(start_ufer.copy(), ziel_ufer.copy(), 0)\n",
    "print(\"Anzahl Überfahrten\", len(überfahrten_liste) - 1, \"\\n\\n\")\n",
    "print(*überfahrten_liste[::-1], sep = \"\\n\")\n",
    "print(\"\\n\\n\")"
   ]
  },
  {
   "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 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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}