Rekursion bricht nicht ab

From	"Christian H. Kuhn" <qno-news@qno.de>
Newsgroups	de.comp.lang.java
Subject	Rekursion bricht nicht ab
Date	2016-04-08 23:28 +0200
Message-ID	<dmqm4qFkm0hU1@mid.individual.net> (permalink)

Show all headers | View raw

-----BEGIN PGP SIGNED MESSAGE-----
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:

- - Stellung gelöst? Dann Zugfolge bis hierher als Lösung zurückgeben.
- - Stellung schon mal gesehen? Dann null zurückgeben, ansonsten hash
der Stellung in Set für diesen Rekursionszweig zufügen.
- - Mögliche Zugliste generieren. Liste leer? Null zurückgeben.
- - Züge ausführen, auf neue Stellung getResult() aufrufen (die
Rekursion). Wenn erhaltenes result != null, kommt es in eine Liste
allResults.
- - Nach ausführen aller Züge: Wenn allResults leer, null zurückgeben.
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
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iQIcBAEBCAAGBQJXCCKNAAoJEGVI2lsCpSdTX6kP/3/l3+9Jt/bV8WxEJL25H1tQ
WkD0L3iuJSL5g/zIo5LzwMIUV3aviSKwJbNJe51NAxO7V68WG24HcQVhMjd0WX0O
eUcFZiCA8weqEC5636gKrGB5Z82N//fp/THDeH/TohFqe3egc8579+oXWb9mRxh6
sq1oLiKkVDDz7GViqzhbEOyX6YBR1GanZyn8XdlbVBEMEsfLzcpfr3rYPw5tsu4m
udrAExVCGFByDAo4yJ1/ll58mKc4LiYWYnTQ+qg5VSumg3YJAdbtH9zfFSrTOtUj
nuL0sSNRn2dYd7QzOLco/el2ktdQILXwLoC+EPC3MsJAKWv2S3eAzMCNdfUyMTzg
oVh/oak65aL8N2MIG5Vz2YyNsMaNtqdi55AvjO5oNxCFCArTa0F0URSmwDfl23AT
cz6msKE6amOKn83ExcObGBChi9XKoaZupBn/naVBXbwhfllcYpABmMOXf0PyoA5l
jQvgDcC5DPl0++Z5L4VcggikXwufjgXlZ8147ErBa/PMT5GAcywa09Ln/LAASWWg
0B4MQ/2AHqls841FbXmDkfYoiL9gFtOtnVQUJ035IgJcABUQtolSYZPMKRg3vVuy
f42ULLw4NfZNyyhEQkUh/0TTw3VUzuPbLrFzQpq9RymU/a0/EJmnHnD+Idnj17Xs
Y2/PUTTaAxwhMnUOyEY5
=KC/a
-----END PGP SIGNATURE-----

Back to de.comp.lang.java | Previous | Next — Next in thread | Find similar

Thread

Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-08 23:28 +0200
  Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-09 16:13 +0200
    Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-10 15:41 +0200
      Re: Rekursion bricht nicht ab Peter Büttner <not_for_mail_peb@gmx.net> - 2016-04-10 16:45 +0200
        Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-10 18:28 +0200
          Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-13 19:25 +0200
            Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-13 21:56 +0200
              Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-23 16:13 +0200
              Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-23 16:13 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-23 17:31 +0200
                Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-25 00:53 +0200
                Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-25 00:56 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-23 19:22 +0200
            Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-14 00:42 +0200
              Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-14 09:20 +0200
              Re: Rekursion bricht nicht ab Christoph Schneegans <Christoph@Schneegans.de> - 2016-04-14 18:47 +0200
              Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-23 16:13 +0200
                Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-25 12:07 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-25 17:38 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-25 22:36 +0200
                Re: Rekursion bricht nicht ab Wanja Gayk <brixomatic@yahoo.com> - 2016-04-28 08:26 +0200
      Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-10 22:15 +0200
        Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-12 15:46 +0200
          Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-12 18:32 +0200
            Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-13 20:44 +0200
              Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-14 12:07 +0200
                Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-23 13:35 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-23 14:57 +0200
                Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-25 23:05 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-26 01:16 +0200
                Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-23 16:05 +0200
                Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-25 12:48 +0200
  Re: Rekursion bricht nicht ab v_borchert@despammed.com (Volker Borchert) - 2016-04-10 06:07 +0000
  Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-10 15:40 +0200
  Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-11 11:21 +0200
    Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-12 15:57 +0200
      Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-12 18:28 +0200
        Re: Rekursion bricht nicht ab "Christian H. Kuhn" <qno-news@qno.de> - 2016-04-12 23:36 +0200
          Re: Rekursion bricht nicht ab Patrick Roemer <sangamon@netcologne.de> - 2016-04-25 21:42 +0200

csiph-web