seminar10.ipynb

    "Wir fangen mit dem Erzeugen der Geburtstagsliste an. Schreiben Sie zunächst den Kopf der Funktion. Wir verwenden n=23 als Parameter, so kann die Funktion ausgeführt werden, ohne dass ein Wert für die Länge der Liste festgelegt werden muss, aber wir haben in der Zukunft die Möglichkeit Listen unterschiedlicher Länge zu erzeugen. Ein so gestellter Parameter sagt: \"Setze für n 23 ein, ausser der Funktionsaufruf spezifiziert etwas anderes\".     \n",
    "  </div>       \n",
    "</details>  \n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">3. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Wir brauchen eine leere Liste, in der wir die zufällig erstellten Geburtstage speichern können. Erstellen Sie diese. \n",
    "  </div>       \n",
    "</details>  \n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">4. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Um uns das Erzeugen von Geburtstagen einfacher zu machen, speichern wir Geburtstage nicht im TT-MM Format, sondern als eine Zahl zwischen 1 und 365 (oder 366, wenn man Schaltjahre in Betracht ziehen möchte). Da wir nur eine zufällige Zahl erzeugen wollen, können wir sehr einfach die `randint`Funktion verwenden. Die Syntax für `randint` ist: `randint(1,365)`. Wobei in den Klammern zuerst die kleinste mögliche Zahl, dann ein Komma und dann die größtmögliche Zahl steht. Vergessen Sie nicht den so erzeugten Wert in einer Variablen zu speichern. \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "Es reicht natürlich nicht, einen zufälligen Geburtstag zu erzeugen, wir brauchen eine Liste von 23 zufälligen Geburtstagen. Wir können eine `for`-Schleife verwenden um `randint` entsprechend oft aufzurufen und den erzeugten Wert an die Liste anzuhängen.\n",
    "    </div>      \n",
    "</details>\n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">6. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "Vergessen Sie nicht, die Liste zurückzugeben. Rufen Sie die Funktion mehrfach auf und schauen Sie sich die Rückgabe an. Wird immer die korrekte Anzahl an Werten zurückgegeben? Liegen alle Werte im erwarteten Bereich?     \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "Nun haben Sie eine Liste mit zufälligen Geburtstagen. Wie können Sie weiter vorgehen?\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">7. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Überlegen Sie, wie Sie prüfen können, ob zwei Werte der Liste gleich sind. Sie dürfen Code, den Sie bereits geschrieben haben gerne wiederverwenden.\n",
    "    \n",
    "   </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">8. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Verwenden Sie die Funktion `has_dublicates`, die Sie bereits geschrieben haben um zu prüfen, ob Sie zwei gleiche Geburtstage haben. \n",
    "    \n",
    "   </div>       \n",
    "</details>\n",
    "\n",
    "Da ein einzelner Test nichts über die Wahrscheinlichkeit aussagen kann, ob ein Phänomen auftritt, schreiben wir nun eine Funktion, die diesen Test mehrfach durchführt und das Ergebnis ausgibt.\n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">9. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Schreiben Sie zunächst den Kopf der Funktion, überlegen Sie, ob Sie Werte zurückgeben lassen wollen oder lieber mit `print`-Statements arbeiten möchten. Beides ist möglich. Im Beispielcode wird mit `print`-Statements gearbeitet. Dieser Funktion müssen Sie übergeben, wie oft Sie den Test durchführen wollen.    \n",
    "   </div>       \n",
    "</details>\n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">10. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "Da wir am Ende wissen möchten wie viele der Tests gleiche Geburtstage hatten, müssen wir einen Zähler initialisieren, der erhöht wird, wann immer der Test auf Duplikate positiv ist.     \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">11. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "     \n",
    "Um den Test wiederholt mit zufälligen Werten durchzuführen, benötigen wir eine `for`-Schleife, die so oft läuft, wie wir im Kopf der Funktion angegeben haben. In der Schleife müssen wir die Geburtstagsliste erzeugen, auf Duplikate testen und wenn der Test positiv ausfällt den Zähler um 1 erhöhen. \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">11. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "Sie könnten die Geburtstagsliste in einer Variablen erstellen, diese Variable an `has_dublicates` übergeben, den Wert von `has_dublicates` in einer weiteren Variablen speichern und diese dann an eine `if`-Bedingung übergeben und dann die Zählererhöhung schreiben. Alternativ kann man die Funktionsaufrufe schachteln. Wir müssen die Liste nicht speichern, stattdessen können wir in der `if`-Bedingung auf has_dublicates() testen. has_dublicase wiederum kann birthdays() aufrufen. \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">12. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "Nach dem die Schleife erfolgreich durchlaufen wurde, haben Sie die Zahl an erfolgreichen Versuchen. Diese müssen wir jetzt noch ausgeben. Schreiben Sie ein `print`-Statement, das sagt, wie viele Versuche sie durchgeführt haben, und wie viele davon mindestens einen doppelten Geburtstag hatte. \n",
    "Im Beispielcode wird auch noch berechnet und ausgedruckt, welcher Anteil an Tests dies ist in Prozent. Dafür können Sie die Anzahl an Versuchen mit doppeltem Geburtstag durch die totale Anzahl an versuchen teilen und das Ergebnis mit 100 multiplizieren. \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "Denken Sie daran Ihre Funktion zu testen. Was stellen Sie fest, wenn Sie die Wahrscheinlichkeitsfunktion mit n=10.000 mehrfach hintereinander aufrufen?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n",
    "# Implementieren Sie hier Ihr Programm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "<a data-flickr-embed=\"true\"  href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
    "\n",
    "(Quelle: Jason Eppink, Flickr)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n",
    "def birthdays (n=23):\n",
    "    bday_list=[]\n",
    "    for i in range (n):\n",
    "        birthday= randint(1, 365)\n",
    "        bday_list.append(birthday)\n",
    "    return bday_list\n",
    "\n",
    "\n",
    "def likelyhood(n):\n",
    "    count=0\n",
    "    for i in range (n):\n",
    "        if has_dublicates(birthdays()):\n",
    "            count= count+1\n",
    "    percentage= (count/n)*100\n",
    "    print (\"In %d Versuchen gab es %d Versuche in denen mindestens 2 Studierende am selben Tag Geburtstag haben.\"\n",
    "           %(n,count))\n",
    "    print (\"Das sind %d Prozent der Fälle\" %percentage)\n",
    "    \n",
    "likelyhood(10000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aufgabe 9\n",
    "Schreiben Sie eine Funktion, die die Datei \"top10000de.txt\" oder \"words.txt\" einliest (siehe [Abschnitt 9.1](seminar09.ipynb#9.1-Wortlisten-einlesen)) und daraus eine Liste erzeugt mit den Wörtern als Elementen erzeugt. Implementieren Sie zwei Versionen dieser Funktion: eine, die die Methode `append` verwendet und eine, die den Operator `+` mittels `t = t + [wort]` verwendet. Welche der beiden Versionen hat eine größere Laufzeit? Warum?\n",
    "\n",
    "Eine Lösung für diese Aufgabe finden Sie hier: http://thinkpython2.com/code/wordlist.py\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">1. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Wenn wir die Laufzeit der beiden Methoden unterscheiden wollen, können wir ein Gerüst schreiben, das die Wortliste einliest und dann so verarbeitet, dass die Worte an die Liste angehängt werden können. Die Zeile in der jeweils das Wort an die Liste angehängt wird, unterscheidet sich dann in beiden Funktionen.\n",
    "      \n",
    "  </div>       \n",
    "</details> \n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">2. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Als erstes müssen wir eine leere Liste erzeugen und das Dokument mit der Wortliste öffnen. Wenn Sie sich nicht mehr daran erinnern können, wie Wortlisten geöffnet werden, schauen Sie in [Notebook 9](notebook_seminar09.ipynb) nach.\n",
    "\n",
    "  </div>       \n",
    "</details> \n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">3. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "In Notebook 9 haben Sie auch gesehen, wie Sie das Dokument Wort für Wort durchlaufen können. Schreiben Sie diese Schleife.\n",
    "\n",
    "  </div>       \n",
    "</details> \n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">4. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "An dieser Stelle müssen Sie das Wort zu der Liste hinzufügen, hier unterscheiden sich die beiden Funktionen. Überlegen Sie was anders sein könnte.\n",
    "      \n",
    "  </div>       \n",
    "</details> \n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">4.5 Hinweis - Append</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Wenn Sie ein Element mit Hilfe von `append()` an die Liste anhängen wollen lautet die gesamte Zeile `t.append(word)` **nicht** `t = t.append(word)`.\n",
    "      \n",
    "  </div>       \n",
    "</details> \n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">4.5 Hinweis - Add</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Im Gegensatz dazu muss die gesamte Zeile für das Anhängen mit dem `+`-Zeichen `t= t+[word]`lauten, wenn Sie `t+[word]` nicht wieder `t` zuweisen, wird die Liste nicht länger\n",
    "      \n",
    "  </div>       \n",
    "</details> \n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis </summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "Abschließend müssen Sie die vollständige Liste zurück zu geben. Verwenden Sie dafür ein `return`-Statement\n",
    "\n",
    "  </div>       \n",
    "</details> \n",
    "\n",
    "Nun können Sie mit Bachgefühl bereits abschätzen welche Funktion schneller ist und welche langsamer. Im folgenden schreiben wir eine Funktion, die die tatsächliche Laufzeit zurückgibt um die Situation genau abzuschätzen.\n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">6. Hinweis </summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "In der Musterlösung wird mithilfe des `time`-Moduls ermittelt, wie lange die Funktionen jeweils zum Durchlaufen benötigen.\n",
    "      \n",
    "  </div>       \n",
    "</details> \n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">7. Hinweis </summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    " Zunächst wird der Zeitpunkt festgehalten, bevor die Funktion gestartet wird, dies geschieht indem die aktuelle Zeit in Sekunden und Millisekunden seit dem Referenzzeitpunkt mit `time.time()` abgefragt und in einer Variablen gespeichert wird.\n",
    "      \n",
    "  </div>       \n",
    "</details> \n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">8. Hinweis </summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "Dann wird einfach der Funktionsaufruf ausgeführt.\n",
    "      \n",
    "  </div>       \n",
    "</details> \n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">9. Hinweis </summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "Sobald der Funktionsaufruf beendet ist, wird erneut die aktuelle Zeit abgefragt. Zieht man davon die Zeit ab, die wir zuvor gespeichert haben, bleibt die Anzahl an Sekunden übrig, die zwischen Referenzzeitpunkt und Ende des Funktionsaufrufs vergangen sind. Vergessen Sie nicht, das Ergebnis ausgeben zu lassen!\n",
    "      \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "Im Folgenden wird einmal kurz das Ergebnis der Aufgabe besprochen:\n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-success\">Lösung </summary>\n",
    "  <div class=\"alert alert-success\" role=\"alert\">\n",
    "      \n",
    "Die Additionsfunktion hat eine größere Laufzeit. In append wird die Liste aufgerufen, bis ans Ende gelaufen und dann einmal das neue Wort geschrieben, in der Additionsfunktion hingegen, muss die liste jedes mal komplett neu geschrieben werden.\n",
    "      \n",
    "  </div>       \n",
    "</details>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier die beiden Varianten Ihrer Funktion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "<a data-flickr-embed=\"true\"  href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
    "\n",
    "(Quelle: Jason Eppink, Flickr)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "def appending():\n",
    "    t = []\n",
    "    fin = open('words.txt')\n",
    "    for line in fin:\n",
    "        word = line.strip()\n",
    "        t.append(word)\n",
    "    return t\n",
    "\n",
    "start_time= time.time()\n",
    "word_list= appending()\n",
    "elapsed_time = time.time() - start_time\n",
    "\n",
    "print (elapsed_time)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def adding():\n",
    "    t = []\n",
    "    fin = open('words.txt')\n",
    "    for line in fin:\n",
    "        word = line.strip()\n",
    "        t=t+[word]\n",
    "    return t\n",
    "\n",
    "\n",
    "start_time= time.time()\n",
    "adding()\n",
    "elapsed_time = time.time() - start_time\n",
    "\n",
    "print (elapsed_time)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aufgabe 10\n",
    "\n",
    "Um zu überprüfen, ob ein Wort in einer Wortliste ist, können wir den Operator `in` verwenden, aber das wäre recht langsam, denn der Operator muss dazu die Liste linear durchlaufen.\n",
    "\n",
    "Wenn wir mit einer sortierten Liste arbeiten, können wir den Vorgang beschleunigen, indem wir *binäre Suche* (auch bekannt als *bisection search*) verwenden. Das entspricht dem Verfahren, welches wir verwenden, wenn wir ein Wort in einem Wörterbuch nachschlagen: wir beginnen in der Mitte und schauen, ob das gesuchte Wort vor dem Wort in der Mitte der Liste stehen müsste. Falls dem so ist, durchsuchen wir die erste Hälfte der Liste auf die gleiche Art, ansonsten durchsuchen wir die zweite Hälfte.\n",
    "\n",
    "In jedem Fall halbieren wir damit den Suchraum. Im Fall unserer Wortliste mit 10000 Wörtern benötigen wir höchstens 13 Schritte, um das gesuchte Wort zu finden oder festzustellen, dass die Liste das Wort nicht enthält. \n",
    "\n",
    "Schreiben Sie eine Funktion `binary_search` die eine sortierte Liste sowie ein Wort als Argumente erwartet und `True` zurückgibt, falls das Wort in der Liste enthalten ist, ansonsten `False`.\n",
    "\n",
    "Alternativ können Sie auch die [Dokumentation für das Modul `bisect`](https://docs.python.org/3.5/library/bisect) lesen und dieses verwenden. Eine Lösung finden Sie hier: http://thinkpython2.com/code/inlist.py\n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-info\">Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Damit die binäre Suche funktioniert, muss die Liste sortiert sein. Das können Sie, wie wir es bereits getan haben, mit der Funktion `sort` erreichen. Mit `help(list.sort)` kriegen Sie mehr Informationen.    \n",
    "  </div>       \n",
    "</details>  \n",
    "\n",
    ".   \n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">1. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Wir verwenden Rekursion um die Suche durchzuführen\n",
    "      \n",
    "  </div>       \n",
    "</details> \n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">2. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Wenn wir Rekursion verwenden müssen wir uns zuerst die beiden Abbruchbedingungen überlegen. Eine Abbruchbedingung für das finden des Wortes und eine Abbruchbedingung, für wenn dass Wort nicht in der Liste ist.\n",
    "      \n",
    "  </div>       \n",
    "</details> \n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">3. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Der erste Fall ist einfach: das Wort, das wir suchen, stimmt mit dem Wort überein, das wir uns gerade anschauen. Dies benötigt eine Vergleich zwischen dem gesuchten Wort und dem Wort das wir uns anschauen. Gibt dieser Vergleich 'TRUE' aus, können wir die Suche abbrechen und 'TRUE' zurückgeben. Schreiben Sie einen Platzhaltervergleich, der dies prüft. Dazu können Sie das gesuchte Wort mit einer zufälligen Zeichenkette vergleichen. Die Zeichenkette werden wir später ersetzen.\n",
    "Die andere Abbruchbedingung ist das nicht finden des Wortes in der Liste. In der Rekursion halbieren wir die Wortliste in jedem Schritt bis die Liste irgendwann 0 Elemente lang ist. Erinnern Sie sich daran, wie Sie die Länge der Liste überprüfen? Wenn dieser Test 0 zurückgibt, müssen Sie 'FALSE' zurückgeben.\n",
    "      \n",
    "  </div>       \n",
    "</details> \n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">4. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Da wir in jedem Schritt die Liste halbieren und anschließend die Hälfte der Liste ignorieren, müssen wir entscheiden welche Hälfte der Liste wir ignorieren und mit welcher Hälfte wir weiterarbeiten. Dazu schauen wir uns das Trennelement in der Mitte der Liste an und entscheiden ob das gesuchte Wort größer oder kleiner ist als das Trennelement ist. Dazu berechnen wir den Index in der Mitte der Liste. \n",
    "      \n",
    "  </div>       \n",
    "</details> \n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "Um den Index zu berechnen, ermitteln wir die Länge der Liste mit 'len()' und verwenden dann Ganzzahldivision um den Index herauszufinden.\n",
    "      \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">6. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "Mit Hilfe von diesem Index können wir nun das Element ansteuern. Nun prüfen wir zuerst, ob das Wort an dieser Stelle gleich dem gesuchten Wort ist. Ersetzen Sie die Zeichenkette aus dem Platzhaltervergleich mit einem Zugriff auf die Liste an diesem Index. \n",
    "      \n",
    "  </div>       \n",
    "</details> \n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">7. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Gibt dieser Vergleich nicht 'TRUE' zurück, prüfen wir als nächstes, ob das Element an Indexstelle i größer ist, als das gesuchte Wort. Ist das Wort an dieser Stelle größer als das gesuchte Wort, wird in der vorderen Listenhälfte gesucht. Andernfalls wird in der hinteren Listenhälfte gesucht. Schreiben Sie den Vergleich und Platzhalter 'return'-Anweisungen. Testen Sie ihre Funktion und schauen Sie, ob alle 'return'-Anweisungen erreicht werden können. \n",
    "      \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">8. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "An dieser Stelle fügen wir die Rekursion ein. Bisher wird nur geprüft ob das Wort genau in der Mitte steht oder ob es größer oder kleiner ist. Mithilfe der Rekursion rufen wir an der Stelle, an der wir entscheiden ob das Wort in der vorderen oder hinteren Listenhälfte steht die Funktion erneut auf, diesmal aber mit der geteilten Liste. \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">9. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "\n",
    "In den 'return'-Anweisugen rufen wir die binäre Suche Funktion auf, dabei übergeben wir immer noch das gesuchte Wort, aber statt der ursprünglichen List übergeben wir nur die halbe Liste. Das erreichen wir, indem wir die ursprüngliche Liste zusamen mit einem Segementoperator übergeben, in dem wir entweder auf die Liste bis zum *i*-ten Element zugreifen, oder aber erst auf die Liste ab dem *i+1*-ten Element zugreifen.\n",
    "      \n",
    "  </div>       \n",
    "</details>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(t, w):\n",
    "    # Implementieren Sie hier die Funktion\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "<a data-flickr-embed=\"true\"  href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
    "\n",
    "(Quelle: Jason Eppink, Flickr)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(word_list, word):\n",
    "    '''Vorbedingung: Sortierte Liste'''\n",
    "    \n",
    "    if len(word_list) == 0:\n",
    "        return False \n",
    "\n",
    "    i = len(word_list) // 2\n",
    "    \n",
    "    if word_list[i] == word:\n",
    "        return True\n",
    "\n",
    "    if word_list[i] > word:\n",
    "        # search the first half\n",
    "        return binary_search(word_list[:i], word)\n",
    "    else:\n",
    "        # search the second half\n",
    "        return binary_search(word_list[i+1:], word)\n",
    "\n",
    "t=sorted([1,3,6,2,7,19,22])\n",
    "binary_search(t,24)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aufgabe 11\n",
    "Zwei Wörter sind ein \"umgekehrtes Paar\" (*reverse pair*), wenn jedes Wort rückwärts gelesen das jeweils andere ergibt (wie bei \"LAGER\" und \"REGAL\"). Schreiben Sie ein Programm, welches alle umgekehrten Paare in unserer Wortliste findet. (Ignorieren Sie dabei wieder Groß- und Kleinschreibung oder verwenden sie die englischsprachige Liste) Eine Lösung finden Sie hier: http://thinkpython2.com/code/reverse_pair.py\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-info\">Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "Wenn Sie die deutsche Wortliste verwenden, werden Sie einige doppelte Paare finden, was daran liegt, dass in top10000.txt Groß- und Kleinschreibung unterschieden wird. \n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    ".\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">1. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "An dieser Stelle werden eigentlich 2 Funktionen gesucht. Eine Funktion, die ein umgekehrtes Paar findet, und eine Funktion, die die gesamte Liste durchläuft und für jedes Wort prüft ob es Teil eines umgekehrten Paares ist und diese Antwort zurückgibt. Teilen wir also die Aufgabe und konzentrieren uns zunächst einmal darauf ein umgekehrtes Paar zu finden, wenn ein beliebiges Wort eingegeben wird.\n",
    "      \n",
    "  </div>       \n",
    "</details> \n",
    "\n",
    "Teil 1\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">2. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "Der Funktion müssen natürlich ein Wort und die komplette Wortliste übergeben werden, damit wir unser wort mit der Liste vergleichen können.\n",
    "      \n",
    "  </div>       \n",
    "</details> \n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">3. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "  \n",
    "Der einfachste Weg rauszufinden ob das Wort, das wir übergeben, Teil eines umgekehrten Paares ist, ist es das umgekehrte Wort dieses Wortes zu bilden und zu schauen, ob es in der Liste vorhanden ist. In Seminar 8 haben Sie gelernt, wie man ein Wort schrittweise rückwärts durchläuft, dies können Sie nutzen um das umgekehrte Wort zu bilden.\n",
    "    </div>       \n",
    "</details> \n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">4. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    " Nun können wir die binäre Suche von vorher wiederverwenden um zu überprüfen, ob das so gebildete Wort in der Liste ist. Diese Funktion gibt 'TRUE' zurück, wenn dies der Fall ist. Hier könnten wir das Wortpaar ausgeben. In dem Beispielcode gibt diese Funktion allerdings 'TRUE' oder 'FALSE' an die nächste Funktion, die wir schreiben zurück, die dann wiederum die Ausgabe händelt.\n",
    "    </div>       \n",
    "</details> \n",
    "\n",
    "Teil 2 \n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Um alle Worte in der Liste zu finden, die Teil eines umgekehrten Paases sind, müssen wir mit einer Schleife die Liste Wort für Wort durchlaufen.\n",
    "    </div>       \n",
    "</details> \n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">6. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "Wenn Sie die deutsche Liste verwenden, stellen Sie sicher, dass sie die Liste auf Kleinschreibung normalisieren, wie wir das bereits in anderen Aufgaben dieses Notebooks gemacht haben.\n",
    "    </div>       \n",
    "</details> \n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">7. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Rufen Sie innerhalb der Schleife die Funktion auf, die wir in Teil 1 geschrieben haben. Übergeben Sie jeweils das aktuelle Wort in der Schleife. Da die Funktion 'TRUE' oder 'FALSE' zurückgibt, können Sie sie verwenden um zu entscheiden ob das Wort als Teil eines umgekehrten Paares ausgegeben oder aber übersprungen werden soll. Wie können wir solche Entscheidungen treffen?\n",
    "    </div>       \n",
    "</details> \n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">8. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "Innerhalb der if-Bedingung müssen wir das gesamte umgekehrte Paar ausgeben. Sie dürfen die Umkehrung des Wortes analog zu Teil 1 treffen. Verwenden Sie für die Ausgabe eine 'print'-Anweisung.\n",
    "    </div>       \n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier Ihr Programm\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "<a data-flickr-embed=\"true\"  href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
    "\n",
    "(Quelle: Jason Eppink, Flickr)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverse_pair(word_list, word):\n",
    "    reverse = word[::-1]\n",
    "    return binary_search (word_list, reverse)\n",
    "\n",
    "\n",
    "def reverse_list(word_list):\n",
    "    for word in word_list:\n",
    "        word= word.lower()\n",
    "        if reverse_pair(word_list, word): \n",
    "            print (word, word[::-1])\n",
    "\n",
    "reverse_list(word_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aufgabe 12\n",
    "Zwei Wörter \"greifen ineinander\" (*interlock*), wenn sich durch abwechselndes Hinzufügen eines Buchstabens aus beiden Wörtern ein neues Wort ergibt. Beispielsweise greifen \"Mai\" und \"im\" ineinander und bilden das Wort \"Miami\". \n",
    "\n",
    "![Mai + im = Miami](https://amor.cms.hu-berlin.de/~jaeschkr/teaching/spp/miami.svg)\n",
    "\n",
    "1. Schreiben Sie ein Program, welches alle Wortpaare findet, die ineinandergreifen. \n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-info\">Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      Durchlaufen Sie nicht alle möglichen Wortpaare!\n",
    "  </div>       \n",
    "</details>\n",
    "\n",
    "2. Gibt es Wörter, die dreifach ineinandergreifen; das heißt, jeder dritte Buchstabe ergibt ein Wort, beginnend mit dem ersten, zweiten oder dritten Buchstaben? (*Leider ist unsere Wortliste mit 10000 Wörtern recht kurz ... als einziges einigermaßen sinnvolles Beispiel ergibt sich \"bekommt\", welches die \"Wörter\" \"Bot\", \"EM\", und \"km\" enthält.*)\n",
    "\n",
    "(Diese Aufgabe wurde durch ein Beispiel auf http://puzzlers.org/ inspiriert, eine Lösung finden Sie hier: http://thinkpython2.com/code/interlock.py)\n",
    "\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">1. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "Ähnlich wie in der vorherigen Aufgabe benötigen wir wieder 2 Funktionen um die Frage zu beantworten. Eine Funktion, die prüft ob ein gegebenes Wort aus n ineinander greifenden Wörtern besteht und eine zweite Funktion, die die ganze Liste Wort für Wort ausliest. Auch in diesem Fall schreiben wir zuerst den Test dafür ob ein einzelnes Wort aus anderen -- in der Wortliste vorkommenden -- Worten zusammengesetzt ist.\n",
    "    </div>       \n",
    "</details>\n",
    "\n",
    "Teil 1 \n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">2. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "Im Kopf der Funktion müssen wir das Wort, die Liste, in der wir die Teilworte finden wollen, und die Schrittweite, also die Anzahl an Teilworten aus denen das gegebene Wort zusammengesetzt sein soll, übergeben. Schreiben Sie den Kopf der Funktion.\n",
    "    </div>       \n",
    "</details>\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">3. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    " Analog zur vorherigen Aufgabe müssen wir wieder aus dem Original Wort die Worte bilden, die wir in der Wortliste suchen wollen. Überlegen Sie sich wie Sie dabei vorgehen können.\n",
    "    </div>       \n",
    "</details>\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">4. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "Um die Teilworte zu bilden nutzen wir den Segment-Operatoren. Wir können hier den ersten Buchstaben und die Schrittweite festlegen. Mit diesen Angaben werden dann nur die gewünschten Buchstaben genommen. Diese können Sie in einer Variable speichern. Versuchen Sie zunächst diesen Teil der Aufgabe zu lösen indem Sie die Teilworte jeweils ausgeben lassen und prüfen ob das gegebene Ergebnis mit dem erwarteten übereinstimmt. Testen Sie dies indem sie alle \"Teilworte\" (sinnvoll oder nicht) eines beliebigen Wortes sowohl für 2 als auch für 3 Teilworte erstellen. Behalten Sie diese Anweisungen, wir benötigen sie im nächsten Schritt.\n",
    "      \n",
    "    </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">5. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "Da wir die Aufgabe sowohl für 2 als auch für 3 Teilworte lösen wollen, ist es ratsam diese Erstellung so allgemein zu halten, dass sie mit jeder beliebigen Schrittweite funktionieren würde. Dies können wir mit einer Schleife erreichen. Schauen Sie sich die Segmentoperatoren an, die Sie geschrieben haben. Was fällt Ihnen auf? Wie könnte man das verallgemeinern?\n",
    "      \n",
    "    </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">6. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "     Wir verwenden eine 'for'-Schleife, in der eine Platzhalter-Variable hochgezählt wird, bis wir die Schrittweite also die Anzahl an Worten erreichen. Damit wird die korrekte Anzahl an Worten gefunden. Das erste Wort beginnt am Index 0, das Zweite am Index 1 und so weiter. Damit dann diese Hilfsvariable verwendet werden um den Startpunkt für jedes der Worte zu setzten. Die Schrittweite ist für alle Worte gleich und ist als Variable vorhanden. Diese kann daher übergeben werden. \n",
    "    </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">7. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      Für jedes Wort, das wir so erzeugen, müssen wir prüfen, ob das Wort in der übergebenen Liste enthalten ist. Wie haben wir dies bisher im Notebook erledigt?\n",
    "    </div>       \n",
    "</details>\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">8. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "Da alle erzeugten Wörter in der Wortliste vorhanden sein müssen und wir möglichst wenige Operationen durchführen wollen, testen wir in der in der Schleife direkt nach der Erstellung das Wort. Was passiert, wenn wir einen einfachen Wahrheitstest machen und das Ergebnis zurück geben? Was passiert, wenn das erste Wort zwar in der Wortliste ist, das zweite oder dritte aber nicht? Überlegen Sie, wie Sie sicherstellen können, dass nur dann 'TRUE' zurückgegeben wird, wenn alle Worte in der Liste sind.\n",
    "    </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">9. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "Wir geben nur dann 'TRUE' zurück, wenn die Schleife verlassen wird. Daher prüfen wir in der Schleife ob wir 'FALSE' zurück geben müssen. Wenn des Ergebnis von 'binary_search' 'TRUE' ist, wird in der Schleife nichts weiter mit dem Wort gemacht und die Schleife startet -- falls nötig -- mit dem nächsten Wort. Sobald eines der Wörter nicht in der Liste ist, wird 'FALSE' zurück gegeben. Mit 'if not' können Sie eine Anweisung schreiben, die sagt: \"Wenn das Ergebnis von 'binary_search' nicht 'TRUE' ist, dann tue:\"\n",
    "    </div>       \n",
    "</details>\n",
    "\n",
    "Teil 2:\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">10. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    " In dieser Funktion wollen wir alle Worte finden, die aus einer bestimten Anzahl an ineinander greifenden Worten bestehen. Als solches muss diese Funktion die Liste und die gewünschte Anzahl an ineinander greifenden Worten übergeben bekommen. Schreiben Sie den Kopf der Funktion.\n",
    "    </div>       \n",
    "</details>\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">11. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "Innerhalb der Funktion müssen wir die Liste Wort für Wort durchlaufen und prüfen ob das Wort ineinander greifende Worte innerhalb der Liste enthält.\n",
    "    </div>       \n",
    "</details>\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">12. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "Jedes Wort, das kürzer ist als die Anzahl an ineinander greifenden Worten, können wir komplett überspringen. Schreiben Sie das 'if'-Statement, das dies überprüft. Mit 'pass' können Sie den Rest eines Schleifendurchlaufs überspringen.   \n",
    "      \n",
    "      \n",
    "      \n",
    "wenn wir ein wort finden, wollen wir dieses ausgeben. Hier drucken wir dafür einen Header, der anzeigt, dass ein wort gefunden wurde und das wort ausgibt, bevor ähnlich wie in der prüffunktion die subworte aus dem originalwort erzuegt und einzel ausgedruckt werden. Dabei wird jedes wort in einer eigenen zeile ausgegeben, aber dafür kann die funktion ohne angepasst zu werden worte mit beliebig vielen unterworten finden.   \n",
    "    </div>       \n",
    "</details>\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">13. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "      \n",
    "Die erste Funktion gibt entweder 'TRUE' oder 'FALSE' zurück. Schreiben Sie ein 'if'-Statement analog zu dem in der Funktion zum finden von umgekehrten Paaren.\n",
    "    </div>       \n",
    "</details>\n",
    "\n",
    "<details>\n",
    "    <summary type=\"button\" class=\"btn btn-primary\">14. Hinweis</summary>\n",
    "  <div class=\"alert alert-info\" role=\"alert\">\n",
    "\n",
    "Innerhalb dieser 'if'-Bedingung wollen wir die ineinandergreifenden Worte ausgeben. Um die Funktion weiterhin für jede beliebige Menge an Teilworten nutzen zu können, können wir die Schleife aus der ersten Funktion wiederverwenden. Statt innerhalb der Schleife zu prüfen ob das Wort in der Liste ist, können wir das Wort mit einem 'print'-Statement ausgeben. Das bedeutet, dass jedes Wort und jedes Teilwort in einer eigenen Zeile gedruckt wird. Vergessen Sie nicht, dass vollständige Wort auszugeben. Es ist daher auch hilfreich eine Trennzeile auszudrucken in der gesagt wird, dass eine neues Wort folgt.\n",
    "      \n",
    "    </div>       \n",
    "</details>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier das Programm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "<a data-flickr-embed=\"true\"  href=\"https://www.flickr.com/photos/jasoneppink/4964471335\" title=\"Spoiler Alert\"><img src=\"https://farm5.staticflickr.com/4110/4964471335_1f86a923f3_n.jpg\" width=\"320\" height=\"213\" alt=\"Spoiler Alert\"></a><script async src=\"//embedr.flickr.com/assets/client-code.js\" charset=\"utf-8\"></script>\n",
    "\n",
    "(Quelle: Jason Eppink, Flickr)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def interwoven(word_list, word, n=3):\n",
    "    for i in range(n):\n",
    "        sub = word[i::n]\n",
    "        if not binary_search(word_list, sub):\n",
    "            return False \n",
    "    return True\n",
    "        \n",
    "def find_interwoven(word_list, n):\n",
    "    for word in word_list:\n",
    "        if len(word)<n:\n",
    "            pass\n",
    "        if interwoven(word_list, word, n):\n",
    "            print (\"New word found:\")\n",
    "            print (word)\n",
    "            for i in range (n):\n",
    "                print(word[i::n])    \n",
    "            \n",
    "find_interwoven(word_list, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Speichern](https://amor.cms.hu-berlin.de/~jaeschkr/teaching/spp/floppy.png) Speichern Sie dieses Notebook, so dass Ihre Änderungen nicht verlorengehen (nicht auf einem Pool-Rechner). \n",
    "Klicken Sie dazu oben links auf das Disketten-Icon und nutzen Sie beispielsweise einen USB-Stick, E-Mail, Google Drive, Dropbox oder Ihre [HU-Box](https://box.hu-berlin.de/).  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Smiley](https://upload.wikimedia.org/wikipedia/commons/thumb/7/79/Face-smile.svg/48px-Face-smile.svg.png)\n",
    "\n",
    "Herzlichen Glückwunsch! Sie haben das 10. Kapitel geschafft. Weiter geht es in [11: assoziative Felder](seminar11.ipynb)."
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}