The Game of Life (invented by J. H. Conway)

% e.g. life([[1,3],[2,1],[2,3],[3,2],[3,3]], 14, 14, X).
%      life([[7,9],[7,10],[7,11],[7,12],[7,13],[7,14]], 14, 23, X),
% On backtracking, successive generations are created and displayed
% It is required, but not verified, that the initial occupied cells be ordered
life(Living, Rows, Cols, Living):-
  show(1, Rows, 1, Cols, Living).
life(Living0, Rows, Cols, Living):-
  counts_of_living_neighbours(Living0, Living0, Ms),
  dead_neighbours(Living0, Living0, [], DeadNeighbours),
  counts_of_living_neighbours(DeadNeighbours, Living0, Ns),
  filter_living(Ms, Living0, Living1),
  filter_dead_neighbours(Ns, DeadNeighbours, Living2),
  ord_union(Living1, Living2, Living3),
  life(Living3, Rows, Cols, Living).

% Finds all empty cells neighbouring the given cells
dead_neighbours([], _, DeadNeighbours, DeadNeighbours).
dead_neighbours([Cell|Cells], Living, DeadNeighbours0, DeadNeighbours):-
  findall(X, dead_neighbour(Cell, Living, X), DeadNeighbours1),
  ord_union(DeadNeighbours0, DeadNeighbours1, DeadNeighbours2),
  dead_neighbours(Cells, Living, DeadNeighbours2, DeadNeighbours).

% On backtracking finds each empty cell neighbouring the given cell
dead_neighbour(Cell, Living, DeadNeighbour):-
  neighbour(Cell, DeadNeighbour),
  \+ member(DeadNeighbour, Living).
  
% Finds the number of occupied cells neighbouring each given cell
counts_of_living_neighbours([], _, []).
counts_of_living_neighbours([Cell|Cells], Living, [N|Ns]):-
  findall(X, living_neighbour(Cell, Living, X), LivingNeighbours),
  length(LivingNeighbours, N),
  counts_of_living_neighbours(Cells, Living, Ns).

% On backtracking finds each occupied cell neighbouring the given cell    
living_neighbour(Cell, Living, LivingNeighbour):-
  neighbour(Cell, LivingNeighbour),
  member(LivingNeighbour, Living).
  
% On backtracking finds each neighbour of the given cell  
neighbour([R,C], [R1,C1]):-R1 is R - 1, C1 is C - 1.
neighbour([R,C], [R1, C]):-R1 is R - 1.
neighbour([R,C], [R1,C1]):-R1 is R - 1, C1 is C + 1.
neighbour([R,C], [R ,C1]):-C1 is C - 1.
neighbour([R,C], [R ,C1]):-C1 is C + 1.
neighbour([R,C], [R1,C1]):-R1 is R + 1, C1 is C - 1.
neighbour([R,C], [R1, C]):-R1 is R + 1.
neighbour([R,C], [R1,C1]):-R1 is R + 1, C1 is C + 1.

% Finds those occupied cells which will survive into the next generation
filter_living([], [], []).
filter_living([2|Ns], [Cell|Cells], [Cell|Living]):-!,
  filter_living(Ns, Cells, Living).
filter_living([3|Ns], [Cell|Cells], [Cell|Living]):-!,
  filter_living(Ns, Cells, Living).
filter_living([_|Ns], [_|Cells], Living):-
  filter_living(Ns, Cells, Living).

% Finds those empty cells which will be occupied in the next generation
filter_dead_neighbours([], [], []).
filter_dead_neighbours([3|Ns], [Cell|Cells], [Cell|Living]):-!,
  filter_dead_neighbours(Ns, Cells, Living).
filter_dead_neighbours([_|Ns], [_|Cells], Living):-
  filter_dead_neighbours(Ns, Cells, Living).

% Displays the current generation
show(R, Rows, _, _, _):-
  R > Rows, !.
show(R, Rows, C, Cols, Living):-
  C > Cols, !,
  nl,
  R1 is R + 1,
  show(R1, Rows, 1, Cols, Living).
show(R, Rows, C, Cols, [[R,C]|Living]):-!,
  C1 is C + 1,
  write('#'),
  show(R, Rows, C1, Cols, Living).
show(R, Rows, C, Cols, [Cell|Living]):-
  less_than(Cell, [R,C]), !,
  C1 is C + 1,
  write('.'),
  show(R, Rows, C1, Cols, Living).
show(R, Rows, C, Cols, Living):-
  C1 is C + 1,
  write('.'),
  show(R, Rows, C1, Cols, Living).

/* length(Xs, L) is true if L is the number of elements in the list Xs.    */
%length(Xs, L):-length_1(Xs, 0, L).

/* length_1(Xs, L0, L) is true if L is equal to L0 plus the number of      */
/*   elements in the list Xs.                                              */
%length_1([], L, L).
%length_1([_|Xs], L0, L):-L1 is L0 + 1, length_1(Xs, L1, L).

/* member(X, Xs) is true if the element X is contained in the list Xs.     */
%member(X, [X|_]).
%member(X, [_|Xs]):-member(X, Xs).

/* ord_union(Set1, Set2, Union) is true if Set1 and Set2 are the ordered   */
/*   representations of two sets and Union is unified with the ordered     */
/*   representation of their union.                                        */
ord_union([], Ys, Ys). 
ord_union([X|Xs], [], [X|Xs]). 
ord_union([X|Xs], [X|Ys], [X|Zs]):-!, 
  ord_union(Xs, Ys, Zs).
ord_union([X|Xs], [Y|Ys], [X|Zs]):-
  less_than(X, Y), !, 
  ord_union(Xs, [Y|Ys], Zs).
ord_union([X|Xs], [Y|Ys], [Y|Zs]):-
  ord_union([X|Xs], Ys, Zs).
  
less_than([A,_], [C,_]):-A < C, !.
less_than([A,B], [A,D]):-B < D.

LPA Index     Home Page

Valid HTML 4.01 Strict