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

该问题原本打算由完全不了解Prolog的人解决。竞赛期间只有3个人用Java,Python和C ++解决了问题。

主要的挑战是要了解需要做什么。对于具有Prolog经验的人来说,这几乎是显而易见的
golorp的名称(如?(_-_/___*__):-___>__.)定义了Prolog谓词,任务是找到变量的最小值,以使谓词得到满足。
有一些详细信息:请再次阅读问题说明。

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

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

由于仅使用Prolog回溯来暴力破解golorp名称的长度(最多1024个字符),所有可能性似乎都不可行-
可能需要约束逻辑编程。

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

最佳答案

这是一个直接采用Golorp描述的ECLiPSe解决方案:

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

关于prolog - 解决Prolog中的“Feed the Golorp”难题,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/23207576/

10-11 23:16
查看更多