/* 

  Party attendance problem in Picat.

  https://iggyfernandez.wordpress.com/2012/05/21/sql-vs-nosql-third-international-nocoug-sql-nosql-challenge-sponsored-by-pythian/
  """
  Burdock Muldoon and Carlotta Pinkstone both said they would come if Albus Dumbledore came. 
  Albus Dumbledore and Daisy Dodderidge both said they would come if Carlotta Pinkstone came. 
  Albus Dumbledore, Burdock Muldoon, and Carlotta Pinkstone all said they would come 
  if Elfrida Clagg came. 
  Carlotta Pinkstone and Daisy Dodderidge both said they would come if Falco Aesalon came. 
  Burdock Muldoon, Elfrida Clagg, and Falco Aesalon all said they would come 
  if Carlotta Pinkstone and Daisy Dodderidge both came. 
  Daisy Dodderidge said she would come if Albus Dumbledore and Burdock Muldoon both came. 

  Whom is needs to be persuaded to attend the party in order to ensure that 
  all her invitees attend?
  """

  Via 
  http://cs.stackexchange.com/questions/2031/can-constraint-satisfaction-problems-be-solved-with-prolog 

  Note: This model just care about single invites.

  Here are two approaches, one CP and one translated from Prolog.
  Both give the same solution, i.e. that either one of these can 
  be invited to get all to the party:

     Albus Dumbledore
     Carlotta Pinkstone
     Elfrida Clagg
     Falco Aesalon

  represented as [ad,cp,ec,fa] in the Prolog based solution.

  More problems (see below) and answers:
  
   http://www.nocoug.org/download/2012-05/Third%20International%20NoCOUG%20SQL%20&%20NoSQL%20Challenge%20%28Additional%20Rules%29


  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import util.
import cp.

main => go.

%
% Answers:
% a. Albus Dumbledore
% b. Carlotta Pinkstone
% c. Elfrida Clagg
% d. Falcon Aesalon
%
go ?=>
  nolog,
  % who will attend the party
  Albus_Dumbledore :: 0..1,
  Burdock_Muldoon :: 0..1,
  Carlotta_Pinkstone :: 0..1,
  Daisy_Dodderidge :: 0..1,
  Elfrida_Clagg :: 0..1,
  Falco_Aesalon :: 0..1,

  People = [Albus_Dumbledore,Burdock_Muldoon,Carlotta_Pinkstone,
            Daisy_Dodderidge,Elfrida_Clagg,Falco_Aesalon],
    
  Names = ["Albus Dumbledore","Burdock Muldoon","Carlotta Pinkstone",
           "Daisy Dodderidge","Elfrida Clagg","Falco Aesalon"],

  % Burdock Muldoon and Carlotta Pinkstone both said they would come if Albus Dumbledore came. 
  Albus_Dumbledore #=> Burdock_Muldoon,
  Albus_Dumbledore #=> Carlotta_Pinkstone,

  % Albus Dumbledore and Daisy Dodderidge both said they would come if Carlotta Pinkstone came. 
  Carlotta_Pinkstone #=> Albus_Dumbledore,
  Carlotta_Pinkstone #=> Daisy_Dodderidge, 

  % Albus Dumbledore, Burdock Muldoon, and Carlotta Pinkstone all said they would come if 
  % Elfrida Clagg came. 
  Elfrida_Clagg #=> Albus_Dumbledore,
  Elfrida_Clagg #=> Burdock_Muldoon,
  Elfrida_Clagg #=> Carlotta_Pinkstone,

  % Carlotta Pinkstone and Daisy Dodderidge both said they would come if Falco Aesalon came. 
  Falco_Aesalon #=> Carlotta_Pinkstone, 
  Falco_Aesalon #=> Daisy_Dodderidge, 

  % Burdock Muldoon, Elfrida Clagg, and Falco Aesalon all said they would come if 
  % Carlotta Pinkstone and Daisy Dodderidge both came. 
  (Carlotta_Pinkstone #/\ Daisy_Dodderidge) #=> Burdock_Muldoon,
  (Carlotta_Pinkstone #/\ Daisy_Dodderidge) #=> Elfrida_Clagg,
  (Carlotta_Pinkstone #/\ Daisy_Dodderidge) #=> Falco_Aesalon,

  % Daisy Dodderidge said she would come if Albus Dumbledore and Burdock Muldoon both came. 
  (Albus_Dumbledore #/\ Burdock_Muldoon) #=> Daisy_Dodderidge,

  % Whom is needs to be persuaded to attend the party in order to ensure that 
  % all her invitees attend?

  %
  % invite exactly one person
  % 
  member(Persuaded,1..People.len),
  People[Persuaded] #= 1,

  % Check for unique solutions
  Sols = solve_all($[split],People),
  if Sols.len == 1 then
    println(persuaded=Names[Persuaded])
  else
    true
    % println(nope=[Names[Persuaded],sols=Sols]),
  end,

  fail,

  nl.

go => true.



go1b ?=>
  Names = ["Albus Dumbledore","Burdock Muldoon","Carlotta Pinkstone",
           "Daisy Dodderidge","Elfrida Clagg","Falco Aesalon"],
  N = Names.len,
  L = 1..N,
  L = [A,B,C,D,E,F],

  Logic = 
  [
  % Burdock Muldoon and Carlotta Pinkstone both said they would come if Albus Dumbledore came. 
  [[A],[B]],
  [[A],[C]],

  % Albus Dumbledore and Daisy Dodderidge both said they would come if Carlotta Pinkstone came. 
  [[C],[A]],
  [[C],[D]],

  % Albus Dumbledore, Burdock Muldoon, and Carlotta Pinkstone all said they would come if 
  % Elfrida Clagg came. 
  [[E],[A]],
  [[E],[B]],
  [[E],[C]],

  % Carlotta Pinkstone and Daisy Dodderidge both said they would come if Falco Aesalon came. 
  [[F],[C]],
  [[F],[D]],

  % Burdock Muldoon, Elfrida Clagg, and Falco Aesalon all said they would come if 
  % Carlotta Pinkstone and Daisy Dodderidge both came. 
  [[C,D],[B]],
  [[C,D],[E]],
  [[C,D],[F]],

  % Daisy Dodderidge said she would come if Albus Dumbledore and Burdock Muldoon both came. 
  [[A,B],[D]]
  ],

  % Whom is needs to be persuaded to attend the party in order to ensure that 
  % all her invitees attend?

  %
  % get minimum required
  %
  party2(Names,Logic, NumRequired,_People,_Persuaded,_NumAttending),
  println(numRequired=NumRequired),
  % println(people=People),
  % println(persuaded=Persuaded),

  All = find_all([Persuaded,People],party2(Names,Logic, NumRequired,People,Persuaded,NumAttending)).sort_down(),
  Count = new_map(),
  foreach([Persuaded,People] in All)
    Count.put(Persuaded,Count.get(Persuaded,0)+1)
  end,

  foreach(PP=CC in Count)
    if CC == 1 then
      println(name=[Names[I] : I in 1..N, PP[I] == 1])
    end
  end,


  nl.


%
% Dataset 2 (see below)
% 1. Carlotta Pinkstone will come if Albus Dumbledore and Burdock Muldoon both come
% 2. Falco Aesalon will come if Daisy Dodderidge and Elfrida Clagg both come
% 
% Answers
% a. Albus Dumbledore, Burdock Muldoon, Daisy Dodderidge, and Elfrida Clagg
%
go2 =>
  Names = ["Albus Dumbledore","Burdock Muldoon", "Carlotta Pinkstone",
           "Daisy Dodderidge","Elfrida Clagg","Falco Aesalon"],
  N = Names.len,
  L = 1..N,
  L = [A,B,C,D,E,F],

  Logic = 
  [
  % 1. Carlotta Pinkstone will come if Albus Dumbledore and Burdock Muldoon both come
  [[A,B],[C]],
  % 2. Falco Aesalon will come if Daisy Dodderidge and Elfrida Clagg both come
  [[D,E],[F]]
  ],

  % Whom is needs to be persuaded to attend the party in order to ensure that 
  % all her invitees attend?

  %
  % get minimum required
  %
  % minof(party2(Names,Logic, NumRequired,_People,_Persuaded,NumAttending),NumRequired),
  % println(people=People),
  % println(persuaded=Persuaded),

  member(NumRequired,1..N),
  println(numRequired=NumRequired),

  All = find_all([Persuaded,People,NumRequired],party2(Names,Logic, NumRequired,People,Persuaded,NumAttending)).sort_down(),
  Count = new_map(),
  foreach([Persuaded,People,NumRequired] in All)
    % println([Persuaded,People,NumRequired]),
    Count.put(Persuaded,Count.get(Persuaded,0)+1)
  end,

  Found = false,
  foreach(PP=CC in Count)
    if CC == 1 then
      Found := true,
      println(name=[Names[I] : I in 1..N, PP[I] == 1])
    end
  end,

  if Found == false then
    fail
  end,

  nl.

%
% another approach: use power set to test all combinations
%
go2b =>
  Names = ["Albus Dumbledore","Burdock Muldoon", "Carlotta Pinkstone",
           "Daisy Dodderidge","Elfrida Clagg","Falco Aesalon"],
  N = Names.len,
  L = 1..N,
  L = [A,B,C,D,E,F],

  Logic = 
  [
  % 1. Carlotta Pinkstone will come if Albus Dumbledore and Burdock Muldoon both come
  [[A,B],[C]],
  % 2. Falco Aesalon will come if Daisy Dodderidge and Elfrida Clagg both come
  [[D,E],[F]]
  ],

  % Whom is needs to be persuaded to attend the party in order to ensure that 
  % all her invitees attend?

  %
  % get minimum required
  %
  % minof(party2(Names,Logic, NumRequired,_People,_Persuaded,NumAttending),NumRequired),
  % println(people=People),
  % println(persuaded=Persuaded),

  % member(NumRequired,1..N),
  % 
  foreach(PS in power_set(1..N), PS != [])
    Persuaded = new_list(N),
    Persuaded :: 0..1,
    foreach(P in PS)
      Persuaded[P] #= 1
    end,
    println(persuaded=Persuaded),
    All = find_all([Persuaded,People,NumRequired],party2(Names,Logic, NumRequired,People,Persuaded,NumAttending)).sort_down(),
    Count = new_map(),
    foreach([Persuaded,People,NumRequired] in All)
      println(count=[Persuaded,People,NumRequired]),
      Count.put(Persuaded,Count.get(Persuaded,0)+1)
    end,

    foreach(PP=CC in Count)
      if CC == 1 then
        println(name=[Names[I] : I in 1..N, PP[I] == 1])
      end
    end,
  end,

  nl.



%
% Dataset 8 (see below)
% Dataset 8:
% Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon will all come if Albus Dumbledore comes
% Albus Dumbledore will come if Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon all come.


% Answers:

% (a) Albus Dumbledore
% (b) Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon


%
go8 =>
  Names = ["Albus Dumbledore","Burdock Muldoon", "Carlotta Pinkstone",
           "Daisy Dodderidge","Elfrida Clagg","Falco Aesalon"],
  N = Names.len,
  L = 1..N,
  L = [A,B,C,D,E,F],

  Logic = 
  [
  % Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon will all come if Albus Dumbledore comes
  [[A],[B,C,D,E,F]],
% Albus Dumbledore will come if Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon all come.
  [[B,C,D,E,F],[A]]
  ],

  % Whom is needs to be persuaded to attend the party in order to ensure that 
  % all her invitees attend?

  %
  % get minimum required
  %
  % party2(Names,Logic, NumRequired,_People,_Persuaded,NumAttending),
  % println(people=People),
  % println(persuaded=Persuaded),

  % member(NumRequired,1..N),
  % println(numRequired=NumRequired),

  foreach(PS in power_set(1..N), PS != [])
    % println(ps=PS),
    Persuaded = new_list(N),
    Persuaded :: 0..1,
    foreach(P in PS)
      Persuaded[P] #= 1
    end,
    % println(persuaded=Persuaded),

    All = find_all([Persuaded,People,NumRequired,NumAttending],party2(Names,Logic, NumRequired,People,Persuaded,NumAttending)).sort_down(),
    AllLen = All.len,
    % println(all=All),
    Count = new_map(),
    foreach([Persuaded1,People1,NumRequired1,NumAttending1] in All)
      % println([persuaded=Persuaded1,people=People1,numRequired=NumRequired1,numAttending=NumAttending1]),
      Count.put(Persuaded1,Count.get(Persuaded1,0)+1),
      if NumAttending1 == N then
         println(numattendingFull=PS),
         println([persuaded=Persuaded1,people=People1,numRequired=NumRequired1,numAttending=NumAttending1,allLen=AllLen])
      end
    end,

    % foreach(PP=CC in Count)
    %  if CC == 1 then
    %    println(name=[Names[I] : I in 1..N, PP[I] == 1])
    %  end
    % end,
  end,
  % fail,

  nl.


%
% for fold/3 in party2/5
%
and_constr(A,B) = A #/\ B.


party2(Names,Logic, NumRequired,People,Persuaded,NumAttending) =>


  nolog,
  % who will attend the party
  N = Names.len,
  People = new_list(N),
  People :: 0..1,

  % convert to constraints
  True #= 1,
  foreach([If,Then] in Logic)
    % println(if=If),
    % println(then=Then),
    FoldIf   = fold(and_constr, True, [People[P] : P in If]),
    FoldThen = fold(and_constr, True, [People[P] : P in Then]),
    FoldIf #=> FoldThen
  end,

  % People to persuade (at least one)
  Persuaded = new_list(N),
  Persuaded :: 0..1,

  foreach(P in 1..N)
    Persuaded[P] #=> People[P] #= 1
  end,

  % sum(Persuaded) #= 1,
  NumRequired #= sum(Persuaded),
  NumRequired #> 0,

  NumAttending #= sum(People),

  Vars = People ++ Persuaded,
  if var(NumRequired) then
    solve($[min(NumRequired), split],Vars)
  else
    solve([$split],Vars)
  end.



%
% This give the same answer as go/0: [ad,cp,ec,fa]
%
%
go_prolog => 
  All = findall(X,partymaker(X)),
  println(All),
  nl.


% Translated from Prolog code from
% http://cs.stackexchange.com/questions/2031/can-constraint-satisfaction-problems-be-solved-with-prolog
% Taken from http://ideone.com/Q3pqU
%
index(-,-)
follows(bm,[ad]).
follows(cp,[ad]).
follows(ad,[cp]).
follows(dd,[cp]).
follows(ad,[ec]).
follows(bm,[ec]).
follows(cp,[ec]).
follows(cp,[fa]).
follows(dd,[fa]).
follows(bm,[cp,dd]).
follows(ec,[cp,dd]).
follows(fa,[cp,dd]).
follows(dd,[ad,bm]).
 
brings(X,S) => brings(X,S,[],[]).

% Without 'table' there's a lot of identical solutions
table
brings(_X,[],_S,_N) => true. 
brings(X,XL,S,N) ?=> XL = [X|L], brings(X,L,[X|S],N). 
brings(X,YL,S,N) ?=> YL=[Y|L],follows(Y,[X]),brings(X,L,[Y|S],N). 
brings(X,YL,S,N) ?=> YL = [Y|L], not member(Y,N),not follows(Y,[X]), 
                   follows(Y,[A,B]),
                   try_bring(X,A,L,S,[Y|N]),
                   try_bring(X,B,L,S,[Y|N]),brings(X,L,[Y|S],N).
brings(X,YL,S,N) => YL=[Y|L], not member(Y,N),not follows(Y,[X]),not follows(Y,[_A,_B]), 
                   follows(Y,[C]),
                   try_bring(X,C,L,S,[Y|N]),brings(X,L,[Y|S],N).
 
try_bring(_X,A,_L,S,_N) ?=> member(A,S).
try_bring(X,A,L,S,N) =>  not member(A,S),Y=sort([A|L]),brings(X,Y,S,N).
 
partymaker(X) => Guests=[ad,bm,cp,dd,ec,fa],member(X,Guests),brings(X,Guests).



/*
  Problem instances
  from https://iggyfernandez.wordpress.com/2012/05/21/sql-vs-nosql-third-international-nocoug-sql-nosql-challenge-sponsored-by-pythian/


*  Dataset 1 (the one presented in the comment above)
The Wicked Witch of the West has invited six friends to the Third Annual Witching & Wizarding Ball at Pythian Academy of Es-Cue-El & No-Es-Cue-El. Burdock Muldoon and Carlotta Pinkstone both said they would come if Albus Dumbledore came. Albus Dumbledore and Daisy Dodderidge both said they would come if Carlotta Pinkstone came. Albus Dumbledore, Burdock Muldoon, and Carlotta Pinkstone all said they would come if Elfrida Clagg came. Carlotta Pinkstone and Daisy Dodderidge both said they would come if Falco Aesalon came. Burdock Muldoon, Elfrida Clagg, and Falco Aesalon all said they would come if Carlotta Pinkstone and Daisy Dodderidge both came. Daisy Dodderidge said she would come if Albus Dumbledore and Burdock Muldoon both came.

The Wicked Witch of the West needs an Es-Cue-El or No-Es-Cue-El spell to determine whom she needs to persuade to attend the wizarding ball in order to ensure that all her invitees attend.

Solution:
inviting either EC, CP, FA or AD would suffice.


* Dataset 2
Carlotta Pinkstone will come if Albus Dumbledore and Burdock Muldoon both come
Falco Aesalon will come if Daisy Dodderidge and Elfrida Clagg both come

Answers:

(a) Albus Dumbledore, Burdock Muldoon, Daisy Dodderidge, and Elfrida Clagg


* Dataset 3
Carlotta Pinkstone will come if Albus Dumbledore and Burdock Muldoon both come
Falco Aesalon will come if Daisy Dodderidge and Elfrida Clagg both come
Carlotta Pinkstone and Falco Aesalon will both come if Albus Dumbledore, Burdock Muldoon, Daisy Dodderidge, and Elfrida Clagg all come

Answers:

(a) Albus Dumbledore, Burdock Muldoon, Daisy Dodderidge, and Elfrida Clagg

* Dataset 4
Burdock Muldoon will come if Albus Dumbledore comes
Carlotta Pinkstone will come if Burdock Muldoon comes
Carlotta Pinkstone will come if Albus Dumbledore comes
Elfrida Clagg will come if Daisy Dodderidge comes
Falco Aesalon will come if Elfrida Clagg comes
Falco Aesalon will come if Daisy Dodderidge comes

Answers:

(a) Albus Dumbledore and Daisy Dodderidge

* Dataset 5
Burdock Muldoon will come if Albus Dumbledore comes
Carlotta Pinkstone will come if Burdock Muldoon comes
Carlotta Pinkstone will come if Albus Dumbledore comes
Elfrida Clagg will come if Daisy Dodderidge comes
Falco Aesalon will come if Elfrida Clagg comes
Falco Aesalon will come if Daisy Dodderidge comes
Carlotta Pinkstone and Falco Aesalon will both come if Albus Dumbledore, Burdock Muldoon, Daisy Dodderidge, and Elfrida Clagg all come

Answers:

(a) Albus Dumbledore and Daisy Dodderidge


Dataset 6:
Burdock Muldoon will come if Albus Dumbledore comes
Carlotta Pinkstone will come if Burdock Muldoon comes
Carlotta Pinkstone will come if Albus Dumbledore comes
Elfrida Clagg will come if Daisy Dodderidge comes
Falco Aesalon will come if Elfrida Clagg comes
Falco Aesalon will come if Daisy Dodderidge comes
Carlotta Pinkstone will come if Burdock Muldoon comes
Albus Dumbledore will come if Carlotta Pinkstone comes
Albus Dumbledore will come if  Burdock Muldoon comes
Falco Aesalon will come if Elfrida Clagg comes
Daisy Dodderidge will come if Falco Aesalon comes
Daisy Dodderidge will come if Elfrida Clagg comes



(a) Albus Dumbledore and Daisy Dodderidge
(b) Burdock Muldoon and Elfrida Clagg
(c) Albus Dumbledore and Elfrida Clagg
(d) Burdock Muldoon and Daisy Dodderidge


Dataset 7:
Albus Dumbledore will come if Burdock Muldoon, Carlotta Pinkstone, and Daisy Dodderidge all come
Albus Dumbledore will come if Carlotta Pinkstone, Daisy Dodderidge, and Elfrida Clagg all come
Albus Dumbledore will come if Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon all come

Answers:

(a) Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon


Dataset 8:
Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon will all come if Albus Dumbledore comes
Albus Dumbledore will come if Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon all come.


Answers:

(a) Albus Dumbledore
(b) Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon


*/