/* 

  Unique set representation puzzle in Picat.

  From Stack Overflow
  "Choosing unique set representing number puzzle"
  http://stackoverflow.com/questions/6689147/choosing-unique-set-representing-number-puzzle
  """
  Following is the input set given.
  
  1009 2000
  1009 2001
  1002 2002
  1003 2002 

  Each line represents one group, Number represents ID of the member in the group. 
  Problem is to choose minimum number of people which re-presents complete given set. 
  Only one member should be choose from each Group. 2-tuple members will not repeated. But 
  members can be part of more than one group.
  
  So in this example answer be 1009 and 2002 which represents the sets. 1009 is chosen 
  because it is representing two team and same is the case for 2002.
  
  I am looking for what algorithm can be used to solve this problem.
  
  Another example:
  
  1009 2000
  1009 2001
  1002 2002
  1003 2002 
  1004 2003
  
  Answer can be { 1009 , 2002, 1004} or { 1009, 2002, 2003}
  """

  Note: This problem seems to be inspired by
  Spotify Job puzzle: Bilateral Projects
  http://www.spotify.com/us/jobs/tech/bilateral-projects/
  

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

*/

import cp.

main => go.

go =>
  member(P,1..3),
  println(p=P),
  puzzle(P,Set),
  unique_set_puzzle(Set, Ids,_S,Z),
  println(z=Z),
  All = findall([Ids2,S2,Z], unique_set_puzzle(Set, Ids2,S2,Z)),
  foreach([Ids2,S2,_Z2] in All)
    println(S2),
    println([Ids[I] : I in 1..Ids2.len, S2[I] == 1]),
    nl
  end,
  println(num_solutions=All.len),
  nl,
  fail,
  nl.
go => true.


unique_set_puzzle(Set, Ids,S,Z) =>
  Ids = [I : I in Set.flatten].sort_remove_dups,
  N = Set.len,
  S = new_list(Ids.len),
  S :: 0..1,
  
  % "Only one member should be choose from each Group"
  foreach(I in 1..N)
    % identify the indices of the id in Ids
    nth(Id1,Ids,Set[I,1]),
    nth(Id2,Ids,Set[I,2]),
    S[Id1] + S[Id2] #= 1
  end,
  Z #= sum(S),
  
  if var(Z) then
    solve($[min(Z)],S)
  else
    solve($[],S)
  end.

puzzle(1,Set) =>
  Set = [[1009, 2000],
         [1009, 2001],
         [1002, 2002],
         [1003, 2002]].


puzzle(2,Set) =>
  Set =  [[1009, 2000],
          [1009, 2001],
          [1002, 2002],
          [1003, 2002],
          [1004, 2003]].

% Example from a comment (n.m).
% Unsolvable.
puzzle(3,Set) =>
  Set = [[1,2],
         [2,3],
         [3,1]].