/* 

  Movie scheduling problem in Picat.

  From Steven Skiena "The Algorithm Design Manual", page 9ff.

  Data from figure 1.5 (where I have estimated the times).
  
  Movie                      Interval
  -----------------------------------
  Tarjan of the Jungle         4..13
  The Four Volume Problem     17..27
  The President's Algorist     1..10
  Steiner's Tree              12..18
  Process Terminated          23..30
  Halting State                9..16
  Programming Challenges      19..25
  "Discrete" Mathematics       2..7
  Calculated Bets             26..31


  All optimal solutions:
  x2 = [0,0,0,0,0,1,1,1,1]
  [Halting State,[9,16]]
  [Programming Challenges,[19,25]]
  ['Discrete' Mathematics,[2,7]]
  [Calculated Bets,[26,31]]

  x2 = [0,0,0,1,0,0,1,1,1]
  [Steiner's Tree,[12,18]]
  [Programming Challenges,[19,25]]
  ['Discrete' Mathematics,[2,7]]
  [Calculated Bets,[26,31]]

  x2 = [0,0,1,1,0,0,1,0,1]
  [The President's Algorist,[1,10]]
  [Steiner's Tree,[12,18]]
  [Programming Challenges,[19,25]]
  [Calculated Bets,[26,31]]



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

  Data = [
         [ 4,13], % "Tarjan of the Jungle",
         [17,27], % "The Four Volume Problem",
         [ 1,10], % "The President's Algorist",
         [12,18], % "Steiner's Tree",
         [23,30], % "Process Terminated",
         [ 9,16], % "Halting State",
         [19,25], % "Programming Challenges",
         [ 2, 7], % "'Discrete' Mathematics",
         [26,31]],  % "Calculated Bets"

  NumMovies = Data.len,

  Movies = [
           "Tarjan of the Jungle",
           "The Four Volume Problem",
           "The President's Algorist",
           "Steiner's Tree",
           "Process Terminated",
           "Halting State",
           "Programming Challenges",
           "'Discrete' Mathematics",
           "Calculated Bets"
           ],
  movie_scheduling(Data,Movies, X,Z),
  printf("\nFinding all optimal solutions with z = %d:\n",Z),
  movie_scheduling(Data,Movies, X2,Z),
  println(x2=X2),
  foreach(I in 1..NumMovies)
    if X2[I] == 1 then
      println([Movies[I],Data[I]])
    end
  end,
  nl,
  fail,
  nl.

go => true.

movie_scheduling(Data,Movies, X,Z) =>
  % decision variables
  NumMovies = Data.len,
  X = new_list(NumMovies),
  X :: 0..1,
  
  Z #= sum(X),

  foreach(I in 1..NumMovies, J in I+1..NumMovies)
    no_overlap(Data[I,1], Data[I,2], Data[J,1], Data[J,2],B),
    (X[I] #= 1 #/\ X[J] #= 1) #=> B #= 1
  end,
  if var(Z) then
    % Finding the optimal value
    solve($[max(Z)],X)
  else
    % Generate all the solutions with optimal Z
    solve($[],X)  
  end.
  

no_overlap(Start1, End1, Start2, End2, B) =>
  B :: 0..1,
  (Start1 #> End2 #\/ Start2 #> End1) #<=> B#=1.