schedule problem 2

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 = 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
    elseif neighbour[2] > 1
      if schedule[neighbour[1], neighbour[2]-1, neighbour[3]] == schedule[current...]
        score += 10
      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

  # can be optimized by checking in which dimension they are adjacent
  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
schedule = Array(Int, 5, day_hours, 4)

# generate random schedule of each intern's busy times
busy = ntuple(8, i -> fill((0,0,0), rand(0:5)))
for intern = 1:8
  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
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)
  remaining_hours = fill(20, 8)
	bad_schedule = false

	for day = 1:5, hour = 1:day_hours, position = 1:4
    not_tried = linspace(1, 8, 8)
		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:2
  for day = 1:5, hour = 1:day_hours, position = 1:4
    intern = schedule[day, hour, position]

    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 != (day, hour, position) && schedule[x[1], x[2], x[3]] == intern
    other_hours = filter(predicate, [(d, h, p) for d = 1:5, h = 1:day_hours, p = 1:4])
    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, metric((day, hour, position), x[1], nextpos(x...), schedule)), candidates)
    max = maxby(x -> x[2], scores)
    # has to check if it's ok to go there
    schedule[current...] = schedule[max[1][1]...]
    schedule[max[1][1]...] = intern
  end
end
println(schedule)