/*

  Set covering in Picat.

  Example from Steven Skiena, The Stony Brook Algorithm Repository
  http://www.cs.sunysb.edu/~algorith/files/set-cover.shtml
  """
  Input Description: A set of subsets S_1, ..., S_m of the 
  universal set U = {1,...,n}.
  
  Problem: What is the smallest subset of subsets T subset S such 
  that \cup_{t_i in T} t_i = U?
  """
  Data is from the pictures INPUT/OUTPUT.

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

*/

import util.
import cp.

main => go.

%
% First find the optimal value (MinVal), then find all the solutions with that value.
%
go =>

   printf("Find the optimal solution"),
   belongs(Belongs),
   set_covering_skiena(Belongs, MinVal,_),

   printf("\nFinding all optimal solutions with MinVal %d:\n", MinVal),
   L = findall(X, $set_covering_skiena(Belongs,  MinVal,X)),
   Len = length(L),
   foreach(S in L) writeln(S) end,
   printf("It was %d solutions\n", Len),nl.

set_covering_skiena(Belongs, MinVal, X) =>

   NumSets = Belongs.length,

   X = new_list(NumSets),
   X :: 0..1,

   BelongsTransposed = transpose(Belongs),
   foreach(Belong in BelongsTransposed)
      sum([XX*(B#>0) : {B,XX} in zip(Belong,X)]) #>= 1 
   end,
   MinVal #= sum(X),

   % either search for all solutions (for the minimum value) or
   % the optimal value
   if ground(MinVal) then
       solve([],X)
   else
       solve([$min(MinVal)], X)
   end.


%
% The belong matrix:
%
belongs(Belongs) => 
  Belongs = 
   [[1,1,0,0,0,0,0,0,0,0,0,0],
    [0,1,0,0,0,0,0,1,0,0,0,0],
    [0,0,0,0,1,1,0,0,0,0,0,0],
    [0,0,0,0,0,1,1,0,0,1,1,0],
    [0,0,0,0,0,0,0,0,1,1,0,0],
    [1,1,1,0,1,0,0,0,1,1,1,0],
    [0,0,1,1,0,0,1,1,0,0,1,1]].