prolog - 在 Prolog 中解决 "Feed the Golorp"难题

Question

前段时间我为 2014 年 Codeforces 愚人节比赛创建了一个问题 - “Feed the Golorp”:http://codeforces.com/contest/409/problem/I .
请阅读所提供链接上的问题说明。

该问题旨在由根本不了解 Prolog 的人解决。在比赛期间，只有 3 个人设法解决了这个问题 - 使用 Java、Python 和 C++。

主要的挑战是了解需要做什么。对于有一些 Prolog 经验的人来说，这应该是显而易见的
那个 golorp 的名字就像 ?(_-_/___*__):-___>__.定义了一个 Prolog 谓词，任务是找到满足谓词的变量的最小值。
有一些细节:再次，请阅读问题说明。

其实在理解目标之后解决问题并不是那么简单。从算法上讲，任务是根据约束对变量进行拓扑排序。
Golorp 的名称最长可达 1024 个字符，因此需要相当高效的算法。

我用正则表达式用 Python 编写了我的引用解决方案。但是比赛结束后，我开始想知道如何解决 Prolog 中的问题。

由于 golorp 名称的长度可能长达 1024 个字符，仅使用 Prolog 回溯来暴力破解所有可能性看起来都不可行-
可能需要约束逻辑编程。

如果我可以从不等式中提取所有变量的列表和变量对的列表，我就可以解决它。例如在 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"

但我不知道如何获得 Vars = [__, ___, __, ___]和 Ineqs = [(__, ___)]来自 ?(__+___+__-___):-___>__.没有太多的代码。 term_variables/2丢失重复变量。 DCG？

或者是否有完全不同的更好的方法来解决 Prolog 中的难题？ (不一定在 ECLiPSe CLP 中)。

更新:几个要测试的大示例:

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

结果:3898080517870043672800

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

结果:200102202220202012100101112202100011201221001200100222012002221000020001020000121002220000002002002000200200020002000200020002000

Answer 1

最后编辑:由于基于蛮力的答案是不合适的，如建议，这里是基于库(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).

在最大的例子上效果很好，产生“3898080517870043672800”......

恢复之前的回答...

纯序言:

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

很容易，鉴于您的广泛解释，但效率不高......

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

编辑我想要一个基于变量排序的反例，因为我觉得我的代码可能不完整/不正确......

确实，我完全错过了连接部分......

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

现在结果更可信

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

或者，更紧凑和产生类似于示例的输出:

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

但是， with_output_to/2 它只是一个 SWI-Prolog 实用程序......