seminar10.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",
    "Mit Hilfe von pydotplus ist es möglich, Graphen zu visualisieren, die auch direkt im Jupyter Notebook angezeigt werden können. Als Beispiel wird hier ein [Trie](https://de.wikipedia.org/wiki/Trie) erzeugt, der schnellen Zugriff auf die Präfixe einer Liste von Wörtern bildet (so etwas ermöglicht z.B. eine schnelle Wortvervollständigung bei der Eingabe von Wörtern auf der Handy-Tastatur ([siehe](https://towardsdatascience.com/implementing-a-trie-data-structure-in-python-in-less-than-100-lines-of-code-a877ea23c1a1))."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.display import Image  \n",
    "import pydotplus\n",
    "\n",
    "# Der Quellcode für die Klasse TrieNode und die Funktion add stammt von der Webseite\n",
    "# from https://towardsdatascience.com/implementing-a-trie-data-structure-in-python-in-less-than-100-lines-of-code-a877ea23c1a1\n",
    "class TrieNode(object):\n",
    "    def __init__(self, char: str):\n",
    "        self.char = char\n",
    "        self.children = []\n",
    "        self.word = None\n",
    "        self.counter = 1\n",
    "\n",
    "def add(root, word):\n",
    "    node = root\n",
    "    for char in word:\n",
    "        found_in_child = False\n",
    "        # Search for the character in the children of the present `node`\n",
    "        for child in node.children:\n",
    "            if child.char == char:\n",
    "                # We found it, increase the counter by 1 to keep track that another\n",
    "                # word has it as well\n",
    "                child.counter += 1\n",
    "                # And point the node to the child that contains this char\n",
    "                node = child\n",
    "                found_in_child = True\n",
    "                break\n",
    "        # We did not find it so add a new chlid\n",
    "        if not found_in_child:\n",
    "            new_node = TrieNode(char)\n",
    "            node.children.append(new_node)\n",
    "            # And then point node to the new child\n",
    "            node = new_node\n",
    "    # Everything finished. Mark it as the end of a word.\n",
    "    node.word = word\n",
    "\n",
    "# fügt eine Liste von Wörtern hinzu\n",
    "def add_words(root, words):\n",
    "    for word in words:\n",
    "        add(root, word)\n",
    "\n",
    "# wandelt den Baum in einen Graphen, also eine Menge von Knoten (vertices) und Kanten (edges) um\n",
    "# Eingaben:\n",
    "# - root: Wurzelknoten des Baums\n",
    "# - vertices: (leere) Liste mit Knoten (jeder Knoten ist vom Typ TrieNode)\n",
    "# - edges: (leere) Liste mit Kanten (jede Kante ist ein Tupel von ganzen Zahlen, die die Knoten-IDs repräsentieren)\n",
    "def tree_to_graph(root, vertices, edges):\n",
    "    # Hinzufügen des Wurzelknotens\n",
    "    if len(vertices) == 0:\n",
    "        vertices.append(root)\n",
    "    # wir nummerieren die Knoten durch:\n",
    "    # jeder Knoten erhält als ID seine Position in der Liste (ab 1 zählend)\n",
    "    rootid = len(vertices)\n",
    "    # Hinzufügen der Kindknoten\n",
    "    for child in root.children:\n",
    "        vertices.append(child)\n",
    "        childid = len(vertices)\n",
    "        \n",
    "        # Kante zum Kindknoten hinzufügen\n",
    "        edges.append((rootid, childid))\n",
    "\n",
    "        # Rekursion, falls Kindknoten vorhanden\n",
    "        if child.children:\n",
    "            tree_to_graph(child, vertices, edges)\n",
    "\n",
    "# erzeugt eine Zeichenkette in der Syntax for GraphViz (http://graphviz.org/)\n",
    "def build_graph_string(vertices, edges):\n",
    "    # Konfiguration für Graph, Knoten und Kanten \n",
    "    s = \"\"\"\n",
    "digraph G {\n",
    "  graph [rankdir=\"LR\"];\n",
    "  node [sep=\"+0.01,+0.01\", height=\"0\", width=\"0\", shape=\"box\", margin=\"0.05, 0.05\"];\n",
    "  edge [];\n",
    "    \"\"\"\n",
    "    # Hinzufügen der Knoten\n",
    "    for i, vertice in enumerate(vertices):\n",
    "        label = vertice.char\n",
    "        # Knoten, die ein Wort repräsentieren, sollen dieses zusätzlich enthalten\n",
    "        if vertice.word:\n",
    "            label += \" (\" + vertice.word + \")\"\n",
    "        s += '  ' + str(i + 1) + ' [label=\"' + label + '\"];\\n'\n",
    "    # Hinzufügen der Kanten\n",
    "    for v1, v2 in edges:\n",
    "        s += '  ' + str(v1) + ' -> ' + str(v2) + ';\\n'\n",
    "    s += \"}\"\n",
    "    return s\n",
    "        \n",
    "\n",
    "# Beispielwörter zum Visualisieren - ergänzen Sie die Liste oder probieren Sie andere Wörter\n",
    "words = [\"Braten\", \"Brauerei\", \"Brause\", \"Brot\", \"Brett\", \n",
    "         \"Brei\", \"Brief\", \"Breite\", \"Brille\", \"Brand\", \"Bruder\", \n",
    "         \"Bruch\", \"Brust\", \"Bronze\", \"Brache\", \"Branche\", \n",
    "         \"Brandung\", \"Braten\", \"Bratsche\", \"Bremse\", \"Brenner\", \n",
    "         \"Brezel\", \"Brikett\", \"Brise\", \"Brocken\", \"Bronze\", \n",
    "         \"Brosche\", \"Brunnen\", \"Brut\"]\n",
    "# Alternative: aus einer Datei einlesen\n",
    "# words = []\n",
    "# fin = open('top10000de.txt', encoding=\"latin1\")\n",
    "# for line in fin:\n",
    "#     if line.startswith(\"Bra\"):\n",
    "#         words.append(line.strip())\n",
    "\n",
    "# Wörter zum Trie hinzufügen (in sortierter Reihenfolge, das liest sich leichter)\n",
    "root = TrieNode('*')\n",
    "add_words(root, sorted(words))\n",
    "\n",
    "# aus dem Trie einen Graph erzeugen\n",
    "vertices = []\n",
    "edges = []\n",
    "tree_to_graph(root, vertices, edges)\n",
    "\n",
    "# die Zeichenkette für GraphViz erzeugen\n",
    "graphdata = build_graph_string(vertices, edges)\n",
    "\n",
    "# den Graph zeichnen und anzeigen\n",
    "graph = pydotplus.graph_from_dot_data(graphdata)  \n",
    "Image(graph.create_png())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10 Listen\n",
    "\n",
    "In diesem Kapitel lernen wir einen der nützlichsten eingebauten Datentypen von Python kennen: Listen. Wir lernen auch mehr über Objekte und was passieren kann, wenn es mehr als einen Namen für das gleiche Objekt gibt.\n",
    "\n",
    "### 10.1 Eine Liste ist eine Folge\n",
    "\n",
    "Wie eine Zeichenkette, ist eine **Liste** eine Folge (*sequence*) von Werten. In einer Zeichenkette sind die Werte Zeichen; in einer Listen können sie von jedem Typ sein. Die Werte in einer Liste heißen **Elemente**, im Englischen manchmal auch *items*.\n",
    "\n",
    "Es gibt mehrere Möglichkeiten, eine neue Liste zu erzeugen. Die einfachste ist es, Elemente in eckigen Klammern einzuschließen (`[` und `]`):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[10, 20, 30, 40]\n",
    "l = ['crunchy frog', 'ram bladder', 'lark vomit']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das erste Beispiel ist eine Liste mit vier ganzen Zahlen. Das zweite Beispiel ist eine Liste mit drei Zeichenketten. Die Elemente einer Liste müssen nicht vom gleichen typ sein. Die folgende Liste enthält eine Zeichenkette, eine Gleitkommazhal, eine ganze Zahl und (ja!) eine andere Liste:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "['spam', 2.0, 5, [10, 20]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Eine Liste innerhalb einer anderen Liste ist **verschachtelt** (*nested*).\n",
    "\n",
    "Eine Liste, die keine Elemente enthält wird **leere Liste** genannt. Wir können Sie mit Hilfe von leeren Klammern erzeugen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[]"
   ]
  },
  {
   "cell_type": "markdown",