seminar09.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Seminar Problemorientierte Programmierung\n",
    "\n",
    "## Exkurs: Was mir an Python gefällt\n",
    "\n",
    "In dieser Rubrik, die immer am Anfang eines Kapitels steht, möchte ich Ihnen zeigen, wofür ich Python nutze und warum ich es mag. Sie werden vielleicht noch nicht verstehen, was ich genau mache, aber Sie sehen damit schon einmal die Möglichkeiten von Python und können später darauf zurückgreifen. Da dies auch ein Exkurs ist, können Sie diese Rubrik gerne auch erst einmal überspringen.\n",
    "\n",
    "Text-Statistik ist ganz einfach machbar - mit dem Wissen aus diesem Kapitel können wir z.B. n-Gramme berechnen. Hier ein Beispiel, welches automatisch eine Webseite herunterlädt und die häufigsten 6-Gramme berechnet. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 9 Fallstudie: Wortspiele\n",
    "\n",
    "In diesem Abschnitt gibt es das zweite Fallbeispiel. In diesem werden Wort-Puzzles gelöst, in denen Wörter mit bestimmten Eigenschaften gesucht werden. Beispielsweise finden wir die längsten Palindrome und suchen nach Wörtern, deren Buchstaben in alphabetischer Reihenfolge erscheinen. Und wir lernen eine weitere Entwicklungsmethode kennen: Rückführung auf ein bereits gelöstes Problem.\n",
    "\n",
    "### 9.1 Wortlisten einlesen\n",
    "\n",
    "Die Übungen in diesem Abschnitt weichen vom [Original](http://greenteapress.com/thinkpython2/html/thinkpython2010.html) insofern ab, als dass Wortlisten mit deutschen Wörtern verwendet werden. Alle Übungen können jedoch auch mit englischen Wortlisten durchgeführt werden.\n",
    "\n",
    "Für die Übungen in diesem Abschnitt benötigen wir eine Liste deutscher Wörter. Es gibt sehr viele Wortlisten im Web, wir verwenden hier eine Liste des [Wortschatz-Projektes](http://wortschatz.uni-leipzig.de/) der Universität Leipzig. Laden Sie [diese Liste mit 10000 häufigen deutschen Wörtern](http://pcai056.informatik.uni-leipzig.de/downloads/etc/legacy/Papers/top10000de.txt) herunter und speichern Sie sie unter dem Dateinamen `top10000de.txt`.\n",
    "\n",
    "Die Datei ist eine reine Textdatei, daher können wir sie mit einem Texteditor anschauen, aber wir können sie auch leicht mit Python einlesen. Die eingebaute Funktion `open` erwartet einen Dateiname als Parameter und gibt uns ein **Dateiobjekt** (*file object*) zurück, mit dessen Hilfe wir die Datei lesen können:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fin = open('top10000de.txt', encoding=\"latin1\")\n",
    "# Hinweis: der Parameter encoding gibt an, in welcher Zeichenkodierung\n",
    "# die Datei verfasst ist. I.A. sollten heute Datein in Unicode verwendet\n",
    "# werden, bei diesen ist in Python3 diese Angabe nicht notwendig.\n",
    "# Leider ist die Datei vom Wortschatz-Projekt aber in Latin1-Kodierung,\n",
    "# so dass wir dies Python mitteilen müssen."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`fin` ist ein üblicher Name für ein Dateiobjekt zum lesenden Zugriff auf die Datei (`fin` steht für **f**ile **in**put). Das Dateiobjekt bietet uns mehrere Methoden zum Lesen der Datei, unter anderem die Methode `readline`, die Zeichen aus einer Datei einliest, bis ein Zeichen für den Zeilenumbruch erreicht wird, und das Ergebnis als Zeichenkette zurückgibt:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fin.readline()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das erste \"Wort\" in dieser Liste ist \"der\". Die Zeichenfolge \"\\n\" repräsentiert das Zeichen für den Zeilenumbruch, durch das die Wörter (zeilenweise) getrennt sind. \n",
    "\n",
    "Das Dateiobjekt merkt sich, an welcher Stelle innerhalb der Datei wir gerade sind. Wenn wir also `readline` nochmal aufrufen, erhalten wir die nächste Zeile zurück:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fin.readline()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das nächste Wort ist also \"die\". Wenn uns das Zeichen für den Zeilenumbruch stört, können wir es mit der Methode `strip` entfernen: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "line = fin.readline()\n",
    "word = line.strip()\n",
    "word"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir können das Dateiobjekt auch innerhalb einer `for`-Schleife verwenden. Das folgende Programm liest die Datei ein und gibt jedes Wort aus - eines pro Zeile:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fin = open('top10000de.txt', encoding=\"latin1\")\n",
    "for line in fin:\n",
    "    word = line.strip()\n",
    "    print(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9.2 Übung\n",
    "\n",
    "Die Lösungen für die Aufgaben hier gibt es im nächsten Abschnitt. Bitte versuchen Sie zunächst, jede Aufgabe selbständig zu lösen, bevor sie eine der Lösungen anschauen.\n",
    "\n",
    "#### Aufgabe 1\n",
    "\n",
    "Schreiben Sie ein Programm welches die Datei `top10000de.txt` einliest und nur die Wörter mit mehr als 20 Zeichen ausgibt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier Ihr Programm\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Am Ergebnis werden Sie merken, dass die Wortliste nicht ganz bereinigt ist und manche Zeilen Phrasen bestehend aus mehreren Wörtern enthalten.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Aufgabe 2\n",
    "\n",
    "![Ernest Vincent Wright](https://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Ernestvincentwright1939.jpg/371px-Ernestvincentwright1939.jpg)\n",
    "\n",
    "1939 hat [Ernest Vincent Wright](https://de.wikipedia.org/wiki/Ernest_Vincent_Wright) den englischen Roman *Gadsby* mit 50000 Wörtern veröffentlicht, von denen keines den Buchstaben \"e\" enthält. Da \"e\" der häufigste Buchstabe im Englischen ist, ist das eine beachtliche Leistung.\n",
    "\n",
    "Tatsächlich ist's knifflig, was im Hirn ohn' das Symbol zu tun. (Im Englischen ist's wohl einfacher - im Original steht hier: *In fact, it is difficult to construct a solitary thought without using that most common symbol. It is slow going at first, but with caution and hours of training you can gradually gain facility.\n",
    "\n",
    "All right, I’ll stop now.*)\n",
    "\n",
    "Schreiben Sie eine Funktion `has_no_e` die `True` zurückgibt, wenn das übergebene Wort den Buchstaben \"e\" nicht enthält. (Denken Sie auch an den Großbuchstaben \"E\".)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def has_no_e(word):\n",
    "    # Implementieren Sie hier die Funktion has_no_e\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Verändern Sie jetzt das Programm aus Aufgabe 1, so dass nur Wörter ausgegeben werden, die kein \"e\" enthalten und berechnen Sie den Anteil der Wörter in der Liste, die kein \"e\" enthalten."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier Ihr Programm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Aufgabe 3\n",
    "\n",
    "Schreiben Sie eine Funktion `avoids` die ein Wort sowie eine Zeichenkette mit verbotenen Buchstaben erwartet und `True` zurückgibt, wenn im Wort keiner der verbotenen Buchstaben auftaucht. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def avoids(word, forbidden):\n",
    "    # Implementieren Sie hier die Funktion\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Hinweis: mit der Methode `lower` können Sie eine Zeichenkette in Kleinbuchstaben umwandeln. `word.lower()` enthält also die gleichen Buchstaben wie `word`, nur halt als Kleinbuchstaben*\n",
    "\n",
    "Verändern Sie Ihr Programm von Aufgabe 2, so dass Sie zunächst den Nutzer bitten, die verbotenen Buchstaben einzugeben und dann drucken Sie die Anzahl der Wörter aus, die keine der Buchstaben enthalten."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier Ihr Programm\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Können Sie eine Kombination von fünf verbotenen Buchstaben finden, die die kleinste Anzahl an Wörtern ausschließt? (*Bestwert unter den 10000 Wörtern der Liste ist bisher 634.*)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Aufgabe 4\n",
    "\n",
    "Schreiben Sie eine Funktion `uses_only` die ein Wort und eine Zeichenkette mit Buchstaben als Argument erwartet und `True` zurückgibt, wenn das Wort nur Buchstaben aus der Liste enthält. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def uses_only(word, characters):\n",
    "    # Implementieren Sie hier die Funktion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Können Sie einen Satz bilden, der nur die Buchstaben `acefhln` enthält?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier Ihr Programm\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Aufgabe 5\n",
    "Schreiben Sie eine Funktion `uses_all` die ein Wort und eine Zeichenketten mit verlangten Buchstaben erwartet und `True` zurückgibt, wenn das Wort alle verlangten Buchstaben mindestens einmal enthält. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def uses_all(word, characters):\n",
    "    # Implementieren Sie hier die Funktion\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wie viele Wörter gibt es, in denen die Vokale `aeiou` alle vorkommen?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier Ihr Programm\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In der Ergebnisliste sollte das Wort `Argumentation` enthalten sein.\n",
    "\n",
    "#### Aufgabe 6\n",
    "\n",
    "Schreiben Sie eine Funktion `is_abecedarian` die `True` zurückgiobt, wenn die Buchstaben in einem Wort in alphabetischer Reihenfolge auftauchen (doppelte Buchstaben sind erlaubt). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_abecedarian(word):\n",
    "    # Implementieren Sie hier die Funktion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wie viele solcher Wörter können Sie in der Liste finden?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier Ihr Programm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*(Das längst Wort mit dieser Eigenschaft in der Liste ist `beginnt`.)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9.3 Suche\n",
    "\n",
    "Alle Beispiele im vorherigen Abschnitt haben eines gemeinsam: sie können mit dem Suchmuster gelöst werden, welches wir in [Abschnitt 8.6](seminar08.ipynb#8.6-Suche) kennengelernt haben. Das einfachste Beispiel ist:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def has_no_e(word):\n",
    "    for letter in word.lower():\n",
    "        if letter == 'e':\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die `for`-Schleife geht über die Zeichen in `word` (genauer: nach Umwandlung in Kleinbuchstaben, wegen `lower`). Falls wir den Buchstaben \"e\" finden, können wir sofort `False` zurückgeben; ansonsten gehen wir zum nächsten Buchstaben. Wenn wir die Schleife ganz normal verlassen, d.h. wenn wir kein \"e\" gefunden haben, geben wir `True` zurück.\n",
    "\n",
    "Wir können diese Funktion noch etwas kompakter schreiben, indem wir den `in`-Operator verwenden, aber ich habe Ihnen diese Variante präsentiert, weil sie die Logik hinter der Suche demonstriert.\n",
    "\n",
    "`avoids` ist eine verallgemeinerte Version von `has_no_e` aber es hat die gleiche Struktur:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def avoids(word, forbidden):\n",
    "    for letter in word.lower():\n",
    "        if letter in forbidden:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir können `False` zurückgeben, sobald wir einen verbotenen Buchstaben finden; wenn wir am Ende der Schleife angelagt sind, geben wir `True` zurück.\n",
    "\n",
    "`uses_only` ist ähnlich, außer dass die Semantik der Bedingung umgekehrt ist:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def uses_only(word, available):\n",
    "    for letter in word.lower(): \n",
    "        if letter not in available:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Anstatt einer Liste verbotener Buchstaben haben wir eine Liste erlaubter Buchstaben. Wenn wir einen Buchstaben in `word` finden, der nicht in `available` enthalten ist, können wir `False` zurückgeben.\n",
    "\n",
    "`uses_all` ist ähnlich, außer dass wir die Rolle des Wortes und der Zeichenkette mit den Buchstaben vertauschen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def uses_all(word, required):\n",
    "    for letter in required: \n",
    "        if letter not in word.lower():\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Anstatt die Buchstaben von `word` zu durchlaufen, durchläuft die Schleife die notwendigen Buchstaben. Wenn einer der notwendigen Buchstaben nicht im Wort enthalten ist, können wir `False` zurückgeben.\n",
    "\n",
    "Wenn Sie schon wie ein Informatiker denken würden, dann würden Sie erkannt haben, dass `uses_all` eine Instanz eines zuvor gelösten Problems ist und Sie hätten geschrieben:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def uses_all(word, required):\n",
    "    return uses_only(required, word)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das ist ein Beispiel für ein Form der Programmentwicklung die sich **Zurückführen auf ein vorher gelöstes Problem** (*reduction to a previously solved problem*) nennt. Das bedeutet, dass wir erkennen, dass das Problem welches wir lösen wollen, eine Instanz eines Problems ist, welches wir schon gelöst haben und wir entsprechend die vorhandene Lösung verwenden."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9.4 Schleifen mit Indizes\n",
    "\n",
    "Die Funktionen in den vorherigen Abschnitten wurden mit `for`-Schleifen implementiert, da nur die Zeichen in den Zeichenketten benötigt wurden, nicht aber deren Indizes.\n",
    "\n",
    "Für die Funktion `is_abecedarian` müssen wir nebeneinanderliegende Buchstaben miteinander vergleichen, was mit einer `for`-Schleife etwas schwierig ist:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_abecedarian(word):\n",
    "    previous = word[0]\n",
    "    for c in word:\n",
    "        if c < previous:\n",
    "            return False\n",
    "        previous = c\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Eine Alternative ist die Verwendung von Rekursion:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_abecedarian(word):\n",
    "    if len(word) <= 1:\n",
    "        return True\n",
    "    if word[0] > word[1]:\n",
    "        return False\n",
    "    return is_abecedarian(word[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Eine weitere Option ist eine `while`-Schleife:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_abecedarian(word):\n",
    "    i = 0\n",
    "    while i < len(word)-1:\n",
    "        if word[i+1] < word[i]:\n",
    "            return False\n",
    "        i = i+1\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Schleife startet mit `i = 0` und endet wenn `i = len(word)-1` gilt. Bei jedem Schleifendurchlauf wird das *i*te Zeichen (was wir uns als das aktuelle Zeichen vorstellen können) mit dem *i+1*ten Zeichen (welches wir uns als das nächste Zeichen vorstellen können) verglichen. \n",
    "\n",
    "Wenn das nächste Zeichen (alphabetisch) kleiner als das aktuelle Zeichen ist, dann haben wir eine Verletzung der alphabetischen Reihenfolge entdeckt und geben `False` zurück.\n",
    "\n",
    "Wenn wir das Ende der Schleife erreichen, ohne eine solche Verletzung zu finden, dann hat das Wort unseren test bestanden. Überlegen Sie sich den Ablauf für das Wort \"Beginn\", um sich von der Richtigkeit der Schleife zu überzeugen. Die Länge des Wortes ist 6, so dass `i` beim letzten Schleifendurchlauf den Wert 4 hat, was der Index des vorletzten Zeichens ist. In der letzten Iteration wird das vorletzte mit dem letzten Zeichen verglichen - was genau das ist, was wir brauchen.\n",
    "\n",
    "Hier ist eine Variante von `is_palindrom` (siehe [Abschnitt 6](seminar06.ipynb#Aufgabe-3), die zwei Indizes verwendet. Einer startet am Anfang und wird nach oben gezählt, der andere startet am Ende und wird nach unten gezählt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_palindrome(word):\n",
    "    i = 0\n",
    "    j = len(word)-1\n",
    "\n",
    "    while i<j:\n",
    "        if word[i] != word[j]:\n",
    "            return False\n",
    "        i = i+1\n",
    "        j = j-1\n",
    "\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir könnten das ganze auch auf ein bereits zuvor gelöstes Problem zurückführen und stattdessen schreiben:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_palindrome(word):\n",
    "    return is_reverse(word, word)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "... indem wir `is_reverse` aus [Abschnitt 8.11](seminar08.ipynb#8.11-Debugging) verwenden. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9.5 Debugging\n",
    "\n",
    "Programme zu testen ist schwierig. Die Funktionen in diesem Abschnitt sind vergleichsweise einfach zu testen, denn wir können die Ergebnisse von Hand überprüfen. Dennoch ist es schwierig bis unmöglich eine Menge von Wörtern zu wählen, mit denen sich alle möglichen Fehler abdecken lassen.\n",
    "\n",
    "Schauen wir uns `has_no_e` als Beispiel an, gibt es zwei offensichtliche Fälle, die wir testen müssen: für Wörter, die ein \"e\" enthalten sollte die Funktion `False` zurückgeben und für Wörter, die kein \"e\" enthalten sollte sie \"True\" zurückgeben. Für beide Fälle fällt es uns leicht, ein Testwort zu finden.\n",
    "\n",
    "Bei jedem der Fälle gibt es jedoch einige nicht so offensichtliche Teilfälle. Unter den Wörtern die ein \"e\" enthalten, sollten wir Wörter testen, die ein \"e\" am Anfang, am Ende und irgendwo in der Mitte enthalten. Wir sollten lange Wörter, kurze Wörter und sehr kurze Wörter, wie zum Beispiel die leere Zeichenkette, testen. Die leere Zeichenkette ist ein Beispiel für einen **Spezialfall** - einer der nicht offensichtlichen Fälle, bei dem sich oft Fehler verstecken.\n",
    "\n",
    "Zusätzlich zu den Testfällen, die wir selber erzeugen, können wir unser Programm auch mit einer Wortliste wie z.B. `top10000de.txt` testen. Indem wir uns die Ausgabe anschauen, finden wir vielleicht Fehler. Aber wir sollten vorsichtig sein: es kann sein, dass wir eine Art von Fehlern finden (Wörter, die nicht enthalten sein sollten, es aber trotzdem sind) aber nicht die andere (Wörter die enthalten sein sollten, es aber nicht sind).\n",
    "\n",
    "Im Allgemeinen kann Testen uns helfen, Fehler zu finden, aber es ist nicht einfach, eine gute Menge von Testfällen zu erzeugen. Und selbst wenn wir das machen, können wir uns nie sicher sein, dass unser Programm korrekt ist. Oder, um es mit den Worten eines legendären Informatikers zu sagen:\n",
    "\n",
    "> Program testing can be used to show the presence of bugs, but \n",
    "> never to show their absence!\n",
    "> \n",
    "> — Edsger W. Dijkstra \n",
    "\n",
    "(Testen kann uns zwar helfen, Bugs zu finden, jedoch nicht, ihre Abwesenheit zu beweisen.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9.6 Glossar\n",
    "Legen wir uns eine Liste mit den wichtigsten Begriffen an, die wir im Kapitel 9 gelernt haben:\n",
    "\n",
    "- Dateiobjekt:\n",
    "- Zurückführen auf ein vorher gelöstes Problem:\n",
    "- Spezialfall:\n",
    "\n",
    "Ergänzen Sie die Liste in eigenen Worten. Das ist eine gute Erinnerungs- und Übungsmöglichkeit."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Übung\n",
    "\n",
    "#### Aufgabe 7\n",
    "\n",
    "Diese Aufgabe basiert auf einem Rätsel welches im Radioprogramm [Car Talk](http://www.cartalk.com/content/puzzlers) gesendet wurde. \n",
    "\n",
    "> Gib' mir ein Wort mit zwei aufeinanderfolgenden doppelten Buchstaben. Ich gebe Dir ein paar Wörter, die sich fast dafür qualifizieren (aber nur fast!) - beispielsweise das Wort Kommission, K-o-m-m-i-s-s-i-o-n. Es wäre gut, aber leider hat sich das \"i\" zwischen \"mm\" und \"ss\" eingeschlichen. Oder \"Ballett\" - wenn wir das \"e\" entfernen könnten, würde es klappen. Aber es gibt mindestens ein Wort, welches zwei aufeinanderfolgende Paare von (jeweils gleichen) Buchstaben hat und vielleicht ist es das einzige solche Wort. Welches Wort ist es?\n",
    "\n",
    "Schreiben Sie ein Programm, um das Wort zu finden. Die Lösung für  englische Wörter (http://thinkpython2.com/code/cartalk1.py) findet sogar Wörter mit drei aufeinanderfolgenden Buchstabenpaaren (die es im Deutschen vermutlich nicht gibt, zumindest nicht in der hier verwendeten Wortliste). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier das Programm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aufgabe 8\n",
    "\n",
    "Hier ist ein weiteres [Car Talk Rätsel](http://www.cartalk.com/content/puzzlers):\n",
    "\n",
    "> Als ich letztens auf der Autobahn gefahren bin ist mir auf meinem Kilometerzähler etwas aufgefallen. Wie die meisten Kilometerzähler hat er sechs Stellen, für die ganzen Kilometer. Wenn also mein Auto 300000 Kilometer gefahren wäre, dann würde ich 3-0-0-0-0-0 sehen. Was ich sah, war sehr interessant. Mir ist aufgefallen, dass die letzten vier Ziffern ein Palindrom gebildet haben, d.h. rückwärts gelesen ergeben sie die gleiche Zahlenfolge wie vorwärts. Beispielswiese ist 5-4-4-5 ein Palindrom. Mein Kilometerzähler könnte also beispielsweise 3-1-5-4-4-5 angezeigt haben. \n",
    ">\n",
    "> Einen Kilometer später ergaben die letzten 5 Ziffern ein Palindrom. Mein Kilometerzähler könnte also beispielsweise 3-6-5-4-5-6 anzeigen. Nach einem weiteren Kilometer ergaben die mittleren 4 der 6 Ziffern ein Palindrom. Bis du bereit? Noch einen Kilometer weiter ergaben alle 6 Ziffern ein Palindrom!\n",
    ">\n",
    "> Die Frage ist: was zeigte der Kilometerzähler an, als ich das erste mal darauf schaute?\n",
    "\n",
    "Schreiben Sie ein Python-Programm, welches alle Zahlen mit sechs Ziffern durchtestet und alle Nummern mit dieser Eigenschaft ausgibt. Eine Lösung finden Sie hier: http://thinkpython2.com/code/cartalk2.py."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier das Programm\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Aufgabe 9\n",
    "\n",
    "Und noch ein [Car Talk Rätsel](http://www.cartalk.com/content/puzzlers) welches sich mit Suche lösen lässt:\n",
    "\n",
    "> Letztens hat mich meine Mutter besucht und uns ist aufgefallen, dass die zwei Ziffern, die mein Alter angegeben rückwärts gelesen ihrem Alter entsprachen. Wir haben uns gefragt, wie oft das über die Jahre schon passiert ist, aber wir wurden abgelenkt und haben keine Antwort gefunden.\n",
    "> Als ich nach Hause kam ist mir aufgefallen, dass die Ziffern unserer Alter sich bisher sechs mal umkehren ließen. Mir fiel auch auf, dass es in ein paar Jahren nochmal passieren würde, wenn es uns bis dahin gut geht. Und wenn wir richtig viel Glück haben, würde es danach noch einmal passieren. Anders gesagt: es könnte acht mal insgesamt passieren. Die Frage ist also, wie alt ich gerade bin?\n",
    "\n",
    "Schreiben Sie ein Programm, welches nach einer Lösung für dieses Rätsel sucht. Hinweis: Sie könnten die Zeichenketten-Methode [zfill](http://python-reference.readthedocs.io/en/latest/docs/str/zfill.html) nützlich finden. Lösung: http://thinkpython2.com/code/cartalk3.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier ihr Programm\n",
    "\n"
   ]
  },
  {
   "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). 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/3/30/Binette-typo.png)\n",
    "\n",
    "Herzlichen Glückwunsch! Sie haben das 8. Kapitel geschafft. Weiter geht es in [9: Wortspiele](seminar09.ipynb)."
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}