在Prolog中解决“喂食Golorp”难题

Question

不久前，我为Codeforces愚人节竞赛2014创建了一个问题 -“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

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

结果：2001022022202020121001011122021000112012210012001002220120022210000200010200001210022200000200221020000000022012020200000112201100020200

- Sergii Dymchenko

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

恢复以前的答案...

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

鉴于您的详细解释，这很容易，但效率不高...

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

< p >编辑我希望有一个基于变量排序的反例，因为我感觉我的代码可能不完整/不正确...

事实上，我完全忽略了连接部分...

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 中的一项实用工具...

- CapelliC

Answer 2

这是一个使用 ECLiPSe 直接获取 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)
    ).

我使用了一个保留副本的term_variables/2变体，并利用了ic约束求解器库定义的所有比较谓词>/2、</2等的约束版本。样例运行：

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

- jschimpf