关于建立符合条件的清单 [英] About building a list until it meets conditions

问题描述

我想用Prolog解决Dan Finkel的巨型猫军之谜" .

I wanted to solve "the giant cat army riddle" by Dan Finkel using Prolog.

基本上，您从 [0] 开始，然后使用以下三种操作之一构建此列表:添加 5 ，添加 7 ，或采用 sqrt .当您成功建立了一个列表，以使 2 ， 10 和 14 依次出现在列表上时，便可以成功完成游戏，它们之间可以有其他数字.

Basically you start with [0], then you build this list by using one of three operations: adding 5, adding 7, or taking sqrt. You successfully complete the game when you have managed to build a list such that 2,10 and 14 appear on the list, in that order, and there can be other numbers between them.

规则还要求所有元素都是不同的，它们都是< = 60 且都是整数.例如，从 [0] 开始，您可以应用(add5，add7，add5)，这将导致 [0、5、12、17]，但由于该顺序没有2,10,14，因此无法满足游戏要求.

The rules also require that all the elements are distinct, they're all <=60 and are all only integers. For example, starting with [0], you can apply (add5, add7, add5), which would result in [0, 5, 12, 17], but since it doesn't have 2,10,14 in that order it doesn't satisfy the game.

我认为我已经成功地编写了必不可少的事实，但是我不知道如何实际构建列表.我认为使用 dcg 是一个不错的选择，但我不知道如何.

I think I have successfully managed to write the required facts, but I can't figure out how to actually build the list. I think using dcg is a good option for this, but I don't know how.

这是我的代码:

:- use_module(library(lists)).
:- use_module(library(clpz)).
:- use_module(library(dcgs)).

% integer sqrt
isqrt(X, Y) :- Y #>= 0, X #= Y*Y.

% makes sure X occurs before Y and Y occurs before Z
before(X, Y, Z) --> ..., [X], ..., [Y], ..., [Z], ... .
... --> [].
... --> [_], ... .

% in reverse, since the operations are in reverse too.
order(Ls) :- phrase(before(14,10,2), Ls).

% rule for all the elements to be less than 60.
lt60_(X) :- X #=< 60.
lt60(Ls) :- maplist(lt60_, Ls).

% available operations
add5([L0|Rs], L) :- X #= L0+5, L = [X, L0|Rs].  
add7([L0|Rs], L) :- X #= L0+7, L = [X, L0|Rs].
root([L0|Rs], L) :- isqrt(L0, X), L = [X, L0|Rs].

% base case, the game stops when Ls satisfies all the conditions.
step(Ls) --> { all_different(Ls), order(Ls), lt60(Ls) }.

% building the list
step(Ls) --> [add5(Ls, L)], step(L).
step(Ls) --> [add7(Ls, L)], step(L).
step(Ls) --> [root(Ls, L)], step(L).

该代码发出以下错误，但是我没有试图追踪它或任何东西，因为我确信我使用了不正确的DCG:

The code emits the following error but I haven't tried to trace it or anything because I'm convinced that I'm using DCG incorrectly:

?- phrase(step(L), X).
caught: error(type_error(list,_65),sort/2)

我正在使用Scryer-Prolog，但我认为所有模块也都可以在 swipl 中使用，例如 clpfd 而不是 clpz .

I'm using Scryer-Prolog, but I think all the modules are available in swipl too, like clpfd instead of clpz.

推荐答案

step(Ls) --> [add5(Ls, L)], step(L).

这不能满足您的要求.它描述了形式为 add5(Ls，L)的列表元素.大概在您到达这里时， Ls 已绑定到某个值，但未绑定 L .如果 Ls 是正确格式的非空列表，并且您执行了目标 add5(Ls，L).但是您没有执行此目标.您正在将术语存储在列表中.然后，在 L 完全未绑定的情况下，希望将其绑定到列表的部分代码将引发此错误.大概是 sort/2 调用在 all_different/1 内部.

This doesn't do what you want. It describes a list element of the form add5(Ls, L). Presumably Ls is bound to some value when you get here, but L is not bound. L would become bound if Ls were a non-empty list of the correct form, and you executed the goal add5(Ls, L). But you are not executing this goal. You are storing a term in a list. And then, with L completely unbound, some part of the code that expects it to be bound to a list will throw this error. Presumably that sort/2 call is inside all_different/1.

编辑:此处发布了一些令人惊讶的复杂或低效的解决方案.我认为DCG和CLP在这里都是过分杀伤力的.所以这是一个相对简单快速的方法.为了执行正确的2/10/14顺序，这使用状态参数来跟踪我们以正确的顺序看到的内容:

There are some surprisingly complex or inefficient solutions posted here. I think both DCGs and CLP are overkill here. So here's a relatively simple and fast one. For enforcing the correct 2/10/14 order this uses a state argument to keep track of which ones we have seen in the correct order:

puzzle(Solution) :-
    run([0], seen_nothing, ReverseSolution),
    reverse(ReverseSolution, Solution).
    
run(FinalList, seen_14, FinalList).
run([Head | Tail], State, Solution) :-
    dif(State, seen_14),
    step(Head, Next),
    \+ member(Next, Tail),
    state_next(State, Next, NewState),
    run([Next, Head | Tail], NewState, Solution).
    
step(Number, Next) :-
    (   Next is Number + 5
    ;   Next is Number + 7
    ;   nth_integer_root_and_remainder(2, Number, Next, 0) ),
    Next =< 60,
    dif(Next, Number).  % not strictly necessary, added by request

    
state_next(State, Next, NewState) :-
    (   State = seen_nothing,
        Next = 2
    ->  NewState = seen_2
    ;   State = seen_2,
        Next = 10
    ->  NewState = seen_10
    ;   State = seen_10,
        Next = 14
    ->  NewState = seen_14
    ;   NewState = State ).

在SWI-Prolog上计时:

Timing on SWI-Prolog:

?- time(puzzle(Solution)), writeln(Solution).
% 13,660,415 inferences, 0.628 CPU in 0.629 seconds (100% CPU, 21735435 Lips)
[0,5,12,17,22,29,36,6,11,16,4,2,9,3,10,15,20,25,30,35,42,49,7,14]
Solution = [0, 5, 12, 17, 22, 29, 36, 6, 11|...] .

重复的 member 调用可确保没有重复项占用大量执行时间.使用已访问"表(未显示)可将其减少到大约0.25秒.

The repeated member calls to ensure no duplicates make up the bulk of the execution time. Using a "visited" table (not shown) takes this down to about 0.25 seconds.

进一步缩减并提高了100倍:

Pared down a bit further and made 100x faster:

prev_next(X, Y) :-
    between(0, 60, X),
    (   Y is X + 5
    ;   Y is X + 7
    ;   X > 0,
        nth_integer_root_and_remainder(2, X, Y, 0) ),
    Y =< 60.

moves(Xs) :-
    moves([0], ReversedMoves),
    reverse(ReversedMoves, Xs).
    
moves([14 | Moves], [14 | Moves]) :-
    member(10, Moves).
moves([Prev | Moves], FinalMoves) :-
    Prev \= 14,
    prev_next(Prev, Next),
    (   Next = 10
    ->  member(2, Moves)
    ;   true ),
    \+ member(Next, Moves),
    moves([Next, Prev | Moves], FinalMoves).

?- time(moves(Solution)), writeln(Solution).
% 53,207 inferences, 0.006 CPU in 0.006 seconds (100% CPU, 8260575 Lips)
[0,5,12,17,22,29,36,6,11,16,4,2,9,3,10,15,20,25,30,35,42,49,7,14]
Solution = [0, 5, 12, 17, 22, 29, 36, 6, 11|...] .

可以对移动表进行预先计算(枚举 prev_next/2 的所有解决方案，在动态谓词中声明它们，然后调用它)以获取一两个毫秒的时间.使用CLP(FD)代替直接".算法使SWI-Prolog上的速度大大降低.特别是，在0..60中的 Y，X#= Y * Y 代替了 nth_integer_root_and_remainder/4 目标，这最多需要花费0.027秒的时间.

The table of moves can be precomputed (enumerate all solutions of prev_next/2, assert them in a dynamic predicate, and call that) to gain another millisecond or two. Using a CLP(FD) instead of "direct" arithmetic makes this considerably slower on SWI-Prolog. In particular, Y in 0..60, X #= Y * Y instead of the nth_integer_root_and_remainder/4 goal takes this up to about 0.027 seconds.

这篇关于关于建立符合条件的清单的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！