Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
7.4. Backtrack Gitterraetsel
Hey,
Zwei kurze Fragen: Koennen wir davon ausgehen, dass die Woerter nur Gross-/Kleinbuchstaben haben und, falls nicht, muessen wir hierbei unterscheiden?
bei Teilaufgabe a) 6.: Es sollen nur gridSpecs, bei denen die Einzelnen Woerter sich ueberlagern fehlerhaft sein, oder? D.h ein Wort kann bspw. direkt vor dem naechsten aufhoeren:
{{0,0,2,0} {0,2,3,0}} waere demnach korrekt. Genauso duerfen sie auch parallel direkt neben einander verlaufen (zB.: {0,0,3,0}{1,0,3,0})
E: Oder weiß jemand, warum das Est noch nen Ausrufezeichen anzeigen koennte, wenn mein Output identisch zu dem Output der AuD seite ist? (diff gibt mir keine Meldung)
Vielleicht wird irgendwie auf die Laufzeit getestet und es benötigt zu lange? Sonst keine Ahnung.
Koennte sein, ich brauche momentan ca 700 ms.
E: Whoops hab ein Array ausversehen jedes mal kopiert 
Hab jetzt auf faui00a (faui05d ist nicht erreichbar) 390ms, aber Est zeigt immer noch einen Fehler an.
glaub es soll unter 300 ms liegen.
Vielleicht, naja wie auch immer, hab heute festgestellt, dass meine ~400ms nur durch ein falsches Ergebnis zustande gekommen sind (die Puzzle wurden nicht mehr geloest und mir ists nicht mal aufgefallen :D) Ich haeng jetzt bei 600ms lokal und zwischen 700-800ms auf faui00a. Falls jemand bestaetigen kann, dass das Ausrufezeichen durch einer zu langsamen Ausfuehrung verursacht werden koennte, bitte Bescheid geben.
Hier sind noch meine Tests:
https://www.dropbox.com/s/gw0xll8pd65vzcr/CrosswordPuzzleSolverTest.java?dl=0
Hallo,
ich hab mal eine Frage zur Teilaufgabe e). Hier steht ja:
Nun gibt es ja zwei allgemeine Fälle, warum das Lösen scheitert:
- Funktion evaluateSpec schlägt Alarm oder
- Puzzle ist zwar laut a) theoretisch lösbar, aber in e) merkt man dass es doch nicht lösbar ist.
Ist es nun bei e) erlaubt/gewollt/erwünscht im Fall:
- char grid = new {{}};
- das entsprechende Grid mit theoretisch benötigter Höhe und Breite
zurückzugeben?
Ich kann bestätigen, dass das Ausrufezeichen auch durch eine zu langsame Ausführung verursacht werden könnte.
Tipp: Die allerletzte Seite des Übungsblattes genau lesen und befolgen…
Kann/sollte es nicht geben, denn schlägt [m]evaluateSpec[/m] Alarm, wird eine Lösung gar nicht erst versucht (und wenn, dann wurde der Solver nicht spezifikationsgemäß verwendet):
if (0 == evaluateSpec) {Wow danke JohnDoe.
Ich hatte es genau andersrum gemacht 
Hat meine Zeit glatt gedrittelt und bekomme auch einen Haken, also ja, das war der Grund.
Nur ich verstehe nicht ganz, warum das jetzt so viel schneller laeuft? Liegt das nur an der Reihenfolge der Eintraege oder gibts nen anderen Grund?
Ah okay, ich hab jetzt grad mal in die Example Datei geschaut und da wird schon vor dem Aufruf des solvePuzzle gecheckt, ob das Rätsel theoretisch gelöst werden kann. Das war mir nicht bewusst, das man das nicht selbst nochmal in solvePuzzle checken soll.
Vielen Dank für die Antwort!
Hey,
Ich hätte einfach mal ne allgemeine Verständnisfrage zur e):
“Hinweis zur letzten Teilaufgabe: Überlegen Sie sich zuerst das konstruktive Induktionsprinzip und
führen Sie dabei die „Induktion in der ersten Dimension“ über gridSpec und erst in der „zweiten
Dimension“ über wordsSpec”
Welche Dimension ist denn damit gemeint? Die von Grid oder von GridSpec?
Ich habe mir das Grundgerüst von Backtracking in den Übungsfolien auch angeschaut, aber kann es nicht richtig auf die Aufgabe interpretieren.
Wie gehe ich denn als erstes vor? Nehme ich mir das erste Wort aus wordspace und überprüfe einfach, an welcher Stelle es passen könnte? Oder nehme ich mir die erste Stelle von Gridspace heraus und schaue, welche passenden Wörter es dazu gibt?
Gegen Ende der Methode muss ich ja auch irgendwann mal ein Gitter erzeugen, welches zurückgegeben werden muss, oder? Aber wie kann ich davor Methoden wie setWord ausführen, wenn ich noch garkein zugehöriges Gitter dafür habe? Wenn ich es mitten in der Rekursion erstelle, bekomme ich einen Stackoverflow (ist ja auch irgendwie verständlich, wenn ich das Gitter etliche Male neu erzeuge)
Ich glaube, momentan hapert es bei mir einfach am Verständnis… das Grundgerüst hat mich mehr verwirrt, als mir für die Aufgabenstellung geholfen.
Ich hoffe es findet sich jemand nettes, der mir kurz die Fragen beantworten könnte 
Dankeschön im Voraus!
Edit: Vielen Dank für eure Tipps ihr habt mir voll auf die Sprünge geholfen :))!
Oh man, so ein Tunnelblick ist doch immer mal was tolles.
Hab es jetzt auch geschafft!
Ich denke mal ich verrate nicht besonders viel, wenn ich so die Worte “private Hilfsfunktion(en)” (mit selbstgewaehlten Paramentern) in den Raum verwerfe…
Deine andere Frage kann ich dir jetzt nicht wirklich beantworten, da ich sonst die ganze Aufgabe spoilern wuerde. Aber: Du kannst dich an den Folien halten, funktioniert fast genauso und 2. beide Wege fuehren nach Rom, nur der eine zu Fuss und der andere mit dem Flugzeug :p. Letztendlich sagt die der Hinweis, welcher Weg schneller ist, aber du kannsts auch einfach ausprobieren.
Am Beispiel Sudoku mit Induktion in der ersten Dimension über (x,y) und in der zweiten über {1,…,9}:
- Dimension (=Rekursiver Aufruf) pro Aufruf wird ein Feld (x,y) im Sudoku gefüllt
- Dimension (=Schleife) in jedem Aufruf werden alle Zahlen {1,…,9} durchprobiert
@ Vany - als ich vor 1 Jahr AUD gehört habe, habe ich mit dem Grid-Riddle auch meine Probleme gehabt.
Ich hatte jedoch die komplette Basis falsch.
Hier noch ein Tipp (auch wenn ich nicht garantieren kann, dass das hilft):
Damit der Rekursive Abstieg funktioniert musst du so ziemlich die komplette Berechnung in deiner Hilfsfunktion ausführen
=> Das was du in den Folien wieder findest kommt eigentlich fast komplett in die Hilfsfunktion rein.
in der Hauptfunktion macht man dann nicht besonders viel, außer einen Grid kreieren, das riddle zu checken und deine Hilfsfunktion aufzurufen.
Ich habe das ganze nun iterativ gelöst, dazu benötigt es keine Hilfsfunktion;)
Steht ja nirgends, dass wir das ganze rekursiv lösen müssen.
Ich wuerde also gerne hier noch ein Antwort zu bereits gestellter Frage erfahren 
Denn nach meinem Verstaendnis ist bei so nem Gitterraetsel immer ein Leerfeld zwischen den Wortfeldern.
EDIT: Oder muss ich die Aufgabenstellung
so verstehen, dass also Laenge 5 gueltig ist, und somit auch keine Leerfelder zwischen Wortfeldern existieren muessen?
Ich habs zumindest genau so interpretiert.
Ich hab nochmal 4 neue Testfaelle hinzugefuegt, um zu ueberpruefen, ob ein Wort mehrmals verwendet wurde.
Zur b): Muss ich da auch irgendwie die eventuell “leeren” Felder zwischen den Wörtern mitbeachten? Oder kann ich die einfach ignorieren?
Ich weiß nicht, welche Leerfelder ihr genau meint …
Bezieht ihr euch auf die Ausgabe auf der Konsole? Mit der hat euer Programm nichts zu tun. Wenn in gridSpec steht, dass das Wort die Länge 5 hat, dann sind das auch 5 Buchstaben. Ohne irgendwelche Leerzeichen.
Hilft das?