Heute möchte ich mal ein etwas anderes Projekt von mir vorstellen. In meinem Repo zum Party-Problem habe ich im Laufe des letzten Jahres das immer gleiche Problem in verschiedenen Programmiersprachen gelöst. Inzwischen sind da so einige Sprachen zusammengekommen.
Das Party-Problem
Das so genannte Party-Problem gehört zu den eher klassischen Problemen der Informatik. Im Kern geht es darum, von einer Liste potentieller Gäste für eine Party alle Personen zu streichen, die nicht mit einer festgelegten Mindestanzahl an Personen auf der Liste befreundet sind.
Was ist daran so toll?
Das Problem ist mir zum ersten Mal in meinem Uni-Kurs Algorithmik über den Weg gelaufen, für den wir es in einer Programmiersprache unserer Wahl mit einem rekursiven Ansatz lösen sollten.
Dabei habe ich festgestellt, dass diese Aufgabenstellung recht gut geeignet ist, um mal in eine neue Programmiersprache rein zu schnupper, da sie viele der am häufigsten benötigten Funktionen erfordert:
- Lesen aus Dateien
- Trennen von Zeichenketten
- Konvertierung von Zeichenketten in Zahlen
- Arbeiten mit Listen
- Schleifenkonstruktionen
- Rekursionen
- Eigene Klassen und Objekte
Wenn man es ordentlich macht lernt man außerdem noch etwas über die Dokumentation von Klassen und Funktionen sowie über Zeilenkommentare in der jeweiligen Programmiersprache.
Die Lösung des Problems in der Theorie
Der Algorithmus zum Lösen des Party-Problem braucht 2 Parameter: 1. die Gästeliste und 2. die Mindestanzahl der Freunde pro Gast. Im Folgenden schreibe ich das als party (List guests, int k), wobei guests die Liste der Gäste ist und k die Mindestanzahl der Freunde. Für eine Gästeliste guests1 und eine Mindestanzahl der Freunde 3 schreibe ich also party (guests1, 3).
Der Algorithmus im Pseudocode
party(guests, k): if (k gleich 0): return guests if (Größe von guests kleiner oder gleich k): return eine leere Liste for jede person in guests: if (Anzahl der Freunde von person < k): id = ID der person entferne person aus guests for jede person2 in guests: lösche id aus der Freundesliste von person2 guests = party(guests, k) return guests return guests
Beispiel
Als k nehme ich hier 4, als Beispielliste verwende ich die Liste aus meinem oben verlinkten Repo:
ID des Gastes | Vorname | Nachname | IDs der Freunde |
---|---|---|---|
1 | Conrad | Zuse | 2, 3, 4, 5, 6, 7 |
2 | Gordon | Moore | 1, 3 |
3 | Robert | Noyce | 1, 2 |
4 | Linus | Torvalds | 1, 5, 6, 7 |
5 | Bruce | Schneier | 1, 4, 6, 7 |
6 | Bjarne | Stroustrup | 1, 4, 5, 7 |
7 | Alan | Turing | 1, 4, 5, 6 |
Wenden wir nun also party auf unsere Beispieldaten an. Da wir hier mit Rekursionen arbeiten, die Funktion party sich also selber mit geänderten Parametern aufruft, benenne ich die Rekursionen mit R0, R1 und R2.
Wir beginnen mit dem ersten Aufruf der Funktion party (guests, 4), also R0.
Zuerst wird in Zeile 2 geprüft, ob k gleich 0 ist. Dann würde sich an der Liste nichts ändern und sie würde unverändert zurückgegeben. Das ist aber nicht der Fall, also weiter.
In Zeile 4 wird geprüft, ob die Anzahl der Gäste auf der Liste kleiner als k ist. Dann könnte keiner der Gäste die Bedingung k erfüllen und entsprechend würde eine leere Liste zurückgegeben.
Interessant wird es ab Zeile 7. Hier fangen wir so richtig an, mit der Liste zu arbeiten. Wir nehmen uns nacheinander jeden Gast auf der Liste vor. In Zeile 8 prüfen wir, ob der Gast weniger als k Freunde hat. Gast 1 hat k oder mehr Freunde, deshalb geht es direkt mit Gast 2 weiter. Der hat zu wenig Freunde, weshalb wir in Zeile 9 landen. Hier speichern wir die ID von Gast 2 zwischen und streichen dann in Zeile 10 Gast 2 von der Liste.
Da wir nun einen Gast von der Liste gestrichen haben müssen wir die Freundeslisten der anderen Gäste bereinigen. Dafür müssen wir uns in Zeile 11 alle Gäste der nun kleiner gewordenen Liste einzeln vornehmen, um in Zeile 12 die eben zwischengespeicherte ID aus der Freundesliste des jeweiligen Gastes zu streichen.
Nachdem wir diese zweite, innere Schleife durchlaufen haben gehen wir in Zeile 13 in die Rekursion R1. Dabei übergeben wir die nun um einen Gast kleinere Liste und k.
Die Rekursion R1 beginnt also wieder bei Zeile 1 und läuft genau so ab, wie der erste Durchlauf. Allerdings wir nicht Gast 2 gestrichen, sondern nun Gast 3, da dieser nun der erste auf der Liste mit zu wenig Freunden ist. Nachdem also Gast 3 von der Liste gestrichen ist und die Freundeslisten der verbleibenden Gäste bereinigt wurden, geht es in Zeile 13 in eine weitere Rekursion.
In der Rekursion R2 durchlaufen wir also ein weiteres Mal die Schleife aus Zeile 7. Da aber bereits alle Gäste mit zu wenigen Freunden gestrichen wurden wird zwar für jeden der verbliebenen Gäste die Bedingung in Zeile 8 geprüft, die Zeilen 9 bis inkl. 14 kommen aber nicht zum Zuge. Wir landen also in Zeile 15 und geben die unveränderte Liste zurück an die vorherige Rekursion R1. R2 endet hier also.
Zurück in der Rekursion R1 ist die Zeile 13 nun also abgeschlossen und wir haben die Liste aus R2 als unsere Gästeliste übernommen. Diese geben wir nun an R0 zurück.
Zurück in R0 ist auch hier die Zeile 13 abgeschlossen. Wir haben aus R1 die aus R2 übernommene Liste zurückerhalten, die nun nur noch die Gäste 1, 4, 5, 6 und 7 enthält. Wir landen also in Zeile 14 und geben die fertige Liste zurück. Das Programm endet hier.
Wir haben also in jedem Programmdurchlauf einen Gast von der Liste gestrichen und das Programm danach auf die kleinere Liste angewendet. Die Anzahl der Rekursionen entspricht also der Anzahl der zu streichenden Gäste und nur in der letzten Rekursion wird die Liste nicht mehr geändert.
Das Ergebnis des gesamten Programms ist also die folgende Liste:
ID des Gastes | Vorname | Nachname | IDs der Freunde |
---|---|---|---|
1 | Conrad | Zuse | 4, 5, 6, 7 |
4 | Linus | Torvalds | 1, 5, 6, 7 |
5 | Bruce | Schneier | 1, 4, 6, 7 |
6 | Bjarne | Stroustrup | 1, 4, 5, 7 |
7 | Alan | Turing | 1, 4, 5, 6 |
Die Lösung des Problems in der Praxis
Natürlich braucht der Algorithmus noch einiges an Drumherum, damit er als Programm funktionieren kann:
Da hier auch mit Objektorientierung gearbeitet werden soll muss eine Klasse für Gäste erstellt werden, die die 4 Eigenschaften eines jeden Gastes (ID, Vorname, Nachname, Freundesliste) zusammenfasst.
Die Gästeliste muss aus einer Textdatei eingelesen und in eine Liste von Objekten dieser neuen Klasse umgewandelt werden. Diese Datei kann zum Beispiel so aussehen:
1|Conrad|Zuse|2,3,4,5,6,7 2|Gordon|Moore|1,3 3|Robert|Noyce|1,2 4|Linus|Torvalds|1,5,6,7 5|Bruce|Schneier|1,6,7,4 6|Bjarne|Stroustrup|1,5,7,4 7|Alan|Turing|1,5,6,4
Die Datei muss also zeilenweise gelesen werden. Für jede Zeile muss dann ein Objekt erstellt werden, das die Daten speichert. Damit wir die Daten korrekt speichern können müssen wir die jeweilige Textzeile erst an Hand des verwendeten Trennzeichens (hier “|”) in die vier Bestandteile teilen. Die ID muss extra noch aus einer Zeichenkette in eine Zahl umgewandelt werden. Die Freundesliste ist nochmal eine weitere Zeichenkette, die wir erst an Hand des Trennzeichens (“,”) in eine Liste umwandeln und deren Elemente dann in Zahlen konvertieren müssen. Daraus kann dann das Gast-Objekt erstellt werden. Die Gast-Objekte müssen dann noch zu einer Liste zusammengefügt werden.
Damit alles gut lesbar bleibt sollte man den Code auch noch mit Kommentaren versehen. Dabei sollte jede Funktion und jede Klasse einen eigenen Kommentarblock haben, der sich an die jeweiligen Konventionen für die Quelltextdokumentation der Programmiersprache hält. Ausgenommen sind hier die so genannten Getter- und Setter-Methoden, da es deren einzige Aufgabe ist, Eigenschaften in Objekten les- oder schreibbar zu machen und sich das schon aus Namen wie getID oder setID ableiten lässt, so dass hier ein Kommentar in der Regel nicht notwendig ist. Außerdem sollten auch schwer verständliche Codeabschnitte mit Zeilenkommentaren zur Erläuterung versehen werden.
14 Languages and counting
Im oben verlinkten Repo findet ihr Beispiel-Implementationen des Party-Problems in (bisher) 14 Programmiersprachen. Die verwendeten Funktionen sind jeweils identisch, es gibt nur sprachspezifische Unterschiede, da sich die Konzepte der Sprachen zum Teil unterscheiden. Die Programme verwenden jeweils das Verzeichnis “res” als Arbeitsverzeichnis, dort liegt auch die Gästeliste.
Das Party-Problem ist bisher in folgenden Sprachen implementiert:
- C
- C++
- C#
- Dart
- Go
- Java
- JavaScript (Konsole, über Node.js)
- Kotlin
- Kotlin-Native
- PHP
- Python
- Ruby
- Rust
- TypeScript (Konsole, über Node.js)
Wenn ihr also mal wieder nach einer neuen Programmiersprache sucht, schaut doch mal ins Repo. Es ist bestimmt etwas Spannendes dabei 😉
Falls ihr Vorschläge bezüglich weiterer Programmiersprachen habt, lasst mich das gerne wissen. Sie sollte nur nicht komplett veraltet sein (Cobol ist also raus 😉 ) und Objektorientierung sollte möglich sein.
1 comments On Coding: Das Party-Problem
Pingback: Coding: Das Party-Problem - ahahn94's Blog ()