%% -*- prolog -*-

%%% Solve some simple symbolic & list processing problems.

%% Given a directed graph; find path from vertex v1 to vertex v2.

%% Representation of graph?

%% vertices v1, ..., v7

% vertex(v1).
% vertex(v2).
% ...

vertex(V) :- member(V, [v1,v2,v3,v4,v5,v6,v7]).

%%

% edge(v1,v2). 			% edge from v1 to v2
% edge(v2,v3).
% ...

edge(V,U) :- member([V,U],
		    [[v1,v2], [v2,v3], [v3,v4], [v4,v5], [v5,v6], [v6,v7], [v7,v1],
		     [v1,v4],[v2,v5],[v3,v6],[v4,v7],[v5,v1],[v6,v2],[v7,v3]]).

% path([v1,v4,v5,v1]) is true because there is a path: v1 -> v4 -> v5 -> v1.
% By (our) definition, a path must contain at least one vertex.
% One vertex path *is* allowed.

% special case for path of length 1.
path([V]) :- vertex(V).

%% alternatives:

% path([V,U]) :- vertex(V), vertex(U), edge(V,U).

%% special cases for paths of length 2, 3, 4
% path([V,U]) :- edge(V,U).
% path([V,U,T]) :- edge(V,U), edge(U,T).
% path([V,U,T,S]) :- edge(V,U), edge(U,T), edge(T,S).

%% general case, for paths of length >=2
path([V,U|P]) :- edge(V,U), path([U|P]).

%% predefined:
% '='(X,X).

%  A=B    ---syntactic-suger---->   '='(A,B)

%%% The game of Nim!
%%% Players alternate taking 1/2/3 pebbles from any of 3 piles.
%%% Whoever takes the last pebble wins.

%%% obvious representation of board: board(3,4,7).
%%% instead using board([x,x,x],[x,x,x,x],[x,x,x,x,x,x,x]).

won(board([],[],[])).
%% move(B1,B2) means player can make move on board B1 yielding board B2

move(board(P,P2,P3), board(Q,P2,P3)) :- stonesoff(P,Q).
move(board(P1,P,P3), board(P1,Q,P3)) :- stonesoff(P,Q).
move(board(P1,P2,P), board(P1,P2,Q)) :- stonesoff(P,Q).

%% stonesoff(P,Q) means Q is result of removing 1/2/3 stones from P.
%% all stones are x
stonesoff([x|Q],Q).
stonesoff([x,x|Q],Q).
stonesoff([x,x,x|Q],Q).

%%% Machinery: CUT, written !

not(G) :- G, !, fail.
not(_).