Risoluzione di "Feed the Golorp" in Prolog

Question

Qualche tempo fa ho creato un problema per Codeforces April Fools Day Contest 2014 - "Feed the Golorp": http://codeforces.com/contest/409/problem/I. Si prega di leggere la dichiarazione del problema sul link fornito.

Il problema doveva essere risolto da persone che non conoscono Prolog. Solo 3 persone sono riuscite a risolvere il problema durante il contest - in Java, Python e C++.

La sfida principale è capire cosa è necessario fare. Per una persona con esperienza di Prolog dovrebbe essere quasi ovvio che il nome di golorp come ?(_-_/___*__):-___>__. definisce un predicato Prolog e il compito è di trovare valori minimi di variabili tali che i predicati siano soddisfatti. Ci sono alcuni dettagli: di nuovo, leggi la dichiarazione del problema.

In realtà risolvere il problema dopo aver compreso l'obiettivo non è così banale. Algoritmicamente il compito è quello di ordinare topologicamente le variabili in base ai vincoli. Il nome di Golorp può essere lungo fino a 1024 caratteri, quindi è necessario un algoritmo decentemente efficiente.

Ho scritto la mia soluzione di riferimento in Python con espressioni regolari. Ma dopo la gara ho iniziato a chiedermi come risolvere il problema in Prolog.

A causa della lunghezza possibile del nome di golorp fino a 1024 caratteri utilizzando solo il backtracking di Prolog per bruteforce, tutte le possibilità non sembrano possibili - è probabilmente necessaria la programmazione della logica dei vincoli .

Se riesco a estrarre l'elenco di tutte le variabili e l'elenco di coppie di variabili dalle disuguaglianze, posso risolverlo. Per esempio in Eclipse 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" 

Ma io non sono sicuro di come ottenere Vars = [__, ___, __, ___] e Ineqs = [(__, ___)] da ?(__+___+__-___):-___>__. senza troppo codice. term_variables/2 perde le variabili duplicate. DCG?

Oppure esiste un modo completamente diverso e migliore per risolvere il puzzle in Prolog? (non necessariamente in ECLiPSe CLP).

Aggiornamento: paio di grandi esempi di prova:

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

Risultato: 3898080517870043672800

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

Risultato: 2001022022202020121001011122021000112012210012001002220120022210000200010200001210022200000200221020000000022012020200000112201100020200

Answer 1

Questa è una soluzione ECLiPSe che prende direttamente la descrizione Golorp:

:- 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) 
    ). 

Ho usato una variante duplicato-conservazione di term_variables/2, e sfruttato il fatto che l'IC biblioteca risolutore vincolo definisce vincoli-versioni di tutto il confronto predicati >/2, </2 ecc esempio di esecuzione:

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

Answer 2

ultima modifica: Dal risposta basata forza bruta era inadeguato, come consigliato, qui è la biblioteca (clpfd) soluzione basata:

:- [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). 

che funziona bene su più grande esempio, dà il "3898080517870043672800" ...

Riprendi precedente risposta...

pura 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]). 

facile, dato il vostro vasta spiegazione, ma non così efficace ...

?- 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] 
. 

modificare Vorrei un controesempio in base a variabili ordinazione, dal momento che Sento che il mio codice potrebbe essere incompleto/errato ...

Infatti, ho completamente perso la parte di concatenazione ...

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). 

ora il risultato è più plausibile

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

o, in qualche modo più compatto e cedevole output simile all'esempio:

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). 

ma, with_output_to/2 è solo uno SWI-Prolog utility ...