Resolviendo el acertijo "Feed the Golorp" en Prolog

metaprogramming constraint-programming

Question

Hace un tiempo creé un problema para Codeforces April Fools Day Contest 2014 - "Feed the Golorp": http://codeforces.com/contest/409/problem/I . Por favor, lea la declaración del problema en el enlace proporcionado.

El problema fue pensado para ser resuelto por personas que no conocen Prolog en absoluto. Solo 3 personas lograron resolver el problema durante el concurso: en Java, Python y C ++.

El principal desafío es entender qué se debe hacer. Para una persona con experiencia en Prolog, debería ser casi obvio que el nombre de golorp es ?(_-_/___*__):-___>__. define un predicado Prolog, y la tarea es encontrar valores mínimos de variables de modo que los predicados estén satisfechos. Hay algunos detalles: de nuevo, lea la declaración del problema.

En realidad, resolver el problema después de comprender el objetivo no es tan trivial. De manera algorítmica, la tarea es ordenar topológicamente las variables de acuerdo con las restricciones. El nombre de Golorp puede tener hasta 1024 caracteres, por lo que se necesita un algoritmo decentemente eficiente.

Escribí mi solución de referencia en Python con expresiones regulares. Pero después del concurso comencé a preguntarme cómo resolver el problema en Prolog.

Debido a la longitud posible del nombre de golorp de hasta 1024 caracteres usando solo el backtracking de Prolog para aplicar fuerza bruta, todas las posibilidades no parecen factibles; probablemente se necesite una programación lógica de restricciones.

Si pudiera extraer la lista de todas las variables y la lista de pares de variables de las desigualdades, puedo resolverlo. Por ejemplo, en 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"

Pero no estoy seguro de cómo obtener Vars = [__, ___, __, ___] e Ineqs = [(__, ___)] de ?(__+___+__-___):-___>__. sin demasiado código term_variables/2 pierde variables duplicadas. DCG?

¿O hay una forma completamente diferente y mejor de resolver el rompecabezas en Prolog? (no necesariamente en ECLiPSe CLP).

Actualización: un par de ejemplos grandes para probar:

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

Resultado: 3898080517870043672800

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

Resultado: 2001022022202020121001011122021000112012210012001002220120022210000200010200001210022200000200221020000000022012020200000112201100020200

Answer 1

Esta es una solución ECLiPSe que toma la descripción de Golorp directamente:

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

Utilicé una variante de preservación de term_variables/2 de term_variables/2 y exploté el hecho de que la librería de term_variables/2 restricciones ic define las versiones de restricción de todos los predicados de comparación >/2, </2 etc. Ejemplo de ejecución:

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

Answer 2

Última edición : Dado que la respuesta basada en la fuerza bruta fue inapropiada, como se aconseja, aquí está la solución basada en la biblioteca (clpfd):

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

que funciona bien en el ejemplo más grande, produciendo "3898080517870043672800" ...

Reanudar la respuesta anterior ...

Prólogo puro:

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

fácil, dada su extensa explicación, pero no tan eficiente ...

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

editar Me gustaría un contraejemplo basado en el orden de las variables, ya que creo que mi código podría estar incompleto / incorrecto ...

De hecho, me perdí completamente la parte de concatenación ...

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

ahora el resultado es más plausible

?- 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, algo más compacto y produciendo resultados similares al ejemplo:

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

pero, con_output_to / 2 es una utilidad SWI-Prolog solamente ...