/***************************/
/*                         */
/* Answers to worksheet 13 */
/*                         */
/***************************/

/* Exercise 13.1 Censorship                                       */

censored(bother).
censored(drat).
censored(damned).
censored(blast).
censored(fiddlesticks).

beep([], []).
beep([W|Ws], [beep|Cs]) :-
   censored(W),
   beep(Ws, Cs).

beep([W|Ws], [W|Cs]) :-
   \+ censored(W),
   beep(Ws, Cs).

/* Exercise 13.2 Sets                                             */

setMember(X, [X|Xs]).
setMember(X, [Y|Ys]) :- setMember(X, Ys).

setInsert(X, Xs, [X|Xs]) :-
   \+ setMember(X, Xs).

setInsert(X, Xs, Xs) :-
   setMember(X, Xs).

setDelete(X, [X|Xs], Xs).
setDelete(X, [Y|Ys], [Y|Zs] ) :-
   setDelete(X, Ys, Zs).

subset([], Xs).
subset([X|Xs], Ys) :- setMember(X, Ys),
                      subset(Xs, Ys).

setEquals(Xs, Ys) :- subset(Xs, Ys), subset(Ys, Xs).

setUnion([], Xs, Xs).
setUnion([X|Xs], Ys, Zs) :-
   setInsert(X, Ys, XYs), setUnion(Xs, XYs, Zs).

setIntersect([], Ys, []).
setIntersect([X|Xs], Ys, [X|Zs]) :-
   setMember(X, Ys), setIntersect(Xs, Ys, Zs).
setIntersect([X|Xs], Ys, Zs) :-
   \+ setMember(X, Ys), setIntersect(Xs, Ys, Zs).

setDiff([], Ys, []).
setDiff([X|Xs], Ys, [X|Zs]) :-
   \+ setMember(X, Ys), setDiff(Xs, Ys, Zs).
setDiff([X|Xs], Ys, Zs) :-
   setMember(X, Ys), setDiff(Xs, Ys, Zs).

/* The problem with setInsert (and setUnion) is when all arguments*/
/* are instantiated: sometimes this will give wrong answers. For  */
/* example, this is right:                                        */
/* ?- setInsert(a, [b, c], [a, b, c]).                            */
/* Prolog correctly returns yes.                                  */
/* But, for this example                                          */
/* ?- setInsert(a, [b, c], [b, c, a]).                            */
/* Prolog incorrectly returns no. (Since sets are not ordered,    */
/* we really want the answer yes.)                                */


/* Exercise 13.3 Planner                                          */

action(move(door, shelf), [at(door), on(floor)], [at(shelf)], [at(door)]).
action(move(shelf, door), [at(shelf), on(floor)], [at(door)], [at(shelf)]).
action(climb(floor, box), [at(shelf), on(floor)], [on(box)], [on(floor)]). 
action(climb(box, floor), [on(box)], [on(floor)], [on(box)]).              
action(get(honey, shelf), [on(box)], [have(honey)], []).                  


forwards(InitialState, GoalState, FinalActions) :- 
   forwards(InitialState, GoalState, [], FinalActions).

forwards(CurrentState, GoalState, RevActions, FinalActions) :- 
   subset(GoalState, CurrentState),
   reverse(RevActions, FinalActions).

forwards(CurrentState, GoalState, RevActions, FinalActions) :-
   action(H, P, A, D),
   \+ setMember(H, RevActions), 
   subset(P, CurrentState),
   fapply(A, D, CurrentState, NewState),
   forwards(NewState, GoalState, [H|RevActions], FinalActions).

fapply(A, D, I, N) :-
   setUnion(A, I, Int),
   setDiff(Int, D, N).

backwards(InitialState, GoalState, FinalActions) :-
   backwards(InitialState, GoalState, [], FinalActions).

backwards(InitialState, CurrentState, FinalActions, FinalActions) :-
   subset(CurrentState, InitialState).

backwards(InitialState, CurrentState, Actions, FinalActions) :-
   action(H, P, A, D),
   \+ setMember(H, Actions), 
   setIntersect(A, CurrentState, [E|Es]),
   bapply(P, A, D, CurrentState, NewState),
   backwards(InitialState, NewState, [H|Actions], FinalActions).

bapply(P, A, D, CurrentState, NewState) :-
   setDiff(CurrentState, A, Int),
   setUnion(Int, P, NewState).

reverse([], []).
reverse([H|T], R) :- reverse(T, N), append(N, [H], R).

append([], Xs, Xs).
append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).

/* Exercise 13.4 Achin' Hearts                                    */

person(case1, [pop, walks, cinema]).
person(case2, [walks]).
person(case3, [scifibooks, roleplaygames, festeringanoraks]).

mightDate(Person1, Person2) :-
   person(Person1, Ints1),
   person(Person2, Ints2),
   \+ (member(I, Ints1),
      \+ (member(I, Ints2))).

wildParty(People1, People2) :-
   combined_interests(People1, P1Ints),
   combined_interests(People2, P2Ints),
   \+ (member(I, P2Ints),
      \+ (member(I, P1Ints))).

combined_interests([], []).
combined_interests([P|Ps], PPInts) :-
  person(P, Ints),
  combined_interests(Ps, PInts),
  append(Ints, PInts, PPInts).

member(X, [X|Xs]).
member(X, [Y|Ys]) :- member(X, Ys).


/* Exercise 13.5                                                    */

/* If there is a fact giraffe(gertie), the first definition returns */
/* X = gertie, i.e. it makes a binding; the second doesn't.         */
/* If there is no such fact, both return no.                        */

check_for_giraffes1(X) :-
  giraffe(X).

check_for_giraffes2(X) :-
  \+ ( \+ giraffe(X)).

/* Hence, the second is a good way of checking for existence ---    */
/* WITHOUT CAUSING BINDINGS TO BE FORMED.                           */



/* Exercise 13.6                                                    */

filter(P, [], []).
filter(P, [X|Xs], [X|Ys]) :- 
   Goal =.. [P, X], call(Goal), 
   filter(P, Xs, Ys).
filter(P, [X|Xs], Ys) :- 
   Goal =.. [P, X], call(\+ Goal), 
   filter(P, Xs, Ys).
                        


/* Exercise 13.7                                                    */

intersect(Xs, Ys, Zs) :- 
   findall(X, (member(X, Xs), member(X, Ys)), Zs).

member(X, [X|Xs]).
member(X, [Y|Ys]) :- member(X, Ys).