schedule problem 4

schedule3.jl

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

new_schedule() = fill(0, 5, day_hours, positions)
schedule = new_schedule()

# 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

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

remaining_hours = fill(work_hours, people)

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 h = 1:remaining_hours[person]
    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

      linear_index = findfirst(x -> x == 0, schedule)
      sub = ind2sub(size(schedule), linear_index)
      println(sub, " for ", busy[person][1])
      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)
          println("swap with: ", (d, h, p))
          schedule[linear_index] = schedule[d, h, p]
          schedule[d, h, p] = person
          break
        end
      end
    end
  end
end

println(schedule)