/*

  Tourist Site Competition in SICStus Prolog.

  From Pierre Flener's presentation 
  "Constraint Technology - A Programming Paradigm on the Rise"
  http://www.it.uu.se/edu/course/homepage/ai/vt08/AI-CT.pdf
     pages 5f: problem statement 
     pages 12f: model
     pages 21ff: walktrough of a solution

  With 7 tourist sites and 7 judges:
  """
  Every tourist site is visited by r = 3 judges.
  Every judge visits c = 3 tourist sites.
  Every pair of sites is visited by lambda = 1 common judge.
  """

  There are 151200 solutions to this problem.
  With the additional constraint that Ali should visit Birka, Falun and Lund
  there are 4320 solutions.


  This problem was also presented as "The Airline-of-the-Year Problem"
  in his (Flener's) presentation
  "Constraint Programming - Programming Paradigm on the Rise"
  http://www.it.uu.se/research/group/astra/ATM-CT/Flener.pdf
  page 4f
  The problem is stated as follows for 7 airlines and 7 judges:
  """
  Constant jury: Every airline is tested by 3 judges.
  Constant load: Every judge tests 3 airlines.
  Equity: Every airline pair is tested by 1 common judge.
  """
  
  Compare with the following models:
  * Comet   : http://www.hakank.org/comet/tourist_site_competition.co
  * MiniZinc: http://www.hakank.org/minizinc/tourist_site_competition.mzn


  Model created by Hakan Kjellerstrand, hakank@bonetmail.com
  See also my SICStus Prolog page: http://www.hakank.org/sicstus/

*/

:-use_module(library(clpfd)).
:-use_module(library(lists)).


go :-
        R = 3,
        C = 3,
        Lambda = 1,

        % Sites
        Birka = 1,
        Falun = 2,
        Lund = 3,
        Mora = 4,
        Sigtuna = 5,
        Uppsala = 6,
        Ystad = 7,
        Sites = [Birka, Falun, Lund, Mora, Sigtuna, Uppsala, Ystad],
        SitesStr = ['Birka', 'Falun', 'Lund', 'Mora', 'Sigtuna', 'Uppsala', 'Ystad'],
        % Judges
        Ali = 1,
        Dan = 2,
        Eva = 3,
        Jim = 4,
        Leo = 5,
        Mia = 6,
        Ulla = 7,
        Judges = [Ali, Dan, Eva, Jim, Leo, Mia, Ulla],
        JudgesStr = ['Ali', 'Dan', 'Eva', 'Jim', 'Leo', 'Mia', 'Ulla'],
        
        SymmetryBreaking = true,

        tourist_site_competition(Sites,Judges,R,C,
                                 Lambda,SymmetryBreaking,X),
        ( foreach(Row,X) do write(Row),nl ),
        print_assignments(X,SitesStr,JudgesStr),
        % fail,
        fd_statistics.


tourist_site_competition(Sites,Judges,R,C,Lambda,SymmetryBreaking,X) :-

        length(Sites,NumSites),
        length(Judges,NumJudges),

        % decision variable
        matrix(X,[NumSites,NumJudges]),
        append(X,XList),
        domain(XList,0,1),

        % Symmetry breaking: Assigns the first site to judges {1,2,3}
        ( SymmetryBreaking ->
              ( for(I1,1,3),
                param(X) do
                    matrix_element(X,I1,1,1)
              )
        ;
              true
        ),

        % Every tourist site is visited by R judges.
        ( foreach(XRow,X),
          param(R) do
              sum(XRow,#=,R)
        ),

        % Every judge visits C tourist sites.
        transpose(X,XTransposed),
        ( foreach(XColumn,XTransposed),
          param(C) do
              sum(XColumn,#=,C)
        ),

        % Every pair of sites is visited by Lambda common judges.
        ( foreach(X1,X),
          count(I,1,_),
          param(X,Lambda) do
              ( foreach(X2,X),
                count(J,1,_),
                param(I,X1,Lambda) do
                    I < J ->
                    (
                       ( foreach(XX1,X1),
                         foreach(XX2,X2),
                         fromto(0,In,Out,Sum) do
                           Reif in 0..1,
                           (XX1 #= 1 #/\ XX1 #= XX2) #<=> Reif #= 1,
                           indomain(Reif),
                           Out #= In + Reif
                       ),
                       Sum #>= Lambda
                    )
                    ;
                    true
              )
        ),
                
        % search
        labeling([], XList).



print_assignments(X,SitesStr,JudgesStr) :-
        ( foreach(Row,X),
          foreach(S,SitesStr),
          param(JudgesStr) do
              format('~w: ',[S]),
              ( foreach(R,Row),
                count(I,1,_),
                fromto(Where,Out,In,[]),
                param(JudgesStr) do
                    R = 1 ->
                    (
                     nth1(I,JudgesStr,Judge),  
                     Out = [Judge|In]
                    )
              ;
                    Out = In
              ),
              write(Where),nl
        ),
        nl.




matrix_element(X, I, J, Val) :-
        nth1(I, X, Row),
        element(J, Row, Val).


% From Mats Carlsson.
matrix(_, []) :- !.
matrix(L, [Dim|Dims]) :-
        length(L, Dim),
        (   foreach(X,L),
            param(Dims)
        do  matrix(X, Dims)
        ).