コンウェイのライフゲームのための最もプロローグの実装は何ですか？

Question

私は今晩（次のように）バージョンを鳴らしましたが、別の手続き型言語から移植したような気がしていて、多くの「純粋な」Prologの機能を利用していませんでした。

これを実行して、次の世代のためにEnterを押してください。

はプロローグの問題を攻撃するときに私は気づいたHere

ことの一つは（も99時間の％）すっきり実装常に存在することである（ラビリンス割合の）バージョンがあり、そしてそれはだようにそれは感じています今回はこのケース。

あなたが考えるより優れた実装方法はありますか？私は私のことに満足していません。それは動作し、ひどく非効率的ではありませんが（？）、まだ...

私は統一をより良く利用できるようです。私が個々にチェックした特定のセルに対してX、Yの座標として隣人を扱う代わりに、私は何とかPrologに私のために何かをさせることができました。

% Conway Game of Life (Stack Overflow, 'magus' implementation) 

% The life grid, 15x15 
grid([ 
     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
     [0,0,0,0,0,1,0,1,0,1,0,0,0,0,0], 
     [0,0,0,0,0,1,0,0,0,1,0,0,0,0,0], 
     [0,0,0,0,0,1,0,0,0,1,0,0,0,0,0], 
     [0,0,0,0,0,1,0,0,0,1,0,0,0,0,0], 
     [0,0,0,0,0,1,0,1,0,1,0,0,0,0,0], 
     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
    ] 
    ). 

% Infinite generates sep with keystroke 
% ------------------------------------- 
life(Grid) :- 
    dumpgen(Grid), 
    onegen(Grid, 0, NewGrid), 
    get_single_char(_), 
    life(NewGrid). 


% Dumps a generation out 
% ---------------------- 
dumpgen([]) :- nl. 
dumpgen([H|T]) :- 
    write(H), nl, 
    dumpgen(T). 

% Does one generation 
% -------------------------------- 
onegen(_, 15, []). 

onegen(Grid, Row, [NewRow|NewGrid]) :- 
    xformrow(Grid, Row, 0, NewRow), 
    NRow is Row + 1, 
    onegen(Grid, NRow, NewGrid). 

% Transforms one row 
% -------------------------------- 
xformrow(_, _, 15, []). 
xformrow(Grid, Row, Col, [NewState|NewList]) :- 
    xformstate(Grid, Row, Col, NewState), 
    NewCol is Col + 1, 
    xformrow(Grid, Row, NewCol, NewList). 


% Request new state of any cell 
% -------------------------------- 
xformstate(Grid, Row, Col, NS) :- 
    cellstate(Grid, Row, Col, CS), 
    nextstate(Grid, Row, Col, CS, NS). 

% Calculate next state of any cell 
% -------------------------------- 

% Cell is currently dead 
nextstate(Grid, Row, Col, 0, NS) :- 
    neightotal(Grid, Row, Col, Total), 
    (Total =:= 3 -> NS = 1 ; NS = 0). 

% Cell is currently alive 
nextstate(Grid, Row, Col, 1, NS) :- 
    neightotal(Grid, Row, Col, Total), 
    ((Total =:= 2; Total =:=3) 
    -> NS = 1; NS = 0). 

% State of all surrounding neighbours 
%------------------------------------- 
neightotal(Grid, Row, Col, TotalSum) :- 

    % Immediately neighbours X, Y 
    XM1 is Col - 1, 
    XP1 is Col + 1, 
    YM1 is Row - 1, 
    YP1 is Row + 1, 

    % State at all those compass points 
    cellstate(Grid, YM1, Col, N), 
    cellstate(Grid, YM1, XP1, NE), 
    cellstate(Grid, Row, XP1, E), 
    cellstate(Grid, YP1, XP1, SE), 
    cellstate(Grid, YP1, Col, S), 
    cellstate(Grid, YP1, XM1, SW), 
    cellstate(Grid, Row, XM1, W), 
    cellstate(Grid, YM1, XM1, NW), 

    % Add up the liveness 
    TotalSum is N + NE + E + SE + S + SW + W + NW. 


% State at any given row/col - 0 or 1 
% ----------------------------------- 
% Valid range, return it's state 
cellstate(Grid, Row, Col, State) :- 
    between(0, 14, Row), 
    between(0, 14, Col), 
    nth0(Row, Grid, RL), 
    nth0(Col, RL, State). 

% Outside range is dead 
cellstate(_, _, _, 0). 

実行：

[debug] ?- grid(X), life(X). 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,1,0,1,0,1,0,0,0,0,0] 
[0,0,0,0,0,1,0,0,0,1,0,0,0,0,0] 
[0,0,0,0,0,1,0,0,0,1,0,0,0,0,0] 
[0,0,0,0,0,1,0,0,0,1,0,0,0,0,0] 
[0,0,0,0,0,1,0,1,0,1,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 

[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,1,0,1,0,0,0,0,0,0] 
[0,0,0,0,1,1,0,0,0,1,1,0,0,0,0] 
[0,0,0,0,1,1,1,0,1,1,1,0,0,0,0] 
[0,0,0,0,1,1,0,0,0,1,1,0,0,0,0] 
[0,0,0,0,0,0,1,0,1,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 

[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,1,0,0,0,1,0,0,0,0,0] 
[0,0,0,0,1,0,0,0,0,0,1,0,0,0,0] 
[0,0,0,1,0,0,1,0,1,0,0,1,0,0,0] 
[0,0,0,0,1,0,0,0,0,0,1,0,0,0,0] 
[0,0,0,0,0,1,0,0,0,1,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 

etc. 

Answer 1

私はロジックのシンプルさは、最も単純なデータ構造のために主張し、それが他の言語に類似し終わると思います。

しかし、仮に、SWI-Prologが提供する無制限の精度の整数とビットフィールド演算子を使用すると、行が整数になり、セルの状態をテストすることができます。下位ビットをマスキングする：我々は考慮すべき9ビット、すなわち512個の値を事前に計算することができる。もちろん、境界のチェックはアルゴリズムを複雑にする可能性があります：いくつかの 'アウトオブバンド'パディングが役に立ちます。

これは簡単に行う必要があります。

編集：ここに私の努力：あなたの時間チャックモールのための

% Conway Game of Life (Stack Overflow, 'chac' implementation) 
% 

:- module(lifec, [play/0]). 

play :- 
    grid(G), 
    lifec(G). 

% The life grid, 15x15 
grid([ 
     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
     [0,0,0,0,0,1,0,1,0,1,0,0,0,0,0], 
     [0,0,0,0,0,1,0,0,0,1,0,0,0,0,0], 
     [0,0,0,0,0,1,0,0,0,1,0,0,0,0,0], 
     [0,0,0,0,0,1,0,0,0,1,0,0,0,0,0], 
     [0,0,0,0,0,1,0,1,0,1,0,0,0,0,0], 
     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], 
     [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] 
    ] 
    ). 

% Infinite generates sep with keystroke 
% ------------------------------------- 
lifec(Grid) :- 
    make_ints(Grid, Ints, Size), 
    lifei(Ints, Size). 

lifei(Ints, Size) :- 
    dumpgen(Ints, Size), 
    onegen(Ints, Size, NewInts), 
    get_single_char(_), 
    !, lifei(NewInts, Size). 

dumpgen(Ints, Size) :- 
    forall(member(I, Ints), 
      (for_next(1, Size, _, show_bit(I)), nl)). 

onegen(Matrix, Size, NewMatrix) :- 
    findall(NewBits, 
     (three_rows(Matrix, Size, Rows), 
     rowstate(Rows, 0, Size, 0, NewBits)), NewMatrix). 

three_rows(Matrix, Size, Rows) :- 
    nth1(I, Matrix, Row), 
    (I > 1 -> U is I - 1, nth1(U, Matrix, Up) ; Up = 0), 
    (I < Size -> D is I + 1, nth1(D, Matrix, Down) ; Down = 0), 
    % padding: add 0 bit to rightmost position 
    maplist(lshift, [Up, Row, Down], Rows). 

:- dynamic evopatt/2. 

rowstate([_, _, _], Size, Size, NewBits, NewBits) :- !. 
rowstate([U, R, D], I, Size, Accum, Result) :- 
    Key is (U /\ 7) \/ ((R /\ 7) << 3) \/ ((D /\ 7) << 6), 
    evopatt(Key, Bit), 
    Accum1 is Accum \/ (Bit << I), 
    maplist(rshift, [U,R,D], P), 
    J is I + 1, 
    rowstate(P, J, Size, Accum1, Result). 

%% initialization 
% 
make_ints(Grid, Ints, Size) :- 
    length(Grid, Size), 
    maplist(set_bits(0, 0), Grid, Ints), 
    % precompute evolution patterns 
    retractall(evopatt(_, _)), 
    for_next(0, 511, _, add_evopatt). 

add_evopatt(N) :- 
    maplist(take_bit(N), [0,1,2], U), 
    maplist(take_bit(N), [3,4,5], V), 
    maplist(take_bit(N), [6,7,8], Z), 
    rule(U, V, Z, Bit), 
    assert(evopatt(N, Bit)). 

% rules from Rosetta Code 
% 
rule([A,B,C],[D,0,F],[G,H,I],1) :- A+B+C+D+F+G+H+I =:= 3. 
rule([_,_,_],[_,0,_],[_,_,_],0). 
rule([A,B,C],[D,1,F],[G,H,I],0) :- A+B+C+D+F+G+H+I < 2. 
rule([A,B,C],[D,1,F],[G,H,I],1) :- A+B+C+D+F+G+H+I =:= 2. 
rule([A,B,C],[D,1,F],[G,H,I],1) :- A+B+C+D+F+G+H+I =:= 3. 
rule([A,B,C],[D,1,F],[G,H,I],0) :- A+B+C+D+F+G+H+I > 3. 

%% utilities 
% 
:- meta_predicate for_next(+,+,-,1). 

for_next(From, To, N, Pred) :- 
    forall(between(From, To, N), call(Pred, N)). 

lshift(X, Y) :- Y is X << 1. 
rshift(X, Y) :- Y is X >> 1. 

show_bit(I, P) :- 
    take_bit(I, P - 1, 1) -> put(0'*) ; put(0'). 

take_bit(N, Pos, Bit) :- 
    Bit is (N >> Pos) /\ 1. 

set_bits(_Index, Accum, [], Accum). 
set_bits(Index, Accum, [ZeroOne|Rest], Number) :- 
    Accum1 is Accum \/ (ZeroOne << Index), 
    Index1 is Index + 1, 
    set_bits(Index1, Accum1, Rest, Number).