10/28/2016 - 1:17 PM


/* 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).