Hi,
Ich bin über das Rätsel (ein Geocache) gestolpert (anhang)
Inspiriert von Yalus Lösung des Damenproblem
(Beitrag "Re: Algorithmus für 5x5 Puzzle (Geduldspiel) gesucht"), dachte ich, ich
probiers auch mal mit Haskell.
Das schema schien sich ja leicht anpassen zu lassen.
Aber irgendwie will es nicht und die Compilerfehlermeldung versteh ich
auch überhaupt nicht.
der Compiler:
https://ideone.com/U6llza
vielleicht kann mir ja jemand auf die Sprünge helfen.
1
(z1,s1) </> (z2,s2) = -- Der </>-Operator liefert genau dann "Wahr", wenn sich (z1,s1) und (z2,s2) nicht bedrohen, d.h.
2
( abs(s1 - s2) > 1 -- min 1 feld zwischen 2 Bällen
3
|| abs(z1 - z2) > 1)
4
5
6
loesungen = do
7
f1 <- [(1,9) ]
8
f2 <- [(2,4) ]
9
f3 <- [(3,11)]
10
f5 <- [(5,15)]
11
12
-- erste zeile
13
b1_1 <- [ (z,s) | z <- 1, s <- [1..15],
14
(z,s) </> f1,
15
(z,s) </> f2 ] --
16
17
b1_2 <- [ (z,s) | z <- 1, s <- [1..15],
18
(z,s) > b1_1,
19
(z,s) </> f1,
20
(z,s) </> f2,
21
(z,s) </> b1_1 ] --
22
23
-- zweiten Zeile
24
b2_1 <- [ (z,s) | z <- 2, s <- [1..15],
25
(z,s) </> f1,
26
(z,s) </> f2,
27
(z,s) </> f3,
28
(z,s) </> b1_1,
29
(z,s) </> b1_2,
30
(z,s) /= (2,14) ] --
31
32
b2_2 <- [ (z,s) | z <- 2, s <- [1..15],
33
(z,s) > b2_1,
34
(z,s) </> f1,
35
(z,s) </> f2,
36
(z,s) </> f3,
37
(z,s) </> b1_1,
38
(z,s) </> b1_2,
39
(z,s) </> b2_1,
40
(z,s) /= (2,14) ] --
41
42
--dritte zeile
43
b3_1 <- [ (z,s) | z <- 3, s <- [1..15],
44
(z,s) </> f2,
45
(z,s) </> f3,
46
(z,s) </> b2_1,
47
(z,s) </> b2_2 ] --
48
49
b3_2 <- [ (z,s) | z <- 3, s <- [1..15],
50
(z,s) > b3_1,
51
(z,s) </> f2,
52
(z,s) </> f3,
53
(z,s) </> b2_1,
54
(z,s) </> b2_2,
55
(z,s) </> b3_1 ] --
56
57
-- vierte Zeile
58
b4_1 <- [ (z,s) | z <- 4, s <- [1..15],
59
(z,s) </> f3,
60
(z,s) </> f5,
61
(z,s) </> b3_1,
62
(z,s) </> b3_2 ] --
63
64
b4_2 <- [ (z,s) | z <- 4, s <- [1..15],
65
(z,s) > b4_1,
66
(z,s) </> f3,
67
(z,s) </> f5,
68
(z,s) </> b3_1,
69
(z,s) </> b3_2,
70
(z,s) </> b4_1 ] --
71
72
b4_3 <- [ (z,s) | z <- 4, s <- [1..15],
73
(z,s) > b4_2,
74
(z,s) </> f3,
75
(z,s) </> f5,
76
(z,s) </> b3_1,
77
(z,s) </> b3_2,
78
(z,s) </> b4_1,
79
(z,s) </> b4_2 ] --
80
81
-- fünfte zeile
82
b5_1 <- [ (z,s) | z <- 3, s <- [1..15],
83
(z,s) </> f5,
84
(z,s) </> b4_1,
85
(z,s) </> b4_2,
86
(z,s) </> b4_3,
87
(z,s) /= (5,6) ] --
88
89
b5_2 <- [ (z,s) | z <- 3, s <- [1..15],
90
(z,s) > b5_1,
91
(z,s) </> f5,
92
(z,s) </> b4_1,
93
(z,s) </> b4_2,
94
(z,s) </> b4_3,
95
(z,s) </> b5_1,
96
(z,s) /= (5,6) ] --
97
98
return (b1_1, b1_2, f1, b2_1, b2_2, f2, b3_1, b3_2, f3, b4_1, b4_2, b4_3, b5_1, b5_2, f5) -- Das ist ein Lösungstupel, für das alle obigen Bedingungen erfüllt sind.
99
100
101
main = mapM_ print loesungen -- Ausgabe der Lösungen in der Form
Vlad Tepesch schrieb:> Inspiriert von Yalus Lösung des Damenproblem> (Beitrag "Re: Algorithmus für 5x5 Puzzle (Geduldspiel) gesucht"),> dachte ich, ich probiers auch mal mit Haskell.
Dabei bist du leider auf ein paar Schwächen des dortigen Codes gestoßen,
die dessen leichteren Verständlichkeit geschuldet sind. Deswegen schrieb
ich dort auch:
> Anmerkung: Damit der Code ohne große Haskell-Kenntnisse verständlich> ist, ist er sehr geradlinig gehalten, enthält deswegen absichtlich viel> Copy/Paste und ist auf eine feste Zahl von Feldern (8×8) beschränkt. Die> Zusammenfassung der Copy/Paste-Teile würde den Code kompakter und> universeller machen, gleichzeitig aber Wissen über ein paar spezielle> Haskell-Funktionen voraussetzen.Vlad Tepesch schrieb:> Aber irgendwie will es nicht und die Compilerfehlermeldung versteh ich> auch überhaupt nicht.
Da ist einfach nur ein Typfehler ;-)
Ich habe in dem Programm sämtliche Deklarationen weggelassen und es dem
Compiler überlassen, die Typen der einzelnen Variablen und Funktionen
herauszufinden, was er immerhin auch geschafft hat.
Ist das Programm aber fehlerhaft, so dass der Compiler keine konsistente
Typisierung aller Variablen finden kann, ist die Lokalisierung des
Fehlers i.Allg. mehrdeutig, und es erscheinen schwer interpretierbare
Fehlermeldungen (der eine oder andere kennt sicher ein ähnliches
Phänomen bei der Template-Programmierung in C++ ;-)). Deswegen ist es
üblich, zumindest alle Top-Level-Funktionen mit Deklarationen zu
versehen, die dem Compiler eine viel genauere Eingrenzung des Fehlers
ermöglichen.
In diesem Fall hätte man sinnvollerweise die Funktionen (</>),
loesungen und main deklariert. Die Deklaration von loesungen
lautet
weil es sich dabei um eine Liste (eckige Klammewrn) von Lösungen
handelt, wobei jede Lösung ein 15-Tupel (äußere runde Klammern) ist,
dessen 15 Elemente wiederum 2-Tupel (innere runde Klammern) aus zwei
Int-Zahlen (Zeilen- und Spaltennummer) sind. Schreibt man diese
Deklaration vor die eigentliche Definition von loesungen, so
reduzieren sich die ellenlangen Fehlermeldungen auf
1
prog.hs:16:26:
2
No instance for (Num [Int]) arising from the literal ‘1’
3
In the expression: 1
4
In a stmt of a list comprehension: z <- 1
5
In a stmt of a 'do' block:
6
b1_1 <- [(z, s) |
7
z <- 1, s <- [1 .. 15], (z, s) </> f1, (z, s) </> f2]
Jetzt zeigt der Compiler auf die richtige Stelle, nämlich die '1' in
z <- 1. Er erwartet nämlich rechts vom Pfeil eine Liste von Ints, findet
aber nur ein Integer-Literal. Um dieses als Int-Liste ([Int]) zu
interpretieren, müsste diese der Typklasse der Zahlen (Num) angehören,
was aber in diesem Programm nicht der Fall ist.
Kurz: Es sollte hier nicht z <- 1, sondern z <- [1] heißen. Der gleiche
Fehler kommt noch ein paarmal vor.
Nachdem diese Fehler korrigiert sind, kompiliert das Programm zwar, gibt
aber viel zu viele Lösungen aus, weil nicht verhindert wird, dass
mehrere Fußbälle in der gleichen Spalte liegen.
Du kannst die zusätzlichen Abfragen noch einbauen, allerdings wird sich
der Code dadurch immer mehr aufblähen. Schon mein Beispiel für das
8-Damen-Problem enthielt sehr viel Copy-Paste-Code, was nicht schick
aussieht und gerade in Haskell ziemlich verpönt ist.
So enthält folgender Code-Ausschnitt 7 fast identische Berechnungen:
1
d8 <- [ (z,s) | z <- [1..8], s <- [1..8],
2
(z,s) > d7,
3
(z,s) </> d1,
4
(z,s) </> d2,
5
(z,s) </> d3,
6
(z,s) </> d4,
7
(z,s) </> d5,
8
(z,s) </> d6,
9
(z,s) </> d7 ]
Zudem taucht der gesamte Block in ähnlicher Form noch siebenmal auf.
Solche Dinge würde man in einer imperativen Programmiersprache in
Schleifen zusammenfassen, in der funktionalen Programmierung gibt es als
Schleifenersatz verschiedene Funktionen höherer Ordnung, insbesondere
die so genannten Folds.
Die zusammengefasste Variante (inkl. der Funktionsdeklarationen) sieht
dann so aus:
1
import Control.Monad
2
3
(</>) :: (Int,Int) -> (Int,Int) -> Bool
4
(z1,s1) </> (z2,s2) =
5
z1 /= z2
6
&& s1 /= s2
7
&& abs (z2 - z1) /= abs (s2 - s1)
8
9
loesungen :: Int -> [[(Int,Int)]]
10
loesungen n = foldM moeglicheBelegungen [] [1..n]
11
where moeglicheBelegungen belegung _ =
12
[ (z,s) : belegung | z <- [1..n], s <- [1..n],
13
null belegung || (z,s) > head belegung,
14
all ((z,s) </>) belegung ]
15
16
main :: IO ()
17
main = mapM_ print (loesungen 8)
Der Code ist nicht nur wesentlich kürzer, sondern auch allgemeiner
geworden, denn loesungen hat jetzt die Kantenlänge n des Schachbretts
als Argument.
Der obige Code-Block aus dem ursprünglichen Programm steckt nun in der
Funktion moeglicheBelegungen, der die bisherige Belegung d1, d2, d3
... di in umgekehrter Reihenfolge als Liste belegung = [di ... d1]
übergeben wird.
Die Prüfung (z,s) > di lautet jetzt
1
null belegung || (z,s) > head belegung,
d.h. (z,s) wird mit dem ersten Element (di) der Liste belegung
verglichen, aber nur dann, wenn diese nicht leer ist.
Die lange Kette von </>-Operationen, deren linker Operand immer (z,s)
und deren rechter Operand der Reihe nach d1, d2 usw. ist, kann
folgendermaßen zusammengefasst werden
1
all ((z,s) </>) belegung
Die Funktion all wendet dabei die Funktion ((z,s) </>) (oder
ausführlicher: die Funktion f x = (z,s) </> x ) nacheinander auf alle
Elemente von belegung an und bildet die Und-Verknüpfung der
Funktionswerte. Das Ergebis ist True, wenn die aktuelle Dame von keiner
der bereits platzierten bedroht wird.
Der Funktionswert von moeglicheBelegungen ist eine Liste aller
möglichen Belegungen, die aus den Elementen von belegungen durch
Hinzufügen einer weiteren Dame entstehen. Dieses Hinzufügen an den
Anfang der Liste geschieht durch den Doppelpunkt in (z,s) : belegung.
Unter Verwendung der Funktion moeglicheBelegungen kann man jetzt für
n=8 den Lösungsalgorithmus folgendermaßen schreiben:
loesungen8 = do
b1 <- moeglicheBelegungen []
b2 <- moeglicheBelegungen b1
b3 <- moeglicheBelegungen b2
b4 <- moeglicheBelegungen b3
b5 <- moeglicheBelegungen b4
b6 <- moeglicheBelegungen b5
b7 <- moeglicheBelegungen b6
b8 <- moeglicheBelegungen b7
return b8
Konstrukte dieser Art lassen sich mit foldM zusammenfassen:
1
loesungen n = foldM moeglicheBelegungen [] [1..n]
Da die an foldM übergebene Funktion mit zwei Argumenten aufgerufen
wird, von denen das zweite aber hier nicht benötigt wird, wird in der
Definition von moeglicheBelegungen als zweiter Arguementname einfach
das Dummy-Symbol '_' verwendet:
1
moeglicheBelegungen belegung _ = ...
Vielleicht gelingt es dir ja, nach diesem Schema ein ähnlich knackiges
Programm für das Fußballproblem schreiben. Wenn nicht, kann ich heute
Abend gerne selber eins posten.
Aber eigentlich ist das Rätsel viel zu schade dafür, mit dem Computer
gelöst zu werden. Ein kleines Stück Papier, ein Bleistift, etwas Logik
und etwa 5 Minuten Zeit sind völlig ausreichend. Man braucht nicht
einmal einen Radiergummi als Backtracking-Instrument.
danke, mit den Hinweisen bezüglich der Fehler, war das Programm einfach
zum laufen zu bringen und eine Lösung zu erhalten.
Mit dem Erstellen der Kurzversion ohne copy/paste tue ich mich aber
schwer. mal sehen, vielleicht juckt es mich in den nächsten Tagen mal
und ich arbeite ein paar Tutorials durch ;) An einigen Ecken fehlt da
noch das Grundverständnis.
Thread beobachten
Seitenaufteilung abschalten