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.
Wall-E
Hallo,
ich sitze jetzt seit ca. 2 Stunden über der Wall-E Aufgabe und versuche ungefähr den Code und Test zu verstehen.
Kann mir jemand hier ein wenig einen Denkanstoß geben?
Die Idee war es ähnlich wie bei KenKen über eine rekursive Funktion mit Backtracking zu machen, allerdings würde dies nach meinem Gedanken ja nur die erste mögliche Lösung (und eventuell nicht die kürzeste finden).
Was sollte ich denn in welcher Variable wie speichern, wenn ich z. B. probiere, eine DesignTile an eine Stelle zu setzen? Und bevor ich das mache überprüfen ob das überhaupt geht. Und wenn ja, dann werden ja in manchen (oder den meisten Fällen) mehrere Tiles belegt, wie speichere ich das am besten und entferne es dann wieder falls keine Lösung gefunden wurde?
Ihr habt schoneinmal richtig erkannt, dass die erste gefundene Lösung nicht immer die Beste sein muss. Sprich ihr müsst auf jeden fall immer Alle Lösungen durchgehen um festzustellen, dass ihr die optimale habt(Außer bei manchen Sonderfällen, bei denen man evtl. eine Implementierung umsetzen könnte, die schon früher erkennt, dass der optimale Algorithmus gefunden wurde, z.B. wenn Nur die größten Fliesen eingesetzt wurden und dadurch das Feld gefüllt wurde.
Ich selbst habe eine eigene Wand erstellt, auf dei ich die Fliesen setze und die ich im Rekursiven Aufruf weitergebe. Außerdem gebe ich auch die derzeitige Teillösung rekursiv weiter.
Allerdings weiß ich nicht ob das so bei euch funktionieren würde, denn ich habe etwas getrickst, damit das tatsächlich zeitlich auch funktioniert…
Nach knapp 6 Stunden Arbeit an meinem Code habe ich immer noch keine zufriedenstellende Lösung gefunden.
Ich habe eine rekursive Funktion, die EINE Lösung findet. Das ist beim Beispiel aus der Aufgabe (und dem Public Test):
R ??? ??? ??? ??? R
??? ??? ??? ??? R ???
??? ??? ??? ??? ??? ???
??? R ??? ??? ??? R
??? ??? ??? ??? ??? ???
Logischerweise ist das nicht die beste Lösung (benötigt 17 Designs).
Ich habe jetzt mehrere Möglichkeiten durchprobiert, alle Möglichkeiten durchzugehen. Allerdings bin ich bisher in den letzten 3 Stunden zu keiner Lösung gekommen… Jemand noch eine Idee?
Wenn du eine Lösung hast, dann darfst du nicht abbrechen, sondern musst weitersuchen, aber dir diese eine Lösung merken, die du schon gefudnen hast…
Findest du eine bessere, dann speicherst du diese und vernichtest die andere…
Wo genau hapert es dabei? Hapert es am Speichern oder am Finden von anderen möglichen Lösungen?
Wenn es am Speichern ahpert solltest du im Kopf behalten, dass hier keinerlei Einschränkungen, soweit ich mich nich erinnere, gegeben sein sollten, was die Struktur deiner klasser angeht. Du kannst dir also zusätzliche Klassenattribute definieren…
Sollte es daran hapern,d ass du nicht durch Alle Möglichkeiten durchiterierst, solltest du nocheinmal genauer über deinen Code nachdenken, denn damit das passiert, musst du entweder irgendwo zu früh abbrechen oder mit einer falschen Fliese anfangen…
So ähnlich hatte ich meine Ansätze quasi schon, hatte Arrays die alle bisher verwendeten Lösungen gespeichert haben. Das Problem ist ja, wie bringe ich ihn dazu weiter zu machen, ohne dass er wieder beim Selben rauskommt? Die ersten X Schritte können ja gleich sein.
Indem du Pro Rekursionstiefe einen Array verwendest…
Dann brauchst du vielleicht nichte einmal einen globalen Array.