scheduling problem in php

schedule.php

<?php

$day_start = 7;
$day_end = 19;
$positions = 4;
$people = 8;
$position_hours = 8;
$work_hours = 20;

$busy = [[[3,16,19]],
         [[0,14,16],[0,8,9],[1,9,10],[3,17,18],[3,13,16],[4,10,13]],
         [[4,12,13]],
         [],
         [],
         [[0,14,16],[1,18,19]],
         [[2,13,16],[3,15,16],[4,18,19]],
         []];
/* $busy = [[], */
/*          [], */
/*          [], */
/*          [], */
/*          [], */
/*          [], */
/*          [], */
/*          []]; */
/* $busy = [[[0, 7, 10], [1,9,16], [2,8,19],[3,7,14],[4,7,12],[4,16,17]], */
/*          [[0,7,19],[1,7,19],[2, 7, 14], [3, 8, 12], [4, 14, 17]], */
/*          [[0, 7, 12], [1,9,16], [2,11,11],[3,14,16],[4,12,14], [3, 7, 19]], */
/*          [[0, 7, 11], [1,11,17], [2,7,17],[3,9,11],[4,13,16]], */
/*          [[0, 7, 6], [2,13,19],[3,12,18],[4,13,18]], */
/*          [[0, 9, 14], [1,7,17],[3,11,17],[4,7,14]], */
/*          [[1,9,17], [2,7,17],[4,11,19], [4, 17, 19]], */
/*          [[0, 7, 19], [2,7,13], [2,16,19],[3,7,19]]]; */



/**
 * new_schedule
 * @param int $day_hours The amount of work hours per day for a position.
 * @param int $positions The number of positions for the schedule.
 * @return array A 3-dimensional array representing the schedule. The dimensions are respectively days, hours, positions.
 **/
function new_schedule($day_hours, $positions) {
  $schedule = array();
  for ($d = 0; $d < 5; $d++) {
    $schedule[] = array();
    for ($h = 0; $h < $day_hours; $h++) {
      $schedule[$d][] = array();
      for ($p = 0; $p < $positions; $p++) {
        $schedule[$d][$h][] = '-';
      }
    }
  }
  return $schedule;
}

/**
 * free
 * @param array $schedule The 3-dimensional array representing the schedule.
 * @param int $day_hours The amount of work hours per day for a position.
 * @param int $positions The number of positions for the schedule.
 * @return array An array of 3-tuples with coordinates of the free slots from the schedule.
 **/
function free($schedule, $day_hours, $positions) {
  $slots = array();

  for ($d = 0; $d < 5; $d++) {
    for ($h = 0; $h < $day_hours; $h++) {
      for ($p = 0; $p < $positions; $p++) {
        if ($schedule[$d][$h][$p] === '-') {
          $slots[] = [$d, $h, $p];
        }
      }
    }
  }

  return $slots;
}

/**
 * diff
 * @param array $xs The set from which the elements of $ys will be removed. (note: $xs will not be mutated)
 * @param array $ys The set, whose elements are going to be removed from $xs.
 * @return xs\ys
 **/
function diff($xs, $ys) {
  $diff = array();
  foreach ($xs as $x) {
    $is_present = false;
    foreach ($ys as $y) {
      if ($x == $y) {
        $is_present = true;
        break;
      }
    }
    if (!$is_present) {
      $diff[] = $x;
    }
  }
  return $diff;
}

/**
 * free_for
 * @param int $person The index of the person in $busy.
 * @param array $busy The innermost array is 3-tuple with (day, busy_start, busy_end) busy block. $busy has array of busy blocks for each person.
 * @param array $free The set of the free slots of the schedule.
 * @param int $day_start The hour in which the work day starts.
 * @param int $positions The number of positions for the schedule.
 * @return array free\busy_hours.
 **/
function free_for($person, $busy, $free, $day_start, $positions) {
  $busy_hours = array();

  $times = $busy[$person][1];
  foreach ($times as $time) {
    for ($h = $time[1]; $h < $time[2]; $h++) {
      for ($pos = 0; $pos < $positions; $pos++) {
        $busy_hours[] = [$time[0], $h - $day_start, $pos];
      }
    }
  }

  return diff($free, $busy_hours);
}

/**
 * busy_times_sum
 * @param array $table The busy table for a single person.
 * @return int The amount of hours the person, whose table is given, is busy per weak.
 **/
function busy_times_sum($table) {
  if (empty($table)) {
    return 0;
  }
  $blocks_times = array_map(function($x) {return $x[2] - $x[1];}, $table);
  return array_reduce($blocks_times, function($x, $y) {return $x + $y;});
}

/**
 * can_swap
 * @param int $p1 The index of the person, that can't be placed.
 * @param array $p2 3-tuple representing the coordinates (in the scheudule) of the candidate for swap.
 * @param array $pos The position where $p1 can't be placed.
 * @param array $schedule The 3-dimensional array representing the schedule.
 * @param array $p1_free_hours The set of free hours for $p1
 * @param array $p2_free_hours The set of free hours for $p2
 * @return bool Returns true if $p1 and $p2 can be swapped, false otherwise.
 **/
function can_swap($p1, $p2, $pos, $schedule, $p1_free_hours, $p2_free_hours) {
  # check if p1 is working at the same hour as the candidate slot on a different position
  if (!empty(array_filter($schedule[$p2[0]][$p2[1]], function($x) use($p1) { return $p1 == $x; }))) {
    return false;
  }
  # check if the candidate is working at the same hour as the free slot on a different position
  if (!empty(array_filter($schedule[$pos[0]][$pos[1]], function($x) use($p2, $schedule) {
    return $schedule[$p2[0]][$p2[1]][$p2[2]] == $x;
  }))) {
    return false;
  }
  # check whether the current person and the candidate are both free on the slots they will take.
  if (!in_array($pos, $p2_free_hours) || !in_array($p2, $p1_free_hours)) {
    return false;
  }
  return true;
}

/**
 * filter_full_positions
 * @param array $available The slots where the current person can be placed.
 * @param array $schedule The 3-dimensional array representing the schedule.
 * @param int $day_hours The amount of work hours per day for a position.
 * @param int $positions The number of positions for the schedule.
 * @param int $position_hours The amount of hours a position should be taken for a day.
 * @return array Returns the slots of $available that are in positions that are not full.
 **/
function filter_full_positions($available, $schedule, $day_hours, $positions, $position_hours) {
  $days = array();

  # get the amount of assigned hours for each position for each day
  for ($d = 0; $d < 5; $d++) {
    $days[$d] = array();
    for ($pos = 0; $pos < $positions; $pos++) {
      $count = 0;
      for ($h = 0; $h < $day_hours; $h++) {
        if ($schedule[$d][$h][$pos] !== '-') {
          $count++;
        }
      }
      if ($count < $position_hours) {
        $days[$d][] = $pos;
      }
    }
  }

  # the actual filtering
  $res = array();
  foreach ($available as $slot) {
    if (in_array($slot[2], $days[$slot[0]])) {
      $res[] = $slot;
    }
  }

  return $res;
}

/**
 * print_schedule
 * @param array $schedule The 3-dimensional array representing the schedule.
 * @param int $positions The number of positions for the schedule.
 **/
function print_schedule($schedule, $positions) {
  for ($pos = 0; $pos < $positions; $pos++) {
    foreach ($schedule as $day) {
      foreach ($day as $hour) {
        print $hour[$pos];
        print ' ';
      }
      print "\n";
    }
    print "\n\n";
  }
}

/**
 * algorithm
 * @param int $day_start The hour when the workday starts.
 * @param int $day_end The hour when the workday ends.
 * @param int $positions The number of positions for the schedule.
 * @param int $people The number of people for which a schedule will be generated.
 * @param int $position_hours The amount of hours a position should be taken for a day.
 * @param int $work_hours The amount of hours one has to work for the company per week.
 * @param array $busy The innermost array is 3-tuple with (day, busy_start, busy_end) busy block. $busy has array of busy blocks for each person.
 * @return array The 3-dimensional array representing the schedule.
 **/
function algorithm($day_start, $day_end, $positions, $people, $position_hours, $work_hours, $busy) {
  $day_hours = $day_end - $day_start;
  $schedule = new_schedule($day_hours, $positions);

  for ($i = 0; $i < count($busy); $i++) {
    $busy[$i] = [$i, $busy[$i]];
  }

  # solt busy, so that the busiest people are first
  usort($busy, function($x, $y) {
    if (busy_times_sum($x[1]) == busy_times_sum($y[1])) {
      return 0;
    }
    return (busy_times_sum($x[1]) > busy_times_sum($y[1])) ? -1 : 1;
  });

  for ($person = 0; $person < $people; $person++) {
    $free_slots = free($schedule, $day_hours, $positions);
    $available = free_for($person, $busy, $free_slots, $day_start, $positions);

    # opt for filling the first available hours for EACH day instead for all available of the first days
    $arangement = [[], [], [], [], []];
    foreach ($available as $a) {
      $arangement[$a[0]][] = $a;
    }
    $new_available = array();
    for ($i = 0; true; $i++) {
      $all_ended = true;
      $current = false;
      foreach ($arangement as $a) {
        $current = array_key_exists($i, $a);
        if ($current) {
          $new_available[] = $a[$i];
        }
        $all_ended = $all_ended && !$current;
      }
      if ($all_ended) break;
    }
    $available = $new_available;

    $available = filter_full_positions($available, $schedule, $day_hours, $positions, $position_hours);

    for ($hour = 0; $hour < $work_hours; $hour++) {
      if (!empty($available)) {
        $current = $available[0];
        $schedule[$current[0]][$current[1]][$current[2]] = $busy[$person][0];
        # remove the slots for all positions on the assigned day-hour (our man is already assigned for that time)
        $just_taken = array();
        for ($pos = 0; $pos < $positions; $pos++) {
          $just_taken[] = [$current[0], $current[1], $pos];
        }
        $available = diff($available, $just_taken);
        $available = filter_full_positions($available, $schedule, $day_hours, $positions, $position_hours);
      } else {
        $swapped = false;
        $indexes = array();
        # get the indexes of all free slots
        for ($p = 0; $p < $positions; $p++) {
          for ($d = 0; $d < 5; $d++) {
            for ($h = 0; $h < $day_hours; $h++) {
              if ($schedule[$d][$h][$p] === '-') {
                $indexes[] = [$d, $h, $p];
              }
            }
          }
        }
        $indexes = filter_full_positions($indexes, $schedule, $day_hours, $positions, $position_hours);
        # if no free slots, can't do nothing more
        if (empty($indexes)) {
          break;
        }
        $index = $indexes[0];

        for ($d = 0; $d < 5; $d++) {
          for ($h = 0; $h < $day_hours; $h++) {
            for ($p = 0; $p < $positions; $p++) {
              # get the index (in busy) of our candidate
              $p2_index = -1;
              $i = 0;
              foreach ($busy as $b) {
                if ($b[0] == $schedule[$d][$h][$p]) {
                  $p2_index = $i;
                  break;
                }
                $i++;
              }
              if ($p2_index == -1) {
                continue;
              }

              $free = free(new_schedule($day_hours, $positions), $day_hours, $positions);
              $p1_free_hours = free_for($person, $busy, $free, $day_start, $positions);
              $p2_free_hours = free_for($p2_index, $busy, $free, $day_start, $positions);

              if (can_swap($busy[$person][0], [$d, $h, $p], $index, $schedule, $p1_free_hours, $p2_free_hours)) {
                $swapped = true;
                $schedule[$index[0]][$index[1]][$index[2]] = $schedule[$d][$h][$p];
                $schedule[$d][$h][$p] = $busy[$person][0];
                break(3);
              }
            }
          }
        }

        # if the current guy couldn't be swapped, then we forfeit and print the progress we've made
        if (!$swapped) {
          echo "Error! The algorithm couldn't create a schedule for the given arguments. (Can't place ", $busy[$person][0], ").\n";
          echo "Here is the schedule so far...\n";
          print_schedule($schedule, $positions);
          exit();
        }
      }
    }
  }

  print_schedule($schedule, $positions);
  return $schedule
}

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