Differences

This shows you the differences between two versions of the page.

--- lehrkraefte:blc:informatik:ffprg2-2023:aufgabe3 [2023/11/14 07:10] – [Wortbaum] Ivo Blöchliger
+++ lehrkraefte:blc:informatik:ffprg2-2023:aufgabe3 [2023/11/14 07:24] (current) – [Aufgabe 3] Ivo Blöchliger
@@ Line 1: / Line 1: @@
+====== Aufgabe 3 ======
+Gegeben ist eine Aufteilung in Regionen und die Wörter in den Regionen.
+Es soll jetzt überprüft werden, ob das Puzzle eine eindeutige Lösung hat.
+Dazu wird ein Algorithmus gesucht, der systematisch das Puzzle versucht zu lösen, indem dieser sämtliche Möglichkeiten durchprobiert. Sobald eine zweite Lösung gefunden wurde, kann der Algorithmus abgebrochen werden. Ansonsten muss er fertig laufen.
+«Alles durchprobieren» ist je nach Definition von «alles» praktisch schlicht unmöglich. Die Idee ist, möglichst früh sagen zu können, dass mit der bereits getroffenen Wahl keine Lösung möglich ist.
+Dazu verwenden wir folgende zwei Eigenschaften:
+  * Nur Wörter aus der Wortliste sind zugelassen.
+  * Die Region, die von einem Wort belegt wird, muss zusammenhängend und zwischen 4 und 8 Felder umfassen.
+<WRAP todo>
+Navigieren Sie in das Verzeichnis funkmast und «checken» Sie den «tag» a3 aus:
+<code bash>
+git fetch --all --tags
+git checkout tags/a3
+git switch -c dev
+</code>
+</WRAP>
+===== Vorschlag zur Implementation =====
+Folgende Feststellung ist zentral für den Algorithmus:
+  * Das Feld am meisten link in der obersten Zeile, die noch freie Zellen hat, ist zwingend ein Wortanfang (vorausgesetzt, die bereits platzierten Wörter sind korrekt).
+==== Wortbaum ====
+Die Idee ist, alle Wörter der Wortliste möglichst schnell und effizient durchprobieren zu können. Da jeweils der, bzw. die ersten Buchstaben gegeben sind, brauchen wir schnellen Zugriff auf alle Wörter die mit gegebenen Buchstaben beginnent. Dazu wird die Liste in einem Baum gespeichert, modelliert mit JavaScript Objects (key-value pairs).
+Jeder Knoten hat maximal 27 Einträge, 'a'-'z' und '_', um ein Wortende zu markieren.
+Die Liste ["aber", "apfel", "abend", "bla"] sieht als Baum wie folgt aus:
+<code javascript>
+{'a': {'b': {'e': {'n': {'d': {'_'}}}, 'r':{'_'}}}}, 'p':{'f':{'e':{'l':{'_'}}}}}, 'b':{'l':{'a':{'_'}}}}
+</code>
+Der Clue ist, dass einfach bei dem Unterbaum weitergearbeitet werden kann, der durch die bereits gegebenen Buchstaben erreicht werden kann. Dazu reicht es, die Referenz auf den Unterbaum zu haben, es brauchen keine weiteren Daten kopiert oder gespeichert zu werden.
+Dieser Baum muss nur einmal aus der Wortliste erstellt werden.
+==== tryNextLetter(used, curUsed, pft) ====
+Diese Funktion liefert ein Array von möglichen Wörtern, die bei der obersten, am meisten links liegenden freien Zellen starten. Ein Wort ist wie die Variable ''curUsed'' (siehe unten) codiert.
+Ist das Array leer, heisst das, dass die vorhergehende Platzierung nicht möglich ist und diese schrittweise rückgängig gemacht werden muss.
+  * ''used[x][y]'': -1 wenn frei, sonst die Nummer der Region, zu der die Zelle gehört.
+  * ''curUsed'': Ein Array von Koordinaten, z.B. ''<nowiki>[[0,0],[1,0], [0,1], [1,1]]</nowiki>'', gibt die Reihenfolge der Buchstaben mit ihren Positionen an.
+  * ''pft'': Wortbaum (der relevante Unterbaum)
+Beim ersten Aufruf wird die Funktion mit ''curUsed = <nowiki>[[x,y]]</nowiki>'' und ''pft = wortbaum[buchstabe]'' aufgerufen, wobei ''x,y'' die Koordinaten der ersten Zelle und ''buchstabe'' der entsprechende Buchstabe ist.
+Die Funktion initialisiert das Array ''found=[]'' und geht dann alle möglichen Buchstaben ''letter'' in ''pft'' durch:
+  * Ist ''letter=='_' '', ist das ein potentielles Wort. Dann erst wird mit der Funktion ''connected(curUsed)'' (siehe unten) überprüft, ob die Koordinaten in ''curUsed'' eine zusammenhängede Region darstellen. Wenn ja, wird die aktuelle Lösung dem Array ''found'' hinzugefügt.
+  * Bei einem normalen Buchstaben ''letter'' werden im Feld ab der Zelle rechts der aktuellen Position und in der Zeile darunter für alle Zellen mit diesem Buchstaben:
+    * Position zu ''curUsed'' hinzugefügt.
+    * ''tryNextLetter'' mit ''curUsed'' und ''pft[letter]'' aufrufen und erhaltene Lösungen dem Array ''found'' hinzufügen.
+    * Position wieder aus ''curUsed''entfernen.
+==== connected(coords) ====
+Diese Funktion überprüft, ob die Koordinaten im Array ''coords'' eine zusammenhängende Region bilden.
+Dabei wird wie folgt vorgegangen:
+  * ''ok[i]=false'' für alle i von 0 bis ''coords.length-1''.
+  * ''ok[0] = true'': Erste Koordinate kann erreicht werden.
+  * ''todo = [0]'': Erste Koordinate muss noch bearbeitet werden.
+  * ''okCount=1'': Anzahl erreichbare Koordinaten (wenn bei Koordinate 0 gestartet wird)
+  * Solange ''todo.length>0'':
+    * Sei ''i==todo.pop()'' (Entferne letztes Element von ''todo'' und speichere es in ''i'')
+    * Für jeden Index ''j'' von 0 bis ''coords.length-1'':
+      * Wenn ''ok[j]==false'' und Koordinaten i und j sind benachbart:
+        * ''ok[j]=true'' markiere j als erreichbar
+        * ''todo.push(j)'' und füge j der Todo-liste hinzu.
+  * ''return coords.length==okCount'' Die Region ist zusammenhängend, wenn alle Koordinaten erreicht wurden.
+==== placeNextWord(used, pft, curRegion=0) ====
+Diese Funktion ermittelt die aktuelle Startposition für das nächste mögliche Wort und platziert alle möglichen Wörter und ruft sich dabei wieder auf. Als Resultat liefert die Funktion die Anzahl Lösungen (0,1 oder 2, mehr werden nicht gesucht).
+  * ''used[x][y]'': -1 wenn frei, sonst die Nummer der Region, zu der die Zelle gehört.
+  * ''pft'': Die komplette Wortliste als Baum.
+  * ''curRegion'': Die Nummer der nächsten Region.
+Zuerst wird die Startzelle gesucht. Gibt es keine solche, ist das Puzzle voll und die Funktion gibt als Resultat 1 Lösung zurück.
+Ab der Startzelle wird für alle möglichen Wörter gesucht und in ''words'' gespeichert.
+Ist ''words'' leer, hat das Puzzle so keine Lösung und die Funktion gibt als Resultat 0 zurück.
+''numSol=0'', die Anzahl möglicher Lösungen bis jetzt.
+Sonst wird für jedes ''word'' in ''words'' folgendes gemacht:
+  * Das Wort ''word'' wird platziert und die entsprechenden Zellen ''used'' auf ''curRegion'' gesetzt.
+  * Es wird ''placeNextWord(used, pft, curRegion+1)'' aufgerufen und das Resultat zu ''numSol''hinzugezählt.
+  * Ist ''numSol>1'' wird ''numSol'' als Resultat zurückgegeben und die Funktion beendet.
+  * Die dem ''word'' entsprechenden Felder in ''used'' werden wieder auf -1 gesetzt.
+==== solve() ====
+Die Funktion erstellt den Wortbaum ''pft'', initialisiert alle ''used[x][y]'' auf -1 und ruft ''placeNextWord(used, pft)'' auf und meldet das Resultat (1 oder 2) zurück.
+Das Puzzle hat einen eindeutige Lösung wenn 1 gemolden wird. (0 ist nicht möglich, weil das Puzzle ja mit einer Lösung generiert wurde).
+===== Weitere Betrachtungen =====
+Es gibt erstaunlich wenige Wörter, die jeweils überhaupt platziert werden können (durchschnittlich unter zwei, wenn man alle Fälle weglässt, wo kein Wort platziert werden kann). Der Algorithmus funktioniert auch noch einigermassen gut bei 4x so grossen Feldern (14x24) mit einer Wortliste von 23k Wörtern.
+Darum funktioniert der hier vorgestellte Algorithmus auch. Es ist nicht klar, ob sich eine frühe Feststellung von nicht-zusammenhängenden Regionen überhaupt lohnen würde.
+Wenn es mehrere Lösungen gibt, sind es fast immer Fälle der folgenden Art:
+<code txt>
++---+---+
+| A   B |
++   +   +
+| E   R |
++---+---+
+| R   A |
++   +   +
+| B   E |
++---+---+
+oder
++---+---+
+| A   B |
++   +---+
+| E | R |
++   +   +
+| R | A |
++---+   +
+| B   E |
++---+---+
+</code>
+Vor allem bei grösseren Felder würde es sich wohl lohnen, solche Fälle zum vornherein zu finden und neue Wörter zu wählen.