% Solving a Dr. Ecco's puzzle "Lines of Fire", Dennis E. Shasha, DDJ, July 1998
% http://www.ddj.com/ddj/1998/1998_07/SHAS/SHAS.htm
%


% Load the facts
% ['Lines-of-Fire-DB.prl'].
% and check to see they are properly loaded...
% ?- hill_fires(24,X), print(X), nl, fail.


% all_hills(X) generates a list of all hills, 0 through 24.
% It is a deterministic predicate!

all_hills(X) :- all_hills(0,25,[],X),!.
all_hills(I,I,X,X).
all_hills(I,Imax,C,X) :- I1 is I + 1, all_hills(I1,Imax,[I|C],X).

% ?- all_hills(X), print(X), nl.


% safe_from(Hill,Hills,SafeHills)
% Tell which hills from the list Hills can not be fired upon by a hovertank
% that occupies a given Hill.
% This predicate thus filters the list Hills to leave only hills that can not
% be hit from a Hill
% This is a deterministic predicate!
% We could've made it non-deterministic, but then we had to make sure that all
% the branches below are independent (mutually exclusive). It is easier
% to assume that when one branch is followed, the previous branches
% do not apply. It is easier thus to separate all non-determinism
% in a member() predicate.

safe_from(_,[],[]) :- !.
safe_from(Hill,[Hill|Tail],Remaining) :- !, safe_from(Hill,Tail,Remaining).
safe_from(Hill,[X|Tail],Remaining) :-
	hill_fires(Hill,X), !, safe_from(Hill,Tail,Remaining).
safe_from(Hill,[X|Y],[X|Remaining]) :- safe_from(Hill,Y,Remaining).


% This is the only _non-deterministic_ predicate
member(X,[X|_]).
member(X,[H|T]) :- member(X,T).


% Find out if there are two hills that dominate the valley (that can hit
% all the other hills)?

% ?- nl, print('Looking for two dominant hills'), nl,
  all_hills(Hills),
  member(X,Hills), safe_from(X,Hills,Remaining),
  member(Y,Hills), safe_from(Y,Remaining,[]),
  print([X,Y]),nl.

% ?- nl, print('Looking for three dominant hills'), nl,
  all_hills(Hills),
  member(X,Hills), safe_from(X,Hills,Remaining),
  member(Y,Hills), safe_from(Y,Remaining,R2),
  member(Z,Hills), safe_from(Z,R2,[]),
  print([X,Y,Z]), nl, fail.

% Just a helpful predicate - lists all hills safe from given ones.

all_safe_from(Hills,SafeHills) :- 
	all_hills(AllHills), all_safe_from(Hills,AllHills,SafeHills),!.
all_safe_from([],L,L).
all_safe_from([H|T],Hs,Shs) :-
	safe_from(H,Hs,Sh1), all_safe_from(T,Sh1,Shs).


% list_length_at_least(L,N). Succeed if the size of L is at least N
list_length_at_least(_,0) :- !.
list_length_at_least([H|T],N) :- N1 is N - 1, list_length_at_least(T,N1).

% Looking for two party dominant hills A and B such that if we take
% A and B first and let the enemy take another hill C, then no matter
% what C is (safe from A and B), the enemy can't hit A and B.
% Moreover, we can take another safe hill D and dominate
% the whole valley.

two_partly_dominant_hills :- 
  nl, print('Looking for two partly dominant hills'), nl,
  all_hills(Hills),
  member(A,Hills), safe_from(A,Hills,Remaining),
  member(B,Hills), not(A = B), safe_from(B,Remaining,R2),
  two_partly_dominant_hills(A,B,R2,R2),
  print([A,B]), nl,
  fail.

two_partly_dominant_hills(_,_,_,[]) :- !.
two_partly_dominant_hills(A,B,Hills,[C|T]) :- !,
  not(hill_fires(C,A)), not(hill_fires(C,B)),
  safe_from(C,Hills,R3),
  member(D,R3), safe_from(D,R3,[]),
  all_safe_from([A,B,D],EnemyHills),
  not(list_length_at_least(EnemyHills,5)),
  all_safe_from(EnemyHills,SafeForUs),
  list_length_at_least(SafeForUs,10),!,
  two_partly_dominant_hills(A,B,Hills,T).


% Check the game condition
check_condition(MyHills,EnemyHills,SafeFromEnemy) :- !,
  all_safe_from(MyHills,Available_for_enemy),
  not(list_length_at_least(Available_for_enemy,6)),
  list_length_at_least(SafeFromEnemy,10).


% A deterministic predicate to compute the difference between two lists.
diff(X,[],X) :- !.
diff([],_,[]) :- !.
diff([X|T],[X|T1],Z) :- !, diff(T,T1,Z).
diff([X|T],[_|D],Z) :- member(X,D), !, diff(T,D,Z).
diff([X|T],D,[X|Z]) :- diff(T,D,Z).

% Perform my turn of the game: choose a hill and make sure
% I will eventually win
% (no matter what hills the enemy takes in his turn).

my_turn(MyHills,Safe_from_me,EnemyHills,SafeFromEnemy) :-
  member(X,SafeFromEnemy), not(member(X,MyHills)),
  safe_from(X,Safe_from_me,NewSafe_from_me),
  enemy_turn(NewSafe_from_me,[X|MyHills],
	     NewSafe_from_me,EnemyHills,SafeFromEnemy),
  print_result([X|MyHills],EnemyHills).
	
enemy_turn([],MyHills,Safe_from_me,EnemyHills,SafeFromEnemy) :- !.
	
enemy_turn([X|T],MyHills,Safe_from_me,EnemyHills,SafeFromEnemy) :-
  member(X,EnemyHills), !,
  enemy_turn(T,MyHills,Safe_from_me,EnemyHills,SafeFromEnemy).

enemy_turn([X|T],MyHills,Safe_from_me,EnemyHills,SafeFromEnemy) :-
  !,
  does_not_fire(X,MyHills),
  not(list_length_at_least(EnemyHills,5)),
  safe_from(X,SafeFromEnemy,NewSafeFromEnemy),
  list_length_at_least(NewSafeFromEnemy,10), !,
  % nl, print('my turn on:'),print(MyHills), print(X),
  my_turn(MyHills,Safe_from_me,[X|EnemyHills],NewSafeFromEnemy), !,
  enemy_turn(T,MyHills,Safe_from_me,EnemyHills,SafeFromEnemy).

% does_not_fire(Hill,List) succeeds if Hill does not fire
% on any of the hills in the List
does_not_fire(_,[]) :- !.
does_not_fire(Hill,[Hill|T]) :- !, fail.
does_not_fire(Hill,[H|T]) :- !, 
  not(hill_fires(Hill,H)), does_not_fire(Hill,T).

print_result([X],EnemyHills) :- !, nl, print([X]), print(EnemyHills).
print_result([X,Y],EnemyHills) :- !, nl, print([X,Y]), print(EnemyHills).
% print_result([X,Y,Z],EnemyHills) :- !, nl, print([X,Y,Z]), print(EnemyHills).
print_result(_,_).

% Find a winning strategy if I'm allowed to take two hills on the first move

main :- 
  all_hills(Hills),
  member(My1,Hills), safe_from(My1,Hills,Remaining),
  my_turn([My1],Remaining,[],Hills),
  fail.

% Find a winning strategy if I'm allowed to take only one hill
% on the first move
main1 :- all_hills(Hills), my_turn([],Hills,[],Hills).


% Proof that for each distinct X and Y there exist such distinct E1 and E2 that
%  - E1 and E2 are distinct from X and Y
%  - X does not hit E1 nor E2; Y does not hit E2 nor E2
% and either
%  E1 hits X or Y
%  E2 hits X or Y
%  the list of hills that cannot be hit from E1 and E2 is shorter than 10
%  
main_aff :- all_hills(Hills), for_each(Hills,Hills).

for_each([],_).
for_each([X|T],Hills) :- !, for_each(Hills,X,Hills), !, for_each(T,Hills).

for_each([],_,_).
for_each([X|T],X,Hills) :- !, for_each(T,X,Hills).
for_each([Y|T],X,Hills) :- !, 
  find_two_enemy_hills(X,Y,Hills), !, for_each(T,X,Hills).

find_two_enemy_hills(X,Y,Hills) :-
  member(E1,Hills), not(X = E1), not(hill_fires(X,E1)),
  % nl, print('E1: '), print(E1),
  (hill_fires(E1,X);
   hill_fires(E1,Y);
   not(E1 = Y), find_two_enemy_hills(X,Y,E1,Hills)).

find_two_enemy_hills(X,Y,E1,Hills) :-
  member(E2,Hills), not(E2 = E1), not(E2 = X), 
  not(E2 = Y), not(hill_fires(X,E2)), not(hill_fires(Y,E2)),
  % nl, print('E2: '), print(E2),
  (hill_fires(E2,X); hill_fires(E2,Y); 
   all_safe_from([E1,E2],SafeForUs),
      not(list_length_at_least(SafeForUs,10)),
      nl, print([X,Y,E1,E2]), print(' '), print(SafeForUs)
  ).

	
% unknown(X,trace).