Adventskalender 21. Dezember 2023 - Logische Programmierung

[paedubucher]

Logische Programmierung

Ein Logical ist ein Rätsel, bei dem aus einer textuellen Problembeschreibung durch logisches Schliessen eine Lösung zu finden ist. Mithilfe von Tabellen, mehr oder weniger formalen Notizen und durch das Ausschlussverfahren lassen sich diese Rätsel lösen; je nach Umfang (Anzahl der relevanten Informationen) mehr oder weniger gut. Zuverlässig und effizient lassen sich Logicals mit einer logischen Programmiersprache wie Prolog lösen. Deren Gebrauch soll anhand eines konkreten Rätsels demonstriert werden. Als Implementierung wird swi-prolog verwendet:

Code: Alles auswählen

# apt install -y swi-prolog

Rätsel (Original)

Das folgende Rätsel ist dem Buch Logicals für Erwachsene: von leicht bis teuflisch schwer (ISBN-13: 979-8361812943) entnommen (Originaltext in Kursiv wiedergegeben):

Die Transsibirische Eisenbahn ist mit ihren 9.288 Kilometern die längste Eisenbahnstrecke der Welt. Seit 1916 verbindet sie Moskau mit Wladiwostok (an der Pazifikküste, gegenüber von Japan). Eva reist mit der Transsibirischen Eisenbahn in Richtung Osten. Ihr Zug hat soeben die Stadt Jekaterinburg verlassen. Finden Sie heraus, in welchen Städten der Zug als nächstes halten wird und wie viele Einwohner dort leben.

1. Krasnojarsk ist nicht die Stadt mit der höchsten Einwohnerzahl.
2. Die vierte Station ist eine Stadt mit 1.090.811 Einwohnern.
3. Die zweite Haltestelle ist Omsk.
4. Die dritte Haltestelle befindet sich nicht in der Stadt mit weniger als einer Million Einwohner.
5. Die Haltestelle unmittelbar nach Tjumen ist in der Stadt mit einer Einwohnerzahl von 1.172.070.

Es ist auch eine Tabelle vorgedruckt, welche die folgenden Informationen beinhaltet:

Städte:

• Krasnojarsk
• Novosibirsk
• Omsk
• Tjumen

Einwohnerzahlen:

• 768.358
• 1.090.811
• 1.172.070
• 1.612.833

Prolog

Prolog basiert auf zweierlei Arten von Prädikaten: Fakten und Regeln. Die oben genannten Städtenamen und Einwohnerzahlen sind Fakten. Die als fünf Punkte geschilderten Bedingungen sind Regeln.

Fakten

Fakten können folgendermassen definiert werden:

Code: Alles auswählen

city(krasnojarsk).
city(novosibirsk).
city(omsk).
city(tjumen).

population(768358).
population(1090811).
population(1172070).
population(1612833).

Hier gibt es zweierlei Prädikate mit den Namen city und population. Die Städtenamen müssen als sogenannte Atome kleingeschrieben werden. Jeder Fakt wird mit einem Punkt terminiert.

Regeln

Die Beziehung zwischen einer Stadt und einer Bevölkerungszahl kann als Regel codiert werden:

Code: Alles auswählen

has_population(City, Population) :-
    city(City),
    population(Population).

Hierbei ist has_population erneut ein Prädikat, das aber nicht auf Atomen sondern auf Variablen basiert (City, Population). Variablen können verschiedene Werte annehmen. Der Regelblock wird mit dem Operator :- eingeleitet. Mehrere Regeln werden mit dem Konjunktionsoperator , (logisches Und) miteinander verbunden und mit einem Punkt terminiert.

Die Regel besagt, dass einerseits City einen der Werte annehmen kann, der mit dem city-Prädikat definiert worden ist, und andererseits, dass analog dazu Population einen mit population definierten Wert annehmen muss. Bei Prolog gilt die sogenannte Closed World Assumption: Sachen, die nicht definiert worden sind, existieren nicht. So gibt es im Universum unseres Rätsels nur gerade vier Städte und vier Einwohnerzahlen.

Eine Regel das Rätsel zu lösen

Das eingangs gestellte Rätsel kann mit einer grossen, zusammengesetzten Regel gelöst werden. Zunächst muss man sich überlegen, welche Informationen man erhalten will: Es sind die Stationen; nennen wir sie A, B, C und D, sowie deren Bevölkerungszahlen PA, PB, PC und PD (P steht für Population). Die entsprechende Regel wird folgendermassen eingeleitet:

Code: Alles auswählen

stations(A, PA, B, PB, C, PC, D, PD) :-

Im Gegensatz zu strukturierten Programmiersprachen können die Variablen zu Beginn unbelegt sein und erst bei der Ausführung mit passenden Werten besetzt werden, sodass die Aussagen über die Variablen mit den möglichen Werten übereinstimmen. Hierbei ist es möglich, dass es mehrere Lösungen gibt, die Prolog auch berechnet und zurückgibt.

Was ist über diese Variablen bekannt? Zunächst einmal bezeichnen A, B, C und D alles Städte; PA, PB, PC, PD bezeichnen deren Bevölkerungszahl:

Code: Alles auswählen

city(A),
city(B),
city(C),
city(D),

population(PA),
population(PB),
population(PC),
population(PD),

Einzigartige Elemente

Weiter muss es sich um vier unterschiedliche Städte handeln. Hierzu wird eine neue Regel namens unique ausprogrammiert:

Code: Alles auswählen

unique([]).
unique([_]).
unique([H|T]) :-
    \+ contains(T, H),
    unique(T).

Die Regel, die aus drei Klauseln besteht, liest sich folgendermassen:

1. Die Elemente einer leeren Liste [] sind einzigartig.
2. Das Element einer Liste bestehend aus einem Element [_] ist einzigartig.
3. Die Elemente einer Liste bestehend aus einem Kopf (head: h) und einem Rest (tail: t) sind einzigartig, wenn…
   1. der Rest den Kopf nicht enthält (\+ ist der Negationsoperator) und
   2. die Elemente vom Rest auch einzigartig sind.

Die Regel contains, die prüft, ob eine Liste ein Element enthält, wurde folgendermassen definiert:

Code: Alles auswählen

contains([], _) :- false.
contains([H|_], H).
contains([_|T], X) :- contains(T, X).

Diese Regel besteht aus drei Klauseln:

1. Eine leere Liste enthält kein beliebiges Element.
2. Eine Liste mit dem ersten Element H enthält dieses Element H.
3. Eine Liste mit einem beliebigen ersten Element enthält das Element X, falls dieses im Rest enthalten ist.

Mit diesen Regeln wird der Listenkopf solange mit dem gesuchten Element verglichen, bis er entweder gefunden wird oder alle Elemente der Liste erfolglos mit ihm verglichen worden sind.

Die beiden Regeln unique/1 und contains/2 sollen nun isoliert getestet werden (utils.pl):

Code: Alles auswählen

unique([]).
unique([_]).
unique([H|T]) :-
    \+ contains(T, H),
    unique(T).

contains([], _) :- false.
contains([H|_], H).
contains([_|T], X) :- contains(T, X).

Die Regeln lassen sich folgendermassen in SWI-Prolog einlesen und ausprobieren:

Code: Alles auswählen

$ swipl utils.pl
?- contains([1,2,3,4,5],3).
true .

?- contains([1,2,3,4,5],6).
false.

?- unique([1,2,3,4,5]).
true .

?- unique([1,2,3,4,5,1]).
false.

So lässt sich die Definition von stations erweitern:

Code: Alles auswählen

stations(A, PA, B, PB, C, PC, D, PD) :-
    city(A),
    city(B),
    city(C),
    city(D),
    unique([A, B, C, D]),

    population(PA),
    population(PB),
    population(PC),
    population(PD),
    unique([PA, PB, PC, PD]).

Mit dieser Regel wird eine Vielzahl von Lösungen gefunden. Diese Menge muss nun reduziert werden.

Nachdem die Grundstruktur des Problems beschrieben worden ist, sollen nun die eigentlichen Regeln des Rätsels verarbeitet werden.

Erste Regel

Die erste Regel besagt: Krasnojarsk ist nicht die Stadt mit der höchsten Einwohnerzahl. Diese Regel liesse sich allgemein ausdrücken, indem die höchste aller Einwohnerzahlen mit einem Prädikat wie max/1 ermittelt werden würde. Man kann es sich aber auch einfach machen, da die Bevölkerungszahlen schon im Voraus bekannt sind.

Der intuitive Ansatz scheitert jedoch:

Code: Alles auswählen

not(has_population(krasnojarsk, 1612833)),

Dies ist der Closed World Assumption von Prolog geschuldet:

Ein Prädikat not(predicate(X)) bedeutet: Existiert kein X, wofür predicate/1 gilt (universelle Quantifikation)? Und nicht: Existiert ein X, wofür predicate/1 nicht gilt (existenzielle Quantifikation)?

Die Regel lässt sich jedoch so formulieren, dass eine der anderen drei Städte diese höchste Bevölkerungszahl haben muss:

Code: Alles auswählen

(
    has_population(novosibirsk, 1612833);
    has_population(omsk, 1612833);
    has_population(tjumen, 1612833)
),

Diese Regel besteht aus drei Unterregel, die mit dem Oder-Operator ; verkettet werden. Die Gesamtregel ist wiederum mit dem Und-Operator , mit den restlichen Regeln verbunden.

Zweite, dritte und vierte Regel

Die zweite Regel besagt: Die vierte Station ist eine Stadt mit 1.090.811 Einwohnern.

Die vierte Stadt D muss die angegebene Einwohnerzahl haben:

Code: Alles auswählen

has_population(D, 1090811),

Die dritte Regel besagt: Die zweite Haltestelle ist Omsk.

Code: Alles auswählen

B = omsk,

Die vierte Regel besagt: Die dritte Haltestelle befindet sich nicht in der Stadt mit weniger als einer Million Einwohner.

Da es nur eine Bevölkerungszahl unter der Million gibt, lässt sich auch diese Regel anhand einer vorgegebenen Zahl formulieren. Die Negation erfordert aber wieder eine mit dem Oder-Operator verkettete Unterregel, bei der die dritte Stadt C nicht als eine der Möglichkeiten auftaucht:

Code: Alles auswählen

(
    has_population(A, 768358);
    has_population(B, 768358);
    has_population(D, 768358)
),

Fünfte Regel

Die fünfte Regel besagt: Die Haltestelle unmittelbar nach Tjumen ist in der Stadt mit einer Einwohnerzahl von 1.172.070.

Jetzt wird es noch einmal kompliziert: Die Stadt Tjumen muss nach einer Stadt X kommen, welche eine Bevölkerungszahl von 1.172.070 hat. Hierzu ist ein neues Prädikat erforderlich: comes_right_after_in/3:

Code: Alles auswählen

comes_right_after_in(_, _, []) :- false.
comes_right_after_in(_, X, [X]) :- false.
comes_right_after_in(X, H, [H|[X|_]]).
comes_right_after_in(Y, X, [_|T]) :- comes_right_after_in(Y, X, T).

Diese Regeln besagen folgendes:

1. In einer leeren Liste [] gibt es keine zwei beliebigen Elemente _, die aufeinanderfolgen.
2. In einer Liste bestehend aus einem Element [X] gibt es nichts, was auf X folgt.
3. In einer Liste bestehend aus einem Kopf H und einem Rest, der mit X anfängt, folgt X auf H.
4. In einer Liste mit beliebigem Kopf folgt Y auf X, sofern Y X im Rest folgt.

Das Prädikat comes_right_after_in/3 wird zu Testzwecken der Datei utils.pl hinzugefügt und dann folgendermassen ausprobiert:

Code: Alles auswählen

$ swipl utils.pl
?- comes_right_after_in(bob,alice,[]).
false.

?- comes_right_after_in(bob,alice,[bob]).
false.

?- comes_right_after_in(bob,alice,[bob,alice]).
false.

?- comes_right_after_in(bob,alice,[alice,bob]).
true .

?- comes_right_after_in(bob,alice,[alice,mallory,bob]).
false.

Damit lässt sich die verbleibende Regel folgendermassen formulieren:

Code: Alles auswählen

comes_right_after_in(X, tjumen, [A, B, C, D]),
has_population(X, 1172070).

Die Regel wird mit dem Punkt . terminiert.

Des Rätsels Lösung?

So wird es Zeit, das Rätsel mithilfe von Prolog aufzulösen:

Code: Alles auswählen

$ swipl transsib.pl
?- stations(A, PA, B, PB, C, PC, D, PD).
A = krasnojarsk,
PA = 768358,
B = omsk,
PB = 1090811,
C = tjumen,
PC = 1172070,
D = novosibirsk,
PD = 1612833 .

Der komplette Code von transsib.pl steht auf NoPaste 42052 zur Verfügung.

Übungen

Wer Prolog einmal selber ausprobieren möchte, kann sich an folgenden Übungen versuchen:

1. Installiere swi-prolog.
2. Lade den Code von 42052 herunter und rufe das stations/8-Prädikat wie oben beschrieben auf.
3. Die gefundene Lösung scheint nicht der Realität zu entsprechen. Ist die Implementierung oder das Rätsel falsch?
4. Suche dir ein weiteres Logical und beschreibe es hier. Versuche es mit Prolog zu lösen und poste den Code hier ‒ egal ob es funktioniert oder nicht: Vielleicht kann ja jemand weiterhelfen.

So wünsche ich allen eine logische Adventszeit!

[Meillo]

Cooles Tuerchen!

Die gefundene Lösung scheint nicht der Realität zu entsprechen. Ist die Implementierung oder das Rätsel falsch?

... ich weiss die Antwort, aber ich verrate sie nicht.

[Meillo]

Hat denn noch gar niemand sonst geraetselt? ... na, vielleicht in der Mittagspause dann.

[paedubucher]

Hat denn noch gar niemand sonst geraetselt? ... na, vielleicht in der Mittagspause dann.

Ich bin gespannt wie ein Pfeilbogen!

[Meillo]

An der Implementierung in Prolog habe ich mich nicht versucht, aber das Loesen von Hand macht mir Spass. Dabei beobachte ich, dass meist die komplizierteste Regel den Ansatzpunkt bietet. Die trivialen Aussagen notiert man sich nur; mit der kompliziertesten Regel muss man aber mit Denken anfangen.

Die grafische, schriftliche Darstellung der Situation/Moeglichkeiten ist entscheidend. Ohne die koennte ich solche Raetsel kaum loesen. Da hat mein Gehirn einfach nicht genug Register.


Hat denn schon jemand die Prolog-Implementierung bei sich ausgefuehrt? Kommt da das Ergebnis raus, das paedubucher gepostet hat?

[chrbr]

Ich habe es noch nicht ausprobiert, hätte aber auch nie angenommen, daß eine Programmiersprache so ein Problem lösen kann. Ich hatte jedenfalls Prolog "als irgendeine Programmiersprache" nur abgelegt. Wenn man sich mit den Installation nicht 1000 Abhängigkeiten aufhalst, dann probiere ich das auch aus. Auf jeden Fall ist das ein überrachend interessantes Türchen.
Dafür sage ich schon einmal "Danke schön!"

[TRex]

Ich hatte jedenfalls Prolog "als irgendeine Programmiersprache" nur abgelegt.

Alles andere als das ich hab beim Lesen VietnamVorlesung-Flashbacks bekommen und hab wieder aufgehört.

[chrbr]

Ich bin am probieren. An Abhängigkeiten muss man sehr wenig installieren, man "versaut" sich also nicht den Rechner. Das "stations(A, PA, B, PB, C, PC, D, PD)." kopiert man sich am besten in das Clipboard. Das muss man sonst in der Prolog Kommandozeile eintippen. Vor den Regeln "rule1" bis "rule5" wurde erwähnt, daß Prolog viele Lösungen herausbekommt. Man sieht zuerst eine Lösung nach der Eingabe von "stations(A, PA, B, PB, C, PC, D, PD).". Mit der Eingabe von RETURN bzw ENTER bricht man die Ausgabe ab. Mit der Eingabe von einem Leerzeichen oder Semikolon bekommt man weitere Lösungen angezeigt.

Bei dem Beispiel mit "rule1" bis "rule5" gibt es weitere Lösungen. Im Beitrag ist nur die erste Lösung abgedruckt. Ich vermute, daß etwas in der Syntax mit den Regeln nicht stimmt. Ich habe den Fehler aber noch nicht gefunden.

[whisper]

Vielen Dank für die Informationen über Prolog!
Es klingt nach einer interessanten Programmiersprache, die auf logischer Schlussfolgerung basiert.
Leider fehlt mir momentan die Zeit und Energie, mich damit zu beschäftigen.
Aber ich werde es mir merken und vielleicht in Zukunft eine Gelegenheit finden, es genauer zu erkunden.

[Meillo]

Bei dem Beispiel mit "rule1" bis "rule5" gibt es weitere Lösungen. Im Beitrag ist nur die erste Lösung abgedruckt. Ich vermute, daß etwas in der Syntax mit den Regeln nicht stimmt. Ich habe den Fehler aber noch nicht gefunden.

Die abgedruckte ``Loesung'' verstoesst gegen Regel 2:

Die zweite Regel besagt: Die vierte Station ist eine Stadt mit 1.090.811 Einwohnern.

Die vierte Stadt D muss die angegebene Einwohnerzahl haben:

Code: Alles auswählen

has_population(D, 1090811),

Code: Alles auswählen

$ swipl transsib.pl
?- stations(A, PA, B, PB, C, PC, D, PD).
A = krasnojarsk,
PA = 768358,
B = omsk,
PB = 1090811,
C = tjumen,
PC = 1172070,
D = novosibirsk,
PD = 1612833 .

Ich verstehe nicht wieso das der Fall ist. Eigentlich wirkt die Regel recht einfach auf mich. Wie kann Prolog dagegen verstossen? Irgendwas scheint mit den Regeln nicht ganz zu passen ...

[Meillo]

Was ich auch noch nicht verstehe (ohne jedoch irgendeine Ahnung von Prolog zu haben ):

Warum brauchen wir ueberhaupt `has_population()' und schreiben nicht einfach:

Code: Alles auswählen

PD = 1090811.

... in der gleichen Art wie bei Omsk?

Ich wuerde mutmassen, dass wir `has_population()' vielleicht nur mit konkreten Staedtenamen aufrufen duerfen/muessen. Wenn wir aber Bevoelkerungszahlen an Positionen koppeln (Regeln 2 und 4), dann koennen wir diese direkt den P*-Variablen zuweisen ...

?

[chrbr]

Mit PD=... wird jedenfalls der PD Wert fest definiert.
Dafür gibt es eine Singleton Warnung für die letzte comes_right_after_in Definition.

Code: Alles auswählen

> swipl transsibirien.pl
Warning: /home/chris/transsibirien.pl:28:
Warning:    Singleton variables: [Y]

Der Teil ist mir sowieso suspekt.

[chrbr]

Der Fehler war von mir.

Aber kann es sein, daß zusätzlich noch eine Regel fehlt?
Die Reihenfolge muss ja nicht zwingend A-B-C-D sein. Das ist ja nur eine übliche Konvention. Ich muss mal versuchen, die Ausgabe in eine Datei umzuleiten. Dann kann man vielleicht etwas erkennen.

[Meillo]

Aber kann es sein, daß zusätzlich noch eine Regel fehlt?
Die Reihenfolge muss ja nicht zwingend A-B-C-D sein. Das ist ja nur eine übliche Konvention.

Guter Gedanke!

Bisher sehe ich nicht, wo hinterlegt ist, dass B nach A kommt und C nach B und D nach C.

Auch frage ich mich, wo die Verknuepfung ist, dass PA die Population von A ist, usw.

[chrbr]

So, script sei Dank habe ich etwas interessantes. Es gibt 192 Möglichkeiten. Davon sind scheinbar immer 6 identische Zeilen, also

Code: Alles auswählen

  10 ?- stations(A, PA, B, PB, C, PC, D, PD^M^[[39G)^[[12G^[[40G.^M
  11 A = krasnnojarsk,^M PA = 768358,^M B = omsk,^M PB = 1172070,^M C = tjumen,^M PC = 1612833,^M D = novosibirsk,^M PD = 1090811 ^[[1m;^[[0m^M
  12 A = krasnnojarsk,^M PA = 768358,^M B = omsk,^M PB = 1172070,^M C = tjumen,^M PC = 1612833,^M D = novosibirsk,^M PD = 1090811 ^[[1m;^[[0m^M
  13 A = krasnnojarsk,^M PA = 768358,^M B = omsk,^M PB = 1172070,^M C = tjumen,^M PC = 1612833,^M D = novosibirsk,^M PD = 1090811 ^[[1m;^[[0m^M
  14 A = krasnnojarsk,^M PA = 768358,^M B = omsk,^M PB = 1172070,^M C = tjumen,^M PC = 1612833,^M D = novosibirsk,^M PD = 1090811 ^[[1m;^[[0m^M
  15 A = krasnnojarsk,^M PA = 768358,^M B = omsk,^M PB = 1172070,^M C = tjumen,^M PC = 1612833,^M D = novosibirsk,^M PD = 1090811 ^[[1m;^[[0m^M
  16 A = krasnnojarsk,^M PA = 768358,^M B = omsk,^M PB = 1172070,^M C = tjumen,^M PC = 1612833,^M D = novosibirsk,^M PD = 1090811 ^[[1m;^[[0m^M
  17
  18 A = krasnnojarsk,^M PA = 768358,^M B = omsk,^M PB = 1612833,^M C = tjumen,^M PC = 1172070,^M D = novosibirsk,^M PD = 1090811 ^[[1m;^[[0m^M
  19 A = krasnnojarsk,^M PA = 768358,^M B = omsk,^M PB = 1612833,^M C = tjumen,^M PC = 1172070,^M D = novosibirsk,^M PD = 1090811 ^[[1m;^[[0m^M
  20 A = krasnnojarsk,^M PA = 768358,^M B = omsk,^M PB = 1612833,^M C = tjumen,^M PC = 1172070,^M D = novosibirsk,^M PD = 1090811 ^[[1m;^[[0m^M
  21 A = krasnnojarsk,^M PA = 768358,^M B = omsk,^M PB = 1612833,^M C = tjumen,^M PC = 1172070,^M D = novosibirsk,^M PD = 1090811 ^[[1m;^[[0m^M
  22 A = krasnnojarsk,^M PA = 768358,^M B = omsk,^M PB = 1612833,^M C = tjumen,^M PC = 1172070,^M D = novosibirsk,^M PD = 1090811 ^[[1m;^[[0m^M
  23 A = krasnnojarsk,^M PA = 768358,^M B = omsk,^M PB = 1612833,^M C = tjumen,^M PC = 1172070,^M D = novosibirsk,^M PD = 1090811 ^[[1m;^[[0m^M
  24
  25 A = krasnnojarsk,^M PA = 1172070,^M B = omsk,^M PB = 768358,^M C = tjumen,^M PC = 1612833,^M D = novosibirsk,^M PD = 1090811 ^[[1m;^[[0m^M
  26 A = krasnnojarsk,^M PA = 1172070,^M B = omsk,^M PB = 768358,^M C = tjumen,^M PC = 1612833,^M D = novosibirsk,^M PD = 1090811 ^[[1m;^[[0m^M
  27 A = krasnnojarsk,^M PA = 1172070,^M B = omsk,^M PB = 768358,^M C = tjumen,^M PC = 1612833,^M D = novosibirsk,^M PD = 1090811 ^[[1m;^[[0m^M
  28 A = krasnnojarsk,^M PA = 1172070,^M B = omsk,^M PB = 768358,^M C = tjumen,^M PC = 1612833,^M D = novosibirsk,^M PD = 1090811 ^[[1m;^[[0m^M
  29 A = krasnnojarsk,^M PA = 1172070,^M B = omsk,^M PB = 768358,^M C = tjumen,^M PC = 1612833,^M D = novosibirsk,^M PD = 1090811 ^[[1m;^[[0m^M
  30 A = krasnnojarsk,^M PA = 1172070,^M B = omsk,^M PB = 768358,^M C = tjumen,^M PC = 1612833,^M D = novosibirsk,^M PD = 1090811 ^[[1m;^[[0m^M

und so weiter. Weiter unten dann auch mit anderen Reihenfolgen der Städte. Aber falls Omsk als zweite Stadt feststeht, dann bleiben 3!=1*2*3=6 Möglichkeiten für die Kombinationen von A, C und D. Dann hat man in den sechser Blöcken die Zuordnung Stadt-Einwohner, aber nicht die Reihenfolge.

Es muss also mindestens noch ein zweites Problem geben.

[chrbr]

Eine Preisfrage kann noch sein, ob das so funktioniert wie beschrieben:

Code: Alles auswählen

comes_right_after_in(X, tjumen, [A, B, C, D]),
    has_population(X, 1172070).

Zur Ergänzung des vorherigen Beitrags, ich habe in "rule2" und "rule4" has_population() durch Px= ersetzt. Morgen werde ich weiter buddeln, für heute reicht es erst einmal.

[Meillo]

Braucht es nicht vielleicht sowas:

Code: Alles auswählen

comes_right_after_in(B, A, [A, B, C, D]).
comes_right_after_in(C, B, [A, B, C, D]).
comes_right_after_in(D, C, [A, B, C, D]).

?

... ich bin jedenfalls gespannt, wie's weiter geht -- eine Bugsuche wie eine Fahrt mit der Transsibirischen Eisenbahn! D.h. die kann noch lange dauern.

[heisenberg]

Ich habe das Türchen noch nicht ganz gelesen und teilweise habe ich auch einen buffer overflow im Gehirn gehabt.

Ich habe erst nicht verstanden, warum Paedubucher das Lösungsarray mit Städtenamen und Bevölkerungszahlen gleichermaßen aufgebaut hat. Nachdem ich die Lösung mit SQL versucht habe, bin ich aber auf den gleichen Ansatz gekommen. Die Lösung mit SQL ist logisch nicht so simpel und enthält logische Redundanzen, hat aber vermutlich sehr ähnliche Züge mit der Art und Weise, wie Prolog das intern handhabt: Es gibt eine große Lösungsmenge (64K Datensätze), die durch die Regeln schrittweise bis auf eine reduziert wird. Ich kann ja zum Schluss die Selects nochmal zeigen.

Ich habe definitiv eine andere Lösung bekommen. Als gewitzter Lehrer wird Paedubucher also absichtlich ein paar Fehler eingebaut haben. Man wird dem Fehler vermutlich auf die Schliche kommen, indem man schaut, gegen welche der Hinweise verstossen wurde.

Nachtrag:

Wenn ich mal ein kleines Testprogramm schreibe ...

Code: Alles auswählen

city(frankfurt).
city(berlin).

unique([]).
unique([_]).
unique([H|T]) :-
    \+ contains(T, H),
    unique(T).

contains([], _) :- false.
contains([H|_], H).
contains([_|T], X) :- contains(T, X).

tst(A, B) :- 
        city(A),
        city(B).

Dann bekomme ich wie erwartet 4 Lösungen ...

Code: Alles auswählen

A = B, B = frankfurt ;
A = frankfurt,
B = berlin ;
A = berlin,
B = frankfurt ;
A = B, B = berlin.

Wenn ich die tst-Regel um das unique erweitere ...

Code: Alles auswählen

tst(A, B) :- 
        city(A),
        city(B),
        unique([A,B]).

... dann bekomme ich immer noch 4 Ergebnisse, aber mit Dopplungen ...

Code: Alles auswählen

A = frankfurt,
B = berlin ;
A = frankfurt,
B = berlin ;
A = berlin,
B = frankfurt ;
A = berlin,
B = frankfurt ;
false.

...und noch ein false am Ende. Das verstehe ich gar nicht.

[chrbr]

Ich habe die Fragestellung mit einem kleinen Python Skript bearbeitet und kommt auf eine einzige Lösung, die sich auch mit der Realität deckt. Das war auch zu erwarten. Nun geht es wieder zum Prolog Skript.

[Meillo]

Nun geht es wieder zum Prolog Skript.

[heisenberg]

Was ich an der swipl - Runtime extrem nervig finde, ist, wie schon anderweitig hier geschrieben wurde, dass man nicht alle Lösungen in einem Rutsch ausgeben lassen kann. Dann könnte man die Ergebnismenge analysieren. Die Vorschläge im Netz, die ich dazu find, haben bei mir alle nicht das Gewünschte bewirkt.

Aber insgesamt sieht man schon, wo man beim Arbeiten damit hinkommt. Durch das geschickte Deklarieren ist dei Menge an Regeln sehr gering und man muss sich da überhaupt nicht um die Programmlogik kümmern.

[chrbr]

Mit dem unique stimmt etwas nicht. https://www.swi-prolog.org/pldoc/man?section=lists zeigt aber Kommandos zu Listen auf, die ich auch von Python her kenne.

Code: Alles auswählen

city(frankfurt).
city(berlin).

tst(A, B) :- 
	city(A),
	city(B),
	is_set([A, B]).

erzeugt keine doppelten Zeilen, sondern

Code: Alles auswählen

?- tst(A, B).
A = frankfurt,
B = berlin ;
A = berlin,
B = frankfurt ;
false.

[chrbr]

Was ich an der swipl - Runtime extrem nervig finde, ist, wie schon anderweitig hier geschrieben wurde, dass man nicht alle Lösungen in einem Rutsch ausgeben lassen kann. Dann könnte man die Ergebnismenge analysieren.

Da kann man sich mit script behelfen, indem man eine script Aufzeichnung startet. Dann lädt man das Prologskript und startet die gewünschte Funktion. Danach drückt man die Leertaste bis sich nichts mehr tut. Nun kann man Prolog und die script Aufzeichnung beenden.

Was mich fast noch mehr stört ist die eigenartige Dokumentation. Das beginnt schon mit den Datentypen. Was ist zum Beispiel mit city()? Listen sind eigentlich mit eckigen Klammern notiert. Auf der Webseite wird empfohlen, sich durch externe Tutorials zu arbeiten. Das ist nicht gerade wie aus einem Guss. Wie Prolog genau funktioniert habe ich auch noch nicht sicher verstanden. Aber interessant ist es schon.

[heisenberg]

Ja. Eine Frickellösung für die Ausgabeverarbeitung habe ich auch. (Copy-Paste)

Das beginnt schon mit den Datentypen. Was ist zum Beispiel mit city()? Listen sind eigentlich mit eckigen Klammern notiert.

city(stadtname) ist ja keine Liste sondern ein einstelliges Prädikat. Einstellige Prädikate heissen auch Atome.

Aber mir geht es ansonsten ähnlich. Ich verstehe passend zur Aufgabenstellung an vielen Stellen nur Bahnhof. Die Dokumentation beantwortet meine Fragen nicht wirklich und die Tutorials sind alles andere als leicht verständlich. Ist halt kein triviales Thema und insofern für mich nicht ungewöhnlich.

Ich wollte mich schon immer mal damit beschäftigen. Insofern freue mich mich über dieses Türchen ganz besonders. Ich habe mich mal in einem Tutorial eingelesen und das, was Paedubucher uns hier präsentiert, das umfasst schon mehrere Kapitel in einem Kurs.

[Meillo]

Gibt's denn hier gar niemanden, der sich mit Prolog so richtig gut auskennt?

TRex ist traumatisiert und paedubucher scheint sich entspannt zurueckzulehnen ... Wir stuempern mit unserem Halbwissen rum, dabei ist es bei einer so indirekten/high-level Sprache wie Prolog besonders wichtig, zu *wissen* was man tut und Trial'n'Error kaum hilfreich.

Moege uns doch ein Prolog-Meister mit seinem Wissen beehren!