/* 

  Conference problem in Picat.

  From 
  "Constraint Programming with Alice"
  http://www.ps.uni-saarland.de/alice/manual/cptutorial/node37.html
  """
  We want to construct the time table of a conference. The conference will consist 
  of 11 sessions of equal length. The time table is to be organized as a sequence of 
  slots, where a slot can take up to 3 parallel sessions. There are the following 
  constraints on the timing of the sessions:

   * Session 4 must take place before Session 11.
   * Session 5 must take place before Session 10.
   * Session 6 must take place before Session 11.
   * Session 1 must not be in parallel with Sessions 2, 3, 5, 7, 8, and 10.
   * Session 2 must not be in parallel with Sessions 3, 4, 7, 8, 9, and 11.
   * Session 3 must not be in parallel with Sessions 5, 6, and 8.
   * Session 4 must not be in parallel with Sessions 6, 8, and 10.
   * Session 6 must not be in parallel with Sessions 7 and 10.
   * Session 7 must not be in parallel with Sessions 8 and 9.
   * Session 8 must not be in parallel with Session 10.

  The time table should minimize the number of slots. 
  
  ...

  This plan says that the conference requires 4 slots, where 
    the sessions 1, 4 and 9 take place in slot 1, 
    the sessions 2, 5 and 6 take place in slot 2, 
    the sessions 3, 7 and 10 take place in slot 3, and 
    the sessions 8 and 11 take place in slot 4.
  """
 
  Solution:
    sessions = [1,2,3,1,2,2,3,4,1,3,4]
    numTimeSlots = 4
    [slot = 1,[1,4,9]]
    [slot = 2,[2,5,6]]
    [slot = 3,[3,7,10]]
    [slot = 4,[8,11]]


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

*/

import cp.


main => go.

go ?=>
  NumSessions = 11,
  MaxTimeSlots = 11,

  % precedences of sessions
  NumPrecedences = 3,
  Precedences = 
   {{4,11},
    {5,10},
    {6,11}},

  % sessions that should not be parallel
  NumPara = 8,
  Parallel = {
           {2, 3, 5, 7, 8, 10}, % not parallel with session 1
           {3, 4, 7, 8, 9, 11}, % not parallel with session 2
           {5, 6, 8},           % not parallel with session 3
           {6, 8, 10},          % not parallel with session 4
           {},                  % not parallel with session 5 (dummy)
           {7,10},              % not parallel with session 6
           {8, 9},              % not parallel with session 7
           {10}                 % not parallel with session 8
           },

  %
  % decision variables
  %
  
  % sessions: in what slot is this session
  Sessions = new_list(NumSessions),
  Sessions :: 1..MaxTimeSlots,

  % number of used time slots (to be minimized)
  NumTimeSlots #= max(Sessions),

  % Precedences:
  foreach(P in 1..NumPrecedences)
     Sessions[Precedences[P,1]] #< Sessions[Precedences[P,2]]
  end,

  % parallel constraints
  foreach(S in 1..NumPara, Parallel[S].len > 0)
     foreach(PP in Parallel[S]) 
        Sessions[S] #!= Sessions[PP]
     end
  end,

  % max 3 sessions per slot
  foreach(S in 1..MaxTimeSlots) 
    % card(slots[s]) <= 3
    sum([Sessions[I] #= S : I in 1..NumSessions]) #<= 3
  end,

  Vars = Sessions,
  solve($[min(NumTimeSlots)],Vars),

  println(sessions=Sessions),
  println(numTimeSlots=NumTimeSlots),
  foreach(Slot in 1..NumTimeSlots)
    println([slot=Slot,[ S : S in 1..NumSessions, Sessions[S] == Slot]])
  end,
  
  nl.

go => true.