Lösung "Feed the Golorp" Puzzle in Prolog

Question

Vor einiger Zeit habe ich ein Problem für den Codeforces April Fools Day Wettbewerb 2014 - "Feed the Golorp": http://codeforces.com/contest/409/problem/I erstellt. Bitte lesen Sie die Problembeschreibung auf dem angegebenen Link.

Das Problem sollte von Leuten gelöst werden, die Prolog überhaupt nicht kennen. Nur 3 Personen konnten das Problem während des Wettbewerbs lösen - in Java, Python und C++.

Die größte Herausforderung besteht darin zu verstehen, was zu tun ist. Für eine Person mit etwas Prolog-Erfahrung sollte es fast offensichtlich sein , dass Golpors Name wie ?(_-_/___*__):-___>__. ein Prolog-Prädikat definiert, und die Aufgabe besteht darin, minimale Werte von Variablen zu finden, so dass die Prädikate erfüllt sind. Es gibt einige Details: Bitte lesen Sie erneut die Problembeschreibung.

Tatsächlich ist das Lösen des Problems nach dem Verstehen des Ziels nicht so trivial. Algorithmisch besteht die Aufgabe darin, die Variablen topologisch nach Randbedingungen zu sortieren. Der Name von Golorp kann bis zu 1024 Zeichen lang sein, daher ist ein anständig effizienter Algorithmus erforderlich.

Ich schrieb meine Referenzlösung in Python mit regulären Ausdrücken. Aber nach dem Wettbewerb begann ich mich zu fragen, wie ich das Problem in Prolog lösen könnte.

Wegen der möglichen Länge des Namens der golorp bis zu 1024 Zeichen mit nur Prolog Backtracking, um bruteforce alle Möglichkeiten sieht nicht machbar - Constraint Logik Programmierung ist wahrscheinlich erforderlich.

Wenn ich Liste aller Variablen und Liste der Variablenpaare aus den Ungleichungen extrahieren könnte, kann ich es lösen. Zum Beispiel in der Eklipse CLP:

:- lib(ic). 
solve(Vars, Ineqs, Result) :- 
    Vars :: 0..9, 
    (foreach((A, B), Ineqs) do 
     A #< B), 
    labeling(Vars), 
    concat_string(Vars, Result). 

[eclipse]: Vars = [__, ___, __, ___], Ineqs = [(__, ___)], solve(Vars, Ineqs, Result). 

Vars = [0, 1, 0, 1] 
__ = 0 
___ = 1 
Ineqs = [(0, 1)] 
Result = "0101" 

Aber ich bin nicht sicher, wie Vars = [__, ___, __, ___] und Ineqs = [(__, ___)] von ?(__+___+__-___):-___>__. ohne zu viel Code zu bekommen. term_variables/2 verliert doppelte Variablen. DCG?

Oder gibt es einen völlig anderen, besseren Weg, um das Puzzle in Prolog zu lösen? (nicht notwendigerweise in ECLiPSe CLP).

Update: paar große Beispiele zu testen:

?(_____________________*_________________________*________________________*___________________*_________________*__________________*___________________________*___*__*____________________*_________________________*_______________*____*___________*_____________*______*_____*_______________*____________*__________________*___________________________*___________________________):-_____>__,_______________<___________________,__>___________,________________________>______,_____________>______,____________________<_________________________,_________________<__________________,_____________<___,____<_________________________,______>____________,________________________>_________________________,_____<____________________,__<____________,_____________________>____________,__________________>_______________,_____>___,___________<_______________,_________________________>____,____<___________________,________________________>___________________________,____________>___________________________,_____<_______________. 

Ergebnis: 3898080517870043672800

?(___*__*_____*____*_____*___*___*_____*___*___*___*__*___*_____*___*_____*____*___*____*_____*_____*____*_____*____*____*____*___*___*__*___*____*__*_____*_____*____*____*___*__*____*___*___*____*_____*_____*____*___*__*_____*____*__*_____*___*___*___*_____*____*___*_____*_____*___*___*___*____*__*_____*_____*__*___*__*__*_____*____*_____*___*__*_____*_____*__*____*___*____*_____*_____*___*___*___*_____*__*__*__*__*___*_____*__*___*___*____*_____*___*__*_____*_____*_____*_____*_____*__*__*___*___*_____*____*___*__*___*__*___*_____*__*_____*_____*_____*____*____*___*___*_____*____*____*__*__*_____*___*__*___*_____*_____):-____>_____,___>____. 

Ergebnis: 2001022022202020121001011122021000112012210012001002220120022210000200010200001210022200000200221020000000022012020200000112201100020200

Answer 1

Dies ist eine ECLiPSe Lösung, die die Golorp Beschreibung direkt übernimmt:

:- lib(ic). 

golorp((?(Jaws):-Stomach), Food) :- 
    term_vars(Jaws, Xs, []), 
    Xs :: 0..9, 
    call(Stomach)@ic, 
    once labeling(Xs), 
    concat_string(Xs, Food). 

term_vars(X, [X|Vs], Vs) :- var(X). 
term_vars(Xs, Vs, Vs0) :- nonvar(Xs), 
    (foreacharg(X,Xs), fromto(Vs,Vs2,Vs1,Vs0) do 
     term_vars(X, Vs2, Vs1) 
    ). 

Ich habe eine doppelte erhalt Variante term_variables/2 und nutzte die Tatsache, dass die ic Constraintlöser Bibliothek definiert Constraint-Versionen aller Vergleichsprädikate >/2, </2 usw. Beispiellauf verwendet:

?- golorp((?(_-_/___*__):-___>__), Food). 
___ = 1 
__ = 0 
Food = "0010" 
Yes (0.00s cpu) 

Answer 2

zuletzt: Da Brute-Force-basierte Antwort unangemessen war, wie empfohlen, hier ist die Bibliothek (clpfd) basierte Lösung:

:- [library(clpfd)]. 

feed_the_golorp_clp(G, Food) :- 
    G = (?(F) :- C), 
    prepare(C, P), 
    term_variables(G, T), 
    T ins 0..9, 
    call(P), 
    label(T), 
    with_output_to(string(Food), yields(F)). 

yields(E) :- E =.. [_,A,B] -> yields(A), yields(B) ; write(E). 

prepare(C, P) :- 
    compound(C), 
    C =.. [O, A, B], 
    member((O, Op), [(<, #<), (>, #>), ((,), (,))]), 
    prepare(A, Pa), 
    prepare(B, Pb), 
    P =.. [Op, Pa, Pb]. 
prepare(C, C). 

, die gut auf dem größten Beispiel funktioniert "3898080517870043672800" ...

Lebenslauf vorherigen nachgebend Antworten...

reiner Prolog:

feed_the_golorp(G, F) :- 
    G = (_ :- B), 
    term_variables(G, F), 
    maplist(food, F), 
    call(B). 

food(X) :- member(X, [0,1,2,3,4,5,6,7,8,9]). 

leicht, Ihre ausführliche Erklärung gegeben, aber nicht so effizient ...

?- time(feed_the_golorp((?(______________________/____+_______*__-_____*______-___):-__<___,___<____,____<_____,_____<______,______<_______), F)). 
% 976,115 inferences, 0.874 CPU in 0.876 seconds (100% CPU, 1116785 Lips) 
______________________ = __, __ = 0, 
____ = 2, 
_______ = 5, 
_____ = 3, 
______ = 4, 
___ = 1, 
F = [0, 2, 5, 0, 3, 4, 1] 
. 

bearbeiten ich ein Gegenbeispiel auf Variablen Bestellung basierte möchte, da Ich fühle, dass mein Code unvollständig/falsch sein könnte ...

Tatsächlich habe ich den Verkettungsteil komplett vermisst ...

feed_the_golorp(G, Food) :- 
    G = (?(F) :- C), 
    term_variables(G, T), 
    maplist(food, T), 
    call(C), 
    yields(F, S), 
    atomic_list_concat(S, Food). 

food(X) :- member(X, [0,1,2,3,4,5,6,7,8,9]). 

yields(C, [C]) :- number(C). 
yields(E, S) :- E =.. [_,A,B], yields(A,Ca), yields(B,Cb), append(Ca,Cb,S). 

jetzt ist das Ergebnis plausibler

?- time(feed_the_golorp((?(___*__*_____*____*_____*___*___*_____*___*___*___*__*___*_____*___*_____*____*___*____*_____*_____*____*_____*____*____*____*___*___*__*___*____*__*_____*_____*____*____*___*__*____*___*___*____*_____*_____*____*___*__*_____*____*__*_____*___*___*___*_____*____*___*_____*_____*___*___*___*____*__*_____*_____*__*___*__*__*_____*____*_____*___*__*_____*_____*__*____*___*____*_____*_____*___*___*___*_____*__*__*__*__*___*_____*__*___*___*____*_____*___*__*_____*_____*_____*_____*_____*__*__*___*___*_____*____*___*__*___*__*___*_____*__*_____*_____*_____*____*____*___*___*_____*____*____*__*__*_____*___*__*___*_____*_____):-____>_____,___>____), F)). 
% 17,806 inferences, 0.009 CPU in 0.010 seconds (94% CPU, 1968536 Lips) 
___ = 2, 
__ = _____, _____ = 0, 
____ = 1, 
F = '2001022022202020121001011122021000112012210012001002220120022210000200010200001210022200000200221020000000022012020200000112201100020200' 
. 

oder etwas kompaktere und nachgiebig Ausgang ähnlich Beispiel:

feed_the_golorp(G, Food) :- 
    G = (?(F) :- C), 
    term_variables(G, T), 
    maplist(food, T), 
    call(C), 
    with_output_to(string(Food), yields(F)). 

food(X) :- member(X, [0,1,2,3,4,5,6,7,8,9]). 

yields(E) :- E =.. [_,A,B] -> yields(A), yields(B) ; write(E). 

aber with_output_to/2 es nur ein SWI-Prolog ist Dienstprogramm ...