schedule problem 3

schedule2.jl

function pickrand(col)
  index = rand(1:length(col))
  col[index]
end

function isbusy(intern, busy, day_hours, day, hour)
  for i = 1:length(busy[intern])
    if busy[intern][i][1] == day && (busy[intern][i][2]-day_hours) <= hour < (busy[intern][i][3]-day_hours)
      return true
    end
  end
  false
end

function neighbours(pos, arr)
  x, y, z = pos
  neigh = Any[]
  if x > 1; push!(neigh, ((x-1, y, z), 1, -1)) end
  if x < size(arr, 1); push!(neigh, ((x+1, y, z), 1, +1)) end
  if y > 1; push!(neigh, ((x, y-1, z), 2, -1)) end
  if y < size(arr, 2); push!(neigh, ((x, y+1, z), 2, 1)) end
  if z > 1; push!(neigh, ((x, y, z-1), 3, -1)) end
  if z < size(arr, 3); push!(neigh, ((x, y, z+1), 3, 1)) end
  neigh
end

function euclideandist(a, b)
  sum([(b[i] - a[i])^2 for i = 1:3])
end

function metric(current, new, neighbour, schedule)
  # by distance
  score = 0
  score = 20 - euclideandist(current, new)
  if score < 0
    score = 0
  end

  # by dimension and size of group
  diff = (neighbour[1] - new[1], neighbour[2] - new[2], neighbour[3] - new[3])

  #= if (diff == (1, 0, 0) || diff == (-1, 0, 0)) =#
  #=   score += 6 =#
  #=   if neighbour[1] < size(schedule, 1) && diff == (1, 0, 0) =#
  #=     if schedule[neighbour[1]+1, neighbour[2], neighbour[3]] == schedule[current...] =#
  #=       score += 10 =#
  #=     end =#
  #=   elseif neighbour[1] > 1 =#
  #=     if schedule[neighbour[1]-1, neighbour[2], neighbour[3]] == schedule[current...] =#
  #=       score += 10 =#
  #=     end =#
  #=   end =#
  #= end =#
  if (diff == (0, 1, 0) || diff == (0, -1, 0)) && neighbour[1] == new[1]
    score += 40
    if neighbour[2] < size(schedule, 2) && diff == (0, 1, 0)
      if schedule[neighbour[1], neighbour[2]+1, neighbour[3]] == schedule[current...]
        score += 30
      end
    end
    if neighbour[2] > 1 && diff == (0, -1, 0)
      if schedule[neighbour[1], neighbour[2]-1, neighbour[3]] == schedule[current...]
        score += 30
      end
    end
    if new[2] > 1 && diff == (0, -1, 0)
      if schedule[new[1], new[2]-1, new[3]] == schedule[current...]
        score += 30
      end
    end
    if neighbour[2] < size(schedule, 2) && diff == (0, 1, 0)
      if schedule[new[1], new[2]+1, new[3]] == schedule[current...]
        score += 30
      end
    end
  end
  #= if diff == (0, 0, 1) || diff == (0, 0, -1) =#
  #=   score += 2 =#
  #=   if neighbour[3] < size(schedule, 3) && diff == (0, 0, 1) =#
  #=     if schedule[neighbour[1], neighbour[2], neighbour[3]+1] == schedule[current...] =#
  #=       score += 10 =#
  #=     end =#
  #=   elseif neighbour[3] > 1 =#
  #=     if schedule[neighbour[1], neighbour[2], neighbour[3]-1] == schedule[current...] =#
  #=       score += 10 =#
  #=     end =#
  #=   end =#
  #= end =#

  other_neighbours = map(x -> x[1], neighbours(current, schedule))
  for neigh in other_neighbours
    if schedule[neigh...] == schedule[new...] && neigh[2] != current[2] && neigh[1] == current[1]
      score += 25
    end
  end

  score
end

function nextpos(pos, direction, amount)
  diff = [0, 0, 0]
  diff[direction] = amount
  (pos[1]+diff[1], pos[2]+diff[2], pos[3]+diff[3])
end

function maxby(f, arr)
  max = 0
  index = 0
  for i in 1:length(arr)
    if f(arr[i]) > max
      index = i
      max = f(arr[i])
    end
  end
  arr[index]
end

# 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
schedule = Array(Int, 5, day_hours, positions)

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

  for i = 1:days
    day = rand(1:5)
    busy_start = rand(day_start:(day_end - 1))
    busy_end = rand((day_start + 1):day_end)
    while !(1 <= busy_end - busy_start <= 4)
      busy_start = rand(day_start:(day_end - 1))
      busy_end = rand((day_start + 1):day_end)
    end
    busy[intern][i] = (day, busy_start, busy_end)
  end
end
i = 1
for b in busy
  print(i)
  sort!(busy[i], lt=(x, y) -> x[1] < y[1])
  i += 1
  print(": ")
  println(b)
end
#= println(busy) =#

# our algorithm starts here
# first, we generate a random schedule
day = hour = position = 0
while true
	#= schedule = Array(Int, 5, day_hours, 4) =#
  schedule = fill(0, 5, day_hours, positions)
	remaining_hours = fill(20, people)
	bad_schedule = false

	for day = 1:5, hour = 1:day_hours, position = 1:positions
    if length(filter(x -> x != 0, schedule[day, :, position])) >= 8
      continue
    end

    not_tried = [i for i = 1:people]
    intern = pickrand(not_tried)

    # if the intern has no more hours or if he is working at another position at the same time
    while remaining_hours[intern] == 0 || intern in schedule[day, hour, :] || isbusy(intern, busy, day_hours, day, hour)
      intern = pickrand(not_tried)

      filter!(x -> x != intern, not_tried)

      # if we have tried all interns and no one is able to work at that time
      if isempty(not_tried)
        bad_schedule = true
        break
      end
    end
    if bad_schedule
      break
    end
    schedule[day, hour, position] = intern
    remaining_hours[intern] -= 1
  end

  if !bad_schedule
    break
  end
end

#= println(schedule) =#

for i = 1:3
  for day = 1:5, hour = 1:day_hours, position = 1:positions
    intern = schedule[day, hour, position]

    if intern == 0
      continue
    end

    next = false
    current = (day, hour, position)
    adjacent = filter(x -> x[1][2] != current[2], neighbours(current, schedule))
    for x in adjacent
      if schedule[x[1]...] == schedule[current...]
        if rand() > 0.3
          next = true
        end
      end
    end
    if next
      continue
    end

    #= other_hours = find(x -> x == intern, schedule) =#
    predicate = x -> x != current && schedule[x...] == intern
    other_hours = filter(predicate, [(d, h, p) for d = 1:5, h = 1:day_hours, p = 1:positions])
    candidates = vcat(map(x -> neighbours(x, schedule), other_hours)...)
    candidates = filter(x -> !isbusy(intern, busy, day_hours, x[1][1], x[1][2]), candidates)
    #= call_metric = x -> println(x);metric((day, hour, position), x[1], nextpos(x[1], x[2], x[3]), schedule) =#
    scores = map(x -> (x[1], metric((day, hour, position), x[1], nextpos(x...), schedule)), candidates)
    scores = sort(scores, lt=(x, y) -> x[2] > y[2])
    #= max = maxby(x -> x[2], scores) =#
    #= println(scores) =#
    max = scores[1][1]
    i = 1
    test = false
    #= schedule[max[1], max[2], ] =#
    while length(filter(x -> x != 0, schedule[max[1], :, max[3]])) > 8
      i += 1
      max = scores[i][1]
    end

    # has to check if it's ok to go there
    schedule[current...] = schedule[max...]
    schedule[max...] = intern
  end
end
println(schedule)