Решение головоломки «Подача голограммы» в Прологе

Question

Некоторое время назад я создал проблему для Codeforces April Fools Day Contest 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?

Или существует совершенно другой, лучший способ решить головоломку в Прологе? (не обязательно в ECLiPSe CLP).

Update: пару больших примеров тест:

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

Результат: 3898080517870043672800

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

Результат: 2001022022202020121001011122021000112012210012001002220120022210000200010200001210022200000200221020000000022012020200000112201100020200

Answer 1

Это решение 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) 

Answer 2

последнее редактирование: С перебором на основе ответа нецелесообразно, в соответствии с рекомендациями, здесь находится библиотека (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-Пролог коммунальные ...