Path: csiph.com!news.mixmin.net!newsreader4.netcologne.de!news.netcologne.de!.POSTED!not-for-mail
From: Patrick Roemer <sangamon@netcologne.de>
Newsgroups: de.comp.lang.java
Subject: Re: Rekursion bricht nicht ab
Date: Mon, 11 Apr 2016 11:21:00 +0200
Organization: news.netcologne.de
Lines: 27
Distribution: world
Message-ID: <nefq9s$ofr$1@newsreader4.netcologne.de>
References: <dmqm4qFkm0hU1@mid.individual.net>
NNTP-Posting-Host: xdsl-213-196-254-224.netcologne.de
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
X-Trace: newsreader4.netcologne.de 1460366460 25083 213.196.254.224 (11 Apr 2016 09:21:00 GMT)
X-Complaints-To: abuse@netcologne.de
NNTP-Posting-Date: Mon, 11 Apr 2016 09:21:00 +0000 (UTC)
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.24) Gecko/20100411 Thunderbird/2.0.0.24 Mnenhy/0.7.6.0
X-Mozilla-News-Host: news://news.netcologne.de
In-Reply-To: <dmqm4qFkm0hU1@mid.individual.net>
Xref: csiph.com de.comp.lang.java:12926

Responding to Christian H. Kuhn:
> 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 ...

Ich habe mir gerade spasseshalber mal das Demovideo für das Spielchen
angeschaut. Wenn ich mich nicht verzählt habe, bringen die da ein
Beispiel mit 15 Gläsern zu je 4 "Bewohnern" und 10 Farben. Ich bin nicht
fit genug in Stochastik, um da ad hoc eine sinnvolle Obergrenze für
auszurechnen, aber vom Bauchgefühl her: Kannst Du knicken.

Ich vermute mal, dass Du eh eine Art Breitensuche machen müssen wirst.
Da hast Du zwangsweise schon größere Mengen an Kandidatenzuständen im
Speicher. Ich würde die "bereits gesehenen" Zustände in einem echten
HashSet halten (natürlich mit sinnvoller #hashCode-Implementierung, aber
eben mit #equals-Vergleich bei Übereinstimmung), und Optimierungsenergie
lieber erst mal darauf verwenden, den Suchraum zu minimieren.

Code sollte zunächst mal korrekt sein, und dann erst performant. Wenn Du
Gefahr läufst, eine Lösung nicht zu finden, weil es in einer Sackgasse
vorher mal den selben Hashcode gab, läuft was schief.

Viele Grüße,
Patrick