 Olian04
10/28/2016 - 1:17 PM

## spider.plg

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