/* 

  Timetable problem in Picat.

  From alma-0 program timetable.a0
  """
  The problem is from 
  @Conference{Scha97,
    author =       "Andrea Schaerf",
    title =        "Combining Local Search and Look-Ahead for Scheduling
                    and Constraint Satisfaction Problems",
    booktitle =     "Proc.\ of the 15th International Joint Conf.\ on
                    Artificial Intelligence (IJCAI-96)",
    address =      "Nagoya, Japan",
    year =         "1997",
    pages =        "1254--1259",
    publisher =    "Morgan Kaufmann",
  }

  There are q courses, and each course i consists of
  k_i lectures, and p periods 1,...,p. For all i = 1,...,q, all lectures
  l = 1,...,k_i must be assigned to a period j in such a way that the
  following constraints are satisfied:

  1. Conflicts: There is a conflict matrix M such that M[i,j] = 1 if
     courses i and j have common students. Lectures of courses i and j  must
     be all scheduled at different times

  2. Availabilities: There is an availability binary matrix A such that
     A[i,j] = 1 then lectures of course i cannot be scheduled at period j.

  3. Rooms: There are r rooms available. At most r lectures can be
     scheduled at period k, for each k = 1,...,p.
  """

  

  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 =>

  courses(Courses),
  periods(Periods),
  rooms(Rooms),
  available(Available),
  conflict(Conflict),
  requirement(Requirement),

  % decision variables
  Timetable = new_array(Courses,Periods),
  Timetable :: 0..1,


  % 1. Conflicts: There is a conflict matrix M such that M[i,j] = 1 if
  %    courses i and j have common students. Lectures of courses i and j  must
  %    be all scheduled at different times
  foreach(C1 in 1..Courses, C2 in 1..Courses, C1 < C2) 
       if Conflict[C1,C2] = 1 then
          foreach(P in 1..Periods) 
             Timetable[C1,P] + Timetable[C2,P] #=< 1
          end
       end
  end,

  %
  % 2. Availabilities: There is an availability binary matrix A such that
  %    A[i,j]= 1 then lectures of course i cannot be scheduled at period j.
  %    [Note: It must be that if A[i,j] = 0 then the lectures cannot be 
  %     scheduled at period j.]
  foreach(C in 1..Courses, P in 1..Periods)
       if Available[C,P] = 0 then
          Timetable[C,P] #= 0
       end
  end,

  % 3. Rooms: There are r rooms available. At most r lectures can be
  %    scheduled at period k, for each k = 1,...,p.
  foreach(P in 1..Periods)
    sum([Timetable[C,P] : C in 1..Courses]) #=< Rooms
  end,

  % The number of lectures per course
  foreach(C in 1..Courses)
    sum([Timetable[C,P] : P in 1..Periods]) #= Requirement[C]
  end,

  solve([ff,updown],Timetable),

  foreach(C in 1..Courses)
    foreach(P in 1..Periods) 
       print(Timetable[C,P]),print(" ")     
    end,
    printf("\n")
  end,
  
  nl.


%
% data (from the Alma-0 program timetable.a0)
%
index(-)
courses(5).

index(-)
periods(20).

index(-)
rooms(2).
 
index(-)
available(
  [
   % 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0  
     [0,0,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,1,1],
     [1,1,0,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1],
     [0,0,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1],
     [1,1,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1],
     [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
  ]).

index(-)
conflict(
  [
    [0,1,0,0,1],
    [1,0,0,1,0],
    [0,0,0,0,1],
    [0,1,0,0,1],
    [1,0,1,1,0]
  ]).

index(-)
requirement([6,10,14,6,4]).