"...git@scm.cms.hu-berlin.de:iqb/verona-modules-aspect.git" did not exist on "65d71db5c2ccd6d4a0247d13d0a11547f81b0ea4"
Newer
Older
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Seminar Problemorientierte Programmierung\n",
"\n",
"## 9 Fallstudie: Wortspiele\n",
"[Chapter 9: Case study: Word play](http://greenteapress.com/thinkpython2/html/thinkpython2010.html)\n",
"\n",
"In diesem Abschnitt gibt es die zweite Fallstudie. In dieser werden Wort-Rätsel 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",
"### Ihre Lernziele:\n",
"\n",
"Beschreiben Sie in 2-3 Stichpunkten kurz was Sie im Seminar heute lernen wollen. Klicken Sie dazu doppelt auf diesen Text und bearbeiten Sie dann den Text:\n",
"## Exkurs: Was mir an Python gefällt\n",
"\n",
"Dieser Code enthält das Grundgerüst, um eine auf TCP basierende Serveranwendung zu programmieren."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Quellen: https://docs.python.org/3/howto/sockets.html und \n",
"# http://www.binarytides.com/python-socket-server-code-example/\n",
"# function for handling connections. This will be used to create threads\n",
"def client_thread(conn):\n",
" # sending message to connected client\n",
" conn.send(bytearray('Welcome to the server. Type something and hit enter\\n', \"utf-8\")) #send only takes string\n",
" \n",
" # infinite loop so that function do not terminate and thread do not end.\n",
" while True:\n",
" \n",
" # receiving from client\n",
" data = conn.recv(1024)\n",
" if not data: \n",
" break\n",
" # print on server side\n",
" print(data.decode(\"utf-8\"))\n",
" # echo to client side\n",
" reply = bytearray('OK ... ', \"utf-8\") + data\n",
" conn.sendall(reply)\n",
" \n",
" # came out of loop\n",
" conn.close()\n",
" \n",
"# create an INET, STREAMing socket\n",
"serversocket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)\n",
"# bind the socket to a public host, and a port\n",
"# serversocket.bind((socket.gethostname(), 8080))\n",
"# use localhost instead \n",
"serversocket.bind((\"localhost\", 8080))\n",
"# become a server socket\n",
"serversocket.listen(5)\n",
"\n",
"while True:\n",
" # accept connections from outside\n",
" (clientsocket, address) = serversocket.accept()\n",
" # now do something with the clientsocket\n",
" # in this case, we'll pretend this is a threaded server\n",
" ct = client_thread(clientsocket)\n",
" ct.run()\n",
"\n",
"serversocket.close()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Wenn Sie den Code starten und sich dann mit Hilfe von Telnet mit der Anwendung verbinden (telnet localhost 8080), werden alle Eingaben an Sie zurückgespiegelt (\"echo\") und hier in Jupyter ausgegeben. Das ist eine sehr einfache Testanwendung, die aus Sicherheitsgründen nur von Ihrem Rechner aus erreichbar ist.\n",
"\n",
"Falls Ihr Rechner keinen Paketfilter (\"Firewall\") laufen hat und Sie die Zeile mit localhost auskommentieren und stattdessen die mit socket.gethostbyname() aktivieren, dann ist die Anwendung ggf. auch von anderen Rechnern erreichbar und stellt ziemlich sicher eine Sicherheitslücke dar. Gehen Sie also vorsichtig mit dieser Option um."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\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. Wir können sie aber 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. Im Allgemeinen sollten Dateien heute in Unicode codiert\n",
"# sein, bei diesen ist in Python3 diese Angabe nicht notwendig.\n",
"# Leider ist die Datei vom Wortschatz-Projekt aber noch in der\n",
"# Latin1-Kodierung, so dass wir dies Python mitteilen müssen."
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
]
},
{
"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",
]
},
{
"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": [
"Diese Schleife können Sie leicht nutzen, um nach Wörtern mit bestimmten Eigenschaften zu suchen. Gibt es im Deutschen Wörter, die auf \"gry\" enden? Oder zumindest auf \"ry\"?\n",
"\n",
"<details>\n",
" <summary type=\"button\" class=\"btn btn-info\">Hinweis</summary>\n",
" <div class=\"alert alert-info\" role=\"alert\">\n",
"\n",
"Mit der Zeichenkettenfunktion [endswith](https://docs.python.org/3/library/stdtypes.html#str.endswith) können Sie prüfen, ob eine Zeichenkette auf eine andere Zeichenkette endet. Zusammen mit einer Verzweigung (`if`) können Sie damit nur die entsprechenden Wörter ausgeben.\n",
" \n",
" </div> \n",
"</details> \n",
" \n",
"\n",
"\n",
"\n",
"[Words that end in GRY](https://xkcd.com/169/), Randall Munroe"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 9.2 Übung\n",
"\n",
"Die Lösungen der Aufgaben gibt es wie gehabt unter der jeweiligen Aufgabe und mit ergänzender Theorie 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": [
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
"Am Ergebnis werden Sie merken, dass die Wortliste nicht ganz bereinigt ist und manche Zeilen Phrasen bestehend aus mehreren Wörtern enthalten. \n",
"\n",
"\n",
"([Spoiler Alert](https://xkcd.com/109/), Randall Munroe)\n",
"\n",
"1. Öffnen Sie die Datei in einer neuen Variablen und rufen Sie diese im Funktionskopf auf.\n",
"2. Um zu überprüfen, ob ein Wort lang genug ist, müssen Sie jede Zeile einzeln aufrufen. Verwenden Sie dafür eine `for`- Schleife, die Sie zuvor gesehen haben.\n",
"3. Für jede Zeile müssen Sie nun prüfen ob die Bedungung erfüllt ist. Wie könnte diese Bedingung aussehen?\n",
"4. Wenn die Bedinung erfüllt ist, geben Sie die entsprechende Zeile mit einem `print`-Statement aus. Verwenden Sie nicht `return`, da Sie die Funktion so sofort beenden und nur das erste Element finden würden, dass die Bedingung erfüllt.\n",
"5. Schreiben Sie den Funktionsaufruf und schauen Sie sich das Ergebnis an."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"fin = open('top10000de.txt', encoding=\"latin1\")\n",
"\n",
"def long(fin):\n",
" \"\"\"Findet Zeilen mit mehr als 20 Buchstaben aus einer beliebigen Wortliste im txt Format\"\"\"\n",
" for line in fin:\n",
" if len(line)>20:\n",
" print (line.strip())\n",
" \n",
" \n",
"long(fin)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Aufgabe 2\n",
"\n",
"\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 es 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. 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"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"([Spoiler Alert](https://xkcd.com/109/), Randall Munroe)\n",
"\n",
"1. Schreiben Sie den Funktionskopf und legen Sie fest welche Rückgabewerte es gibt. (Wenn kein `e` vorkommt, `True`, sonst `False`.)\n",
"2. Um jeden Buchstaben in dem Wort zu prüfen, schreiben Sie eine `for`-Schleife, wie in [Abschnitt 8.3](seminar08.ipynb#Durchlauf-mit-einer-for-Schleife) gezeigt.\n",
"3. Prüfen Sie für jeden Buchstaben, ob er `e` ist. Denken Sie dabei daran, dass die Buchstaben sowohl groß als auch klein geschrieben sein können. Wenn der Buchhstabe `e` ist, kann der Test sofort abgebrochen und die Schleife mit `return False` verlassen werden.\n",
"4. Wenn in der Schleife nie eine `return`-Anweißung erreicht wird, wird die Schleife verlassen und `True` zurückgegeben."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
"def has_no_e(word):\n",
" for letter in word: \n",
" if letter == 'e':\n",
" return False\n",
" if letter == 'E':\n",
" return False\n",
" return True\n",
" \n",
"has_no_e('nicht')"
]
},
{
"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\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"([Spoiler Alert](https://xkcd.com/109/), Randall Munroe)\n",
"\n",
"1. Gehen Sie hier analog zu Aufgabe 1 vor, kopieren Sie ruhig den Code, den Sie für Aufgabe 1 geschrieben haben, so verringern Sie die Gefahr von Tippfehlern.\n",
"2. Verändern Sie die `if`-Verzweigung so, dass Sie `has_no_e` aufruft und den Rückgabewert prüft. Liefert `has_no_e` `True` zurück wird das Wort ausgegeben.\n",
"3. Um den Anteil zu bestimmen, müssen wir zählen auf wie viele Worte die Bedingung zutrifft. Legen Sie dafür eine Variable an und initialisieren Sie sie mit 0.\n",
"4. Immer wenn Sie das Wort ausgeben inkrementieren Sie den Zähler.\n",
"5. Um den Anteil zu berechnen teilen Sie diese Variable durch die Gesamtmenge an Wörtern, in diesem Fall 10000. Vergessen Sie nicht die so berechnete Zahl auszugeben."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"fin = open('top10000de.txt', encoding=\"latin1\")\n",
"def test(fin):\n",
" count=0\n",
" for line in fin:\n",
" if has_no_e(line):\n",
" count=count+1\n",
" print(line)\n",
" anteil=count/10000\n",
" print(anteil)\n",
" \n",
"test(fin)"
]
},
{
"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. \n",
"\n",
"*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"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def avoids(word, forbidden):\n",
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
"\n",
"([Spoiler Alert](https://xkcd.com/109/), Randall Munroe)\n",
"\n",
"\n",
"1. Diese Aufgabe ist eine Verallgemeinerung von `has_no_e`.\n",
"2. Auch in dieser Aufgabe muss das Wort Buchstabe für Buchstabe überprüft werden.\n",
"3. Der Vergleich findet allerdings nicht mit `e` statt, sondern mit dem zusätzlich eingegebenen Buchstaben.\n",
"4. Da wir im Vorfeld nicht wissen, um welchen Buchstaben es sich handelt, können wir nicht einfach zwei Tests durchführen, sondern müssen stattdessen das Wort vereinheitlichen. Nutzen Sie dazu `word.lower()`."
]
},
{
"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\n",
"\n",
"\n",
"avoids(\"ad\", \"f,g,h\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"Verändern Sie Ihr Programm von Aufgabe 2, so dass Sie zunächst die 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": [
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
"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 590.*)\n",
"\n",
"\n",
"\n",
"([Spoiler Alert](https://xkcd.com/109/), Randall Munroe)\n",
"\n",
"1. Auch dieser Test funktioniert analog zum ersten Test. Kopieren Sie die Funktion, geben Sie ihr einen neuen Namen und passen Sie sie an. Dadurch vermeiden Sie eventuelle Flüchtigkeitsfehler.\n",
"2. Aus der Aufgabenstellung geht hervor, dass wir eine Nutzereingabe brauchen. Verwenden Sie dafür `input`. \n",
"3. Stellen Sie sicher, dass die Eingabe aus `input` einer Variablen zugewießen wird.\n",
"4. Rufen Sie dann in der Schleife `avoids` mit dem User-Input auf. Um zu sehen, wie viele Worte Sie nicht ausgeschlossen haben, verwenden Sie den Zähler.\n",
"5. Geben Sie diesen Zähler nach Verlassen der `for`-Schleife einmalig aus."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"fin = open('top10000de.txt', encoding=\"latin1\")\n",
"\n",
"def test2(fin):\n",
" forbidden=input(\"Geben Sie Buchstaben ein, die nicht vorkommen sollen:\\n\")\n",
" count=0\n",
" print(\"Dies sind die übrigen Worte:\")\n",
" for line in fin: \n",
" word=line.strip()\n",
" if avoids(word, forbidden):\n",
" count=count+1\n",
" print (word)\n",
" print (count)\n",
"test2(fin)"
]
},
{
"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": [
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
"\n",
"\n",
"([Spoiler Alert](https://xkcd.com/109/), Randall Munroe)\n",
"\n",
"1. Auch hier können Sie Code wiederverwenden. Überlegen Sie wie Sie den Code anpassen können.\n",
"2. Diesmal wollen Sie nicht prüfen, ob der Buchstabe verboten ist. Stattdessen interessiert uns, ob er erlaubt ist.\n",
"3. Sie müssen die Prüfung also negativ, nicht positiv formulieren. Wenn ein Buchstabe des Wortes nicht in der verfügbaren Liste zu finden ist, kann das Programm abbrechen und `False` zurück geben.\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\n",
"\n",
"uses_only(\"acefhln\", \"acefhln\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Können Sie einen Satz bilden, der nur die Buchstaben `acefhln` enthält? Nutzen Sie ihr Programm um alle Worte auf der Liste zu finden, die Sie verwenden dürfen."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"([Spoiler Alert](https://xkcd.com/109/), Randall Munroe)\n",
"\n",
"1. Wie gehabt, können Sie Code wiederverwenden und es ist empfehlenswert, das zu tun, da Sie so viele Flüchtigkeitsfehler vermeiden können. Nehmen Sie am besten den Testcode, den Sie für `forbidden` verwendet haben.\n",
"2. Sie müssen den Testcode natürlich anpassen. Als erstes können Sie die `if`-Verzweigung verändern. Welche Funktion wird aufgerufen, um zu testen, ob ein Wort die Bedingung erfüllt?\n",
"3. Wenn Sie dies angepasst haben, schauen Sie, was Sie an die Funktion übergeben müssen. Das Wort wird automatisch in der Schleife übergeben, aber die Liste der verfügbaren Buchstaben müssen Sie manuell anpassen. Da eine Nutzereingabe nicht notwendig ist, können Sie der Variablen einfach einen String zuweißen, der alle erlaubten Buchstaben enthält.\n",
"4. Drucken Sie alle Worte aus, die die Bedingung erfüllen, und versuchen Sie aus den Worten einen Satz zu bilden.\n",
"*Hinweiß: Ich habe mich entschieden die Zählervariable zu behalten, da Sie mir sagt, wie viele Worte ich zur Verfügung habe. Dies ist nicht notwendig.*"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"\n",
"\n",
"fin = open('top10000de.txt', encoding=\"latin1\")\n",
"\n",
" \n",
" \n",
"def sentence(fin):\n",
" available=\"acefhln\"\n",
" count=0\n",
" for line in fin:\n",
" word=line.strip()\n",
" if uses_only(word, available):\n",
" count=count+1\n",
" print(line)\n",
" return count\n",
" \n",
"\n",
"sentence(fin)\n",
"\n",
"#Elf Fahnen lehnen an Helene\n",
"#Aber ich bin sicher Sie können einen besseren Satz bilden. Viel Erfolg!"
]
},
{
"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"
]
},
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"([Spoiler Alert](https://xkcd.com/109/), Randall Munroe)\n",
"\n",
"1. Wenn Sie das Wort Buchstabe für Buchstabe durchgehen, können Sie sicherstellen, dass nur erlaubte Buchstaben verwendet werden. Können Sie so auch sicherstellen, dass alle Buchstaben verwendet werden? Probieren Sie es aus.\n",
"2. Da es so nicht möglich ist, überlegen Sie, wie Sie sicherstellen können, dass alle Buchstaben verwendet werden. Sie können dafür die Strukturen verwenden, die Sie bereits kennen. \n",
"3. Wir haben gesehen, dass wir unseren Buchstaben mit einer ganzen Liste an Buchstaben vergleichen können. In diesem Fall behandeln wir word.lower() als diese Liste und die Liste mit vorgegebenen Buchstaben als unser Wort. Gehen Sie die Liste also Buchstabe für Buchstabe durch und gleichen Sie Sie mit word.lower() ab. Überprüfen Sie wann `True` und wann `False` zurückgegeben wird."
]
},
{
"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\n",
"uses_all(\"Hallo\", \"ahlo\")"
]
},
{
"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",
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
"\n",
"\n",
"([Spoiler Alert](https://xkcd.com/109/), Randall Munroe)\n",
"\n",
"1. Wie gehabt können Sie den Test kopieren. Bennenen Sie ihn um und passen Sie auf, dass Sie den Namen auch in dem Funktionsaufruf ändern. \n",
"2. Hier wird gefragt, wie viele Wörter alle Vokale enthalten, der Zähler ist also ein notwendiges Element der Funktion. \n",
"3. Wie müssen sie die `if`-Anweißung anpassen, was ist die zweite Variable, die Sie der Funktion übergeben?"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def all_vowels(fin):\n",
" required='aeiou'\n",
" count=0\n",
" for line in fin:\n",
" word=line.strip()\n",
" if uses_all(word, required):\n",
" count=count+1\n",
" print(line)\n",
" return count\n",
"\n",
"\n",
"\n",
"fin = open('top10000de.txt', encoding=\"latin1\")\n",
"all_vowels(fin)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Schreiben Sie eine Funktion `is_abecedarian` die `True` zurückgibt, 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"
]
},
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"\n",
"([Spoiler Alert](https://xkcd.com/109/), Randall Munroe)\n",
"\n",
"1. Hier gibt es verschiedene richtige Lösungen. Weiter unten werden 3 verschiedene Lösungen vorgestellt und es kann sein, dass sich Ihr Ansatzt von dem hier präsentierten unterscheiden. Das heißt nicht zwingend, dass Ihr Ansatz falsch ist. Schauen Sie sich gegebenenfalls die Lösung weiter unten an, wenn Sie sich unsicher sind.\n",
"2. Der hier verwendete Ansatz verwendet eine `for`-Schleife. \n",
"3. Es wird eine Hilfsvariable benötigt, die den letzten Buchstaben speichert, damit die Buchstaben miteinander verglichen werden können. Diese wird vor der Schleife auf den ersten Buchstaben des Wortes gesetzt. \n",
"4. in jedem Durchlauf der Schleife wird der aktuelle Buchstabe mit dem vorherigen verglichen. Wenn er kleiner ist, wird `False` zurückgegeben, sonst wird `previous` auf `letter` gesetzt. \n",
"5. Wird die Schleife verlassen, ohne das `False` zurückgegeben wurde, wird `True` zurückgegeben. "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def is_abecedarian(word):\n",
" previous=word[0]\n",
" for letter in word.lower():\n",
" if letter<previous:\n",
" return False\n",
" previous=letter\n",
" return True\n",
"\n",
"is_abecedarian(\"beginnt\")"
]
},
{
"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ängste Wort mit dieser Eigenschaft in der Liste ist `beginnt`.)*"
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"([Spoiler Alert](https://xkcd.com/109/), Randall Munroe)\n",
"\n",
"1. Wie gehabt ist dies eine Abwandlung des ersten Tests, den Sie geschrieben haben. Kopieren Sie also eine der Testanweißungen. Da nach der Anzahl der Worte mit dieser Eigenschaft gefragt ist, bietet es sich an, einen der Tests zu kopieren, der bereits count enthält. \n",
"2. Überlegen Sie, wie Sie diese Funktion anpassen müssen. An welcher Stelle wird `is_abecedarian()` aufgerufen, was passiert wenn `is_abecedarian() True` zurückgibt?\n",
"3. Vergessen Sie nicht die .txt datei zu öffnen und zu übergeben. "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def abecedarian(fin):\n",
" count=0\n",
" for line in fin:\n",
" word=line.strip()\n",
" if is_abecedarian(word):\n",
" count=count+1\n",
" print(line)\n",
" return count\n",
"\n",
"\n",
"\n",
"\n",
"fin = open('top10000de.txt', encoding=\"latin1\")\n",
"abecedarian(fin)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"[State Word Map](https://xkcd.com/1845/), Randall Munroe\n",
"\n",
"Die Wortliste erlaubt uns viele interessante Fragestellungen zu beantworten. Welches ist beispielsweise das längste Wort in der Wortliste? [Wikipedia zu den längsten Wörtern im Deutschen](https://en.wikipedia.org/wiki/Longest_words#German)\n",
"\n",
"### 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` (genau genommen nach der Umwandlung in Kleinbuchstaben, wegen der Verwendung von `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 sie 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 angelangt sind, geben wir `True` zurück.\n",
"`uses_only` ist ähnlich, aber die Semantik der Bedingung ist umgekehrt:\n"
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
]
},
{
"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:])"
]
},
{
"metadata": {},
"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",
"Hier ist eine Variante von `is_palindrome` (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": {},