schedule problem 5

schedule3.jl

# our schedule is 3D array with (5 workdays, W workhours, P positions) for dimensions
day_start = 7
day_end = 19
positions = 4
people = 8
position_hours = 8
work_hours = 20

# generate random schedule of each intern's busy times
busy = ntuple(people, i -> fill((0,0,0), rand(0:7)))
for intern = 1:people
  days = length(busy[intern])

  b = 0
  for i = 1:days
    day = rand(1:5)
    busy_start = rand(day_start:(day_end - 1))
    busy_end = rand((busy_start+1):day_end)
    predicate(block) = day == block[1] && !isempty(intersect(busy_start:busy_end, block[2]:block[3]))
    contradictions = filter(predicate, busy[intern][1:i-1])
    b = 0
    while !(1 <= busy_end - busy_start <= 4) || !isempty(contradictions)
      b += 1
      if b > 20
        break
      end

      busy_start = rand(day_start:(day_end - 1))
      busy_end = rand((busy_start + 1):day_end)
      contradictions = filter(predicate, busy[intern][1:i-1])
    end
    if b > 20
      break
    end
    busy[intern][i] = (day, busy_start, busy_end)
  end
  if b > 20
    intern -= 1
  end
end
i = 1
for b in busy
  sort!(busy[i], lt=(x, y) -> x[1] < y[1])
  println(i, ": ", b)
  i += 1
end

function algorithm(day_start, day_end, positions, people, position_hours, work_hours, busy)
  day_hours = day_end - day_start
  new_schedule() = fill(0, 5, day_hours, positions)
  schedule = new_schedule()

  busy = ntuple(people, i -> (i, busy[i]))

  busy_times_sum(table) = isempty(table)? 0 : sum(block -> block[3] - block[2], table)
  busy = sort([busy...], lt = (x, y) -> busy_times_sum(x[2]) > busy_times_sum(y[2]))

  function free(schedule)
    slots = (Int, Int, Int)[]

    for d = 1:size(schedule, 1), h = 1:size(schedule, 2), p = 1:size(schedule, 3)
      if schedule[d, h, p] == 0
        push!(slots, (d, h, p))
      end
    end

    slots
  end

  function free_for(person, busy, free)
    busy_hours = (Int, Int, Int)[]

    times = busy[person][2]
    for (day, busy_start, busy_end) in times
      for h = busy_start:(busy_end-1)
        [push!(busy_hours, (day, h-day_start+1, pos)) for pos = 1:positions]
      end
    end

    setdiff(free, Set(busy_hours))
  end

  # p1 is the index of the person, that can't be placed
  # p2 is the position of the candidate for swap
  function can_swap(p1, p2, pos, schedule, p1_free_hours, p2_free_hours)
    if !isempty(filter(val -> p1 == val, schedule[p2[1], p2[2], :]))
      return false
    end
    if !isempty(filter(val -> schedule[p2...] == val, schedule[pos[1], pos[2], :]))
      return false
    end
    if !in(pos, p2_free_hours) || !in(p2, p1_free_hours)
      return false
    end
    true
  end

  for person = 1:people
    free_slots = free(schedule)
    free_hours = ntuple(people, i -> free_for(i, busy, free_slots))
    possibile = [(h[1], h[2], pos) for h = free_hours[person], pos = 1:positions]
    available = intersect(possibile, free_slots)
    filter!(slot -> countnz(schedule[slot[1], :, slot[3]]) < position_hours, available)
    for hour = 1:work_hours
      if length(available) > 0
        schedule[available[1]...] = busy[person][1]
        just_taken = Set([(available[1][1], available[1][2], pos) for pos = 1:positions])
        available = setdiff(available, just_taken)
        filter!(slot -> countnz(schedule[slot[1], :, slot[3]]) < position_hours, available)
      else
        swapped = false
        linear_index = findfirst(x -> x == 0, schedule)
        sub = ind2sub(size(schedule), linear_index)
        for d = 1:size(schedule, 1), h = 1:size(schedule, 2), p = 1:size(schedule, 3)
          p2_index = findfirst(x -> x[1] == schedule[d, h, p], busy)
          if p2_index == 0
            continue
          end
          p1_free_hours = free_for(person, busy, free(new_schedule()))
          p2_free_hours = free_for(p2_index, busy, free(new_schedule()))
          if can_swap(busy[person][1], (d, h, p), sub, schedule, p1_free_hours, p2_free_hours)
            swapped = true
            schedule[linear_index] = schedule[d, h, p]
            schedule[d, h, p] = person
            break
          end
        end
        if !swapped
          println("Error! The algorithm couldn't create a schedule for the given arguments. (Can't place ", busy[person][1], ").")
          println("Here is the schedule so far...")
          println(schedule)
          exit()
        end
      end
    end
  end

  println(schedule)
end

algorithm(day_start, day_end, positions, people, position_hours, work_hours, busy)