Rekursion bricht nicht ab

08/04/2016 - 23:28 von Christian H. Kuhn | Report spam
Hash: SHA256

Hallo Gemeinde,

Die letzten paarundzwanzig Mal hat sich die Lösung beim Schreiben der
Hilfebitte gefunden, diesmal wohl nicht ...

Ich bringe mir gerade Continous Integration bei, weil ich nicht
ausschließen will, dass ich das mal beruflich brauche. Eclipse, Git,
Maven, Jenkins, verteilt auf LapTop, Tower und remote server. Ein paar
Tests mit Checkstyle, JUnit4, JaCoCo. Was genau davon sinnvoll ist,
ist diskutierbar, hier geht es eher um die Bedienung. Und um die
Technik zu testen, habe ich mir als Fingerübung einen Lösungsfinder
für das Android-Spiel Lyfoes geschrieben.

Die Vorbereitung war natürlich das aufwendigste. TDD, ein paar
Klassen, aus denen die Hauptklasse nachher zusammengesetzt wird, die
ganzen Tests, Checkstyle besteht auf javadoc, Variablennamen im
richtigen Format, dann doch einen Testfall vergessen und zu geringe
Testabdeckung (und dabei auch gelernt, warum 100% Testabdeckung nicht
immer nur Fetisch ist), und ganz zum Schluss die eigentliche Lösungssuche.

Natürlich per Rekursion. Die Lyfoes werden durch Buchstaben
repràsentiert, die Reagenzglàser durch Vector<Character>, das gesamte
Setup durch Vector<Vector<Character>>. Im Prinzip wird bei getResult()
überprüft:

der Stellung in Set für diesen Rekursionszweig zufügen.
Rekursion). Wenn erhaltenes result != null, kommt es in eine Liste
allResults.
Sonst eine kürzeste Zugfolge aus allResults zurückgeben.

Klappt in einigen einfachen Testfàllen. Klappt insbesondere dann, wenn
in der Startposition nur ein leeres Reagenzglas als Puffer fürs
Umsortieren ist. Sobald da zwei sind, bricht die Rekursion nicht mehr ab.

Ich sehe zwei Möglichkeiten: Entweder habe ich eine Abbruchbedingung
übersehen. Ich finde aber keine weitere. Oder die hashCode-Funktion
für die Stellungen taugt nix. Den Verdacht hatte ich eh, aber eher in
die andere Richtung: dass ich für eine neue Stellung den gleichen hash
habe wie für eine bisherige und deshalb Lösungen nicht finde. Ideal
wàre eine bijektive hash-Funktion, die aber den Zahlenraum int nicht
sprengt ...

Aufgrund dieser allgemeinen Beschreibung wird mir niemand helfen
können. Der Quellcode ist hier: https://www.qno.de/lyfoesolver.zip
steht unter keiner Lizenz (jedenfalls wüsste ich nichts), lachen ist
erlaubt ;-) (ebenfalls zu Lernzwecken habe ich alles Mögliche und
vermutlich manches mehr mit Exceptions geregelt). Für Hinweise, wo
genau ich mich wie dàmlich angestellt habe, bin ich dankbar.

TIA
QNo
 

Lesen sie die antworten

#1 Patrick Roemer
09/04/2016 - 16:13 | Warnen spam
Responding to Christian H. Kuhn:
Klappt in einigen einfachen Testfàllen. Klappt insbesondere dann, wenn
in der Startposition nur ein leeres Reagenzglas als Puffer fürs
Umsortieren ist. Sobald da zwei sind, bricht die Rekursion nicht mehr ab.



Geh das kleinstmögliche Szenario, bei dem das Verhalten auftritt, mal
mit Papier und Stift von Hand durch. Dann lass in Deinem Programm in
jedem Rekursionsschritt den Spielzustand ausgeben (oder steppe im
Debugger durch) und vergleiche mit Deinen Erwartungen. Oft findet man so
schon raus, wo es hakt.

Aufgrund dieser allgemeinen Beschreibung wird mir niemand helfen
können. Der Quellcode ist hier: https://www.qno.de/lyfoesolver.zip



Es wird wohl schwierig, anhand dieses Codes hier Hilfe zu finden - schon
alleine, weil man ja erst mal verstehen müsste, worum es bei dem Spiel
überhaupt geht. :)

Zumindest wàre es sinnvoll, ein paar funktionierende Testfàlle
beizulegen, und einen, der das Problem demonstriert.

Viele Grüße,
Patrick

Ähnliche fragen