/* Author: Oliver Linnarsson, Johan Parö */
% if A knows B then B knows A.
% knows_sym(Source1, Source2).
knows_sym(X,Y) :- knows(X,Y); knows(Y,X). % recursive call to test the next person.
% finds the Spider
% spider(Source).
spider(Spider) :-
person(Spider), % Spider has to be a person.
isSpider(Spider). % test if Spider is the spider.
% Finds a subset of all people where Spider is the spider.
% isSpider(Source).
isSpider(Spider) :-
findall(X, (person(X), X \= Spider, knows_sym(Spider, X)), AllPPL), % find all ppl thats not the spider
subset(AllPPL, SubsetPPL), % find A subset of ppl, (will eventually find ALL subsets)
\+ isStranger(SubsetPPL, _), !. % Every person has to know someone in the subset.
% no one in [H|T] knows Stranger.
% isStranger(Origin, Source).
isStranger([],_). % we are done
isStranger([H|T], Stranger) :-
person(H), % H has to be a person
person(Stranger), % Stranger has to be a person
H \= Stranger, % H can not be the starger itself
\+ knows_sym(H, Stranger), % H can not know the Stranger
isStranger(T, Stranger).
% returns all subsets of a set [H|T].
% subset(Origin, Subset).
subset([], []).
subset([H|T], [H|TL]) :- % leads to a case where H is a conspirator
makeStranger(T, R, H), % removes a person from the input list, if someone he knows is chosen to be tested as a conspirator.
subset(R, TL).
subset([H|T], TL) :-
\+ isStranger(T, H), % makes shure that H knows atleast one in T, since every one not in the subset is a normal, and every normal has to know a cnospirator.
% does not need to check if H knows any one in TL, because if he didnt, he would already be part of TL.
subset(T, TL).
% makeStranger(Origin, Return, Source).
makeStranger([], [], _).
makeStranger([H|T], [H|TL], ToBeStranger) :-
\+ knows_sym(H, ToBeStranger), % H does not know ToBeStranger -> Include H in Return
makeStranger(T, TL, ToBeStranger).
makeStranger([H|T], TL, ToBeStranger) :-
knows_sym(H, ToBeStranger), % H knows ToBeStranger -> Exclude H from Return
makeStranger(T, TL, ToBeStranger).