/*

  Scheduling speakers in Picat.

  http://stackoverflow.com/questions/20747059/optimizing-working-scheduling-minizinc-code-constraint-programming
  """
  Please can you help optimize this working MiniZinc code:
  Task: There is a conference which has 6x time slots. There are 3 speakers attending 
  the conference who are each available at certain slots. Each speaker will present for 
  a predetermined number of slots.

  Objective: Produce the schedule that has the earliest finish of speakers.

  Example: Speakers A, B & C. Talk durations = [1, 2, 1]

  Speaker availability:

  +---+------+------+------+
  |   | Sp.A | Sp.B | Sp.C |
  +---+------+------+------+
  | 1 |      | Busy |      |
  | 2 | Busy | Busy | Busy |
  | 3 | Busy | Busy |      |
  | 4 |      |      |      |
  | 5 |      |      | Busy |
  | 6 | Busy | Busy |      |
  +---+------+------+------+

  Link to working MiniZinc code: http://pastebin.com/raw.php?i=jUTaEDv0

  What I'm hoping to optimize:

    ensure allocated slots don't overlap and the allocated slot is free for the speaker
  constraint 
      forall(i in 1..num_speakers) (
          ending_slot[i] = starting_slot[i] + app_durations[i] - 1
      ) /\
      forall(i,j in 1..num_speakers where i < j) (
          no_overlap(starting_slot[i], app_durations[i], starting_slot[j], app_durations[j])
      ) /\
      forall(i in 1..num_speakers) (
          forall(j in 1..app_durations[i]) (
              starting_slot[i]+j-1 in speaker_availability[i]
          )
      ) 
  ;

  Expected solution:

  +---+----------+----------+----------+
  |   |   Sp.A   |   Sp.B   |   Sp.C   |
  +---+----------+----------+----------+
  | 1 | SELECTED | Busy     |          |
  | 2 | Busy     | Busy     | Busy     |
  | 3 | Busy     | Busy     | SELECTED |
  | 4 |          | SELECTED |          |
  | 5 |          | SELECTED | Busy     |
  | 6 | Busy     | Busy     |          |
  +---+----------+----------+----------+
  """

  Optimizing speakers for a conference in MiniZinc.
  Produced by Stackoverflow.com user Igor K
  Based on MiniZinc model created by Hakan Kjellerstrand, hakank@gmail.com. http://www.hakank.org/minizinc
  """


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

*/

import cp.

main => go.

go =>
   scheduling_speakers(1),
   nl.

go2 =>
   scheduling_speakers(2),
   nl.


%
% testing random instances
%
go3 =>
    N = 100,
    NumSlots = 136,
    Available = [],
    println("Generating problem instance..."),
    foreach(_I in 1..N) 
      A = 1..NumSlots,
      % and then remove some available slots
      foreach(_J in 1..1+random2() mod NumSlots)
         A := delete(A,1+(random2() mod A.length))
      end,
      Available := Available ++ [A]
    end,
    println("Available:"),
    foreach(S in 1..N) 
       printf("Speaker %2d: %w\n", S, Available[S])
    end,
    Duration=random_duration(N,4,NumSlots),
    println(duration=Duration),
    println("Solving..."),
    scheduling_speakers(N,NumSlots,Available,Duration),
    nl.


% random problem for printing MiniZinc instance (no solving)
go4 =>
    N = 10,
    NumSlots = 12,
    Available = [],
    foreach(_I in 1..N) 
      A = 1..NumSlots,
      % and then remove some available slots
      foreach(_J in 1..1+random2() mod NumSlots)
         A := delete(A,1+(random2() mod A.length))
      end,
      Available := Available ++ [A]
    end,
    println("% Generated by scheduling_speakers_optimize.pi"),
    println("% Note: This problem has no hole in the schedule."),
    Duration=random_duration(N,4,NumSlots),
    println(duration=Duration),
    print_problem_minizinc(N,NumSlots,Available,Duration),
    nl.


%
% solving problem(P)
%
scheduling_speakers(P) =>
   problem(P,N,NumSlots,Available,Duration),
   scheduling_speakers(N,NumSlots,Available,Duration).


scheduling_speakers(N,NumSlots,Available,Duration) =>

   if sum(Duration) > NumSlots then
     printf("Impossible: sum(Duration)[%d] > NumSlots[%d]\n", sum(Duration), NumSlots),
     halt
   end,

   %
   % decision variables
   % 
   Start = new_list(N),
   Start :: 1..NumSlots,

   End   = new_list(N),
   End :: 1..NumSlots,

   M = new_array(NumSlots, N),
   M :: 0..1,

   % max slot
   Z #= max([End[I] : I in 1..N]),

   %
   % constraints
   %
   Ts = [],
   foreach(I in 1..N) 
     End[I] #= Start[I] + Duration[I] - 1,

     % ensure that the speaker is available for the full talk
     foreach(J in 1..Duration[I])
        T #= Start[I]+J-1,
        T :: Available[I],
        Ts := Ts ++ [T]
     end
   end,

   cumulative(Start,Duration, [1 : _I in 1..N], 1),

   % all_different(Start),
   % all_different(End),

   % connect the "m" matrix
   foreach(T in 1..NumSlots) 
     % If there is no holes in the schedule then 
     % we can fasten things up by sum() #= 1
     if sum(Duration) = NumSlots then
        sum([M[T,S] #= 1 : S in 1..N]) #= 1
     else 
        sum([M[T,S] #= 1 : S in 1..N]) #<= 1
     end,

     foreach(S in 1..N)
        if not(member(T,Available[S])) then
           M[T,S] #= 0
        end,
        (T #>= Start[S] #/\ T #=< End[S]) #= M[T,S] #= 1
     end

   end,

   foreach(S in 1..N) 
      sum([M[T,S] : T in 1..NumSlots]) #= Duration[S]
   end,

   %
   % search
   % 
   Vars = Start ++ End ++ Ts,
   solve($[min(Z),ff,report($printf("Z: %d\n",Z))], Vars),

   print_solution(N,NumSlots,Available,Start,End,Z).


%
% Print the solution.
%
print_solution(N,NumSlots,Available,Start,End,Z) =>
   println(z=Z),
   println(start=Start),
   println('end  '=End),

   if N <= 100 then
     println("\nSchedule"),
     print("   "),
     foreach(S in 1..N) 
       % printf("Sp. %d    ", S)
       printf("%3d ", S)
     end,
     nl,
     foreach(T in 1..NumSlots)
       printf("%3d: ", T),
       foreach(S in 1..N) 
         if not(member(T,Available[S])) then
           % print("Busy     ")
           print("-   ")
         elseif T >= Start[S], T =< End[S] then
           print("S   ")
         else
           print("    ")
         end
       end,
       nl
     end
   end,
   println(speaker_order=speaker_order(N,NumSlots,Start,End)),
   nl.


%
% Order of speakers, one for each time slot
%
speaker_order(NumSpeakers,NumSlots,Start,End) = [S : T in 1..NumSlots, S in 1..NumSpeakers, T >= Start[S], T <= End[S]].
 

%
% print a problem for MiniZinc
%
print_problem_minizinc(N,NumSlots,Available,Duration) =>
  printf("num_speakers = %d;\n", N),
  printf("num_slots = %d;\n", NumSlots),
  println("speaker_availability = ["),
  foreach(A in Available) 
    print("{"),
    foreach(AA in A) 
      printf("%d,",AA)
    end,
    printf("},\n")
  end,
  println("];"),
  printf("app_durations = %w;\n", Duration),
  nl.

% Original problem
% Note: the schedule will have some time where there's no speaker.
problem(1,N,NumSlots,Available,Duration) =>
  N = 3,        % number of speakers
  NumSlots = 6, % number of slots
  Available = [ % available for speaking
         [1,4,5],
         [4,5],
         [1,3,4,6]
       ],
  % duration of the talk
  Duration = [1,2,1].


% Slighly larger problem
problem(2,N,NumSlots,Available,Duration) =>
   N = 6,
   Duration = [2,1,2,1,2,2],
   NumSlots = sum(Duration),
   Available = 
       [
         [3,4,5,6,9,10],
         [3,4,7,8,9,10],
         [2,3,4,5,6,7,8],
         [4,5,6,10],
         [1,3,4,5,6,7,8],
         [1,2,3,4,7,8,9,10]
       ].

%
% Find a random duration which sums to Sum
% (here an indomain_rand would be handy...)
%
random_duration(N,Limit,Sum) = A =>
   A = new_list(N),
   A :: 1..Limit,
   sum(A) #= Sum,
   solve($[ff,updown],A).