Skip to content

Instantly share code, notes, and snippets.

@mzdravkov

mzdravkov/generate.php

Created July 9, 2015 12:27
Show Gist options
  • Save mzdravkov/357b4322b448d908224b to your computer and use it in GitHub Desktop.
Save mzdravkov/357b4322b448d908224b to your computer and use it in GitHub Desktop.
Download ZIP
Basic web interface for the scheduling problem.
Raw
generate.php
<?php
include 'schedule.php';
$day_start = (int)$_POST['day_start'];
$day_end = (int)$_POST['day_end'];
$positions = (int)$_POST['positions'];
$people = (int)$_POST['people'];
$position_hours = (int)$_POST['position_hours'];
$work_hours = (int)$_POST['work_hours'];
if ($day_start >= $day_end ||
$people * $work_hours != $positions * $position_hours * 5) {
/* http_redirect('new.php', ['failed' => true]); */
header("()Location: new.php?failed=true");
die();
}
$day_pattern = '/person_(\d+)_day_(\d+)/';
$start_pattern = '/person_(\d+)_start_(\d+)/';
$end_pattern = '/person_(\d+)_end_(\d+)/';
$busy = array();
foreach ($_POST as $param) {
$matches = array();
$is_day = preg_match($day_pattern, $param, $matches);
$is_start = preg_match($start_pattern, $param, $matches);
$is_end = preg_match($end_pattern, $param, $matches);
$pos = -1;
if ($is_day) $pos = 0;
if ($is_start) $pos = 1;
if ($is_end) $pos = 2;
if ($pos == -1) continue;
if (!array_key_exists(int($matches[1]), $busy)) {
$busy[int($matches[1])] = array();
}
$busy[int($matches[1])][$pos] = int($matches[2]);
}
for ($i = 0; $i < $people; $i++) {
if (!array_key_exists($i, $busy)) {
$busy[$i] = [];
}
}
$schedule = algorithm($day_start, $day_end, $positions, $people, $position_hours, $work_hours, $busy);
/* header("Location: /?schedule=".$schedule); */
/* die(); */
for ($pos = 0; $pos < $positions; $pos++) {
foreach ($schedule as $day) {
foreach ($day as $hour) {
echo $hour[$pos];
echo ' ';
}
?><br/><?php
}
?><br/><br/><?php
}
?>
<a href="/">Go back to the index</>
Raw
index.html
<html>
<head>
<title>Schedule</title>
</head>
<body>
<a href="/new.php">New schedule</a>
</body>
</html>
Raw
new.php
<html>
<head>
<title>Schedule</title>
<script language="javascript">
function add(div_id) {
var div = document.getElementById(div_id);
var day = document.createElement("select");
var start = document.createElement("select");
var end = document.createElement("select");
for (k = 0; k < 5; k++) {
var opt = document.createElement('option');
opt.value = k;
opt.innerHTML = k;
day.appendChild(opt);
}
day_start = parseInt(document.forms[0].day_start.value);
day_end = parseInt(document.forms[0].day_end.value);
for (k = day_start; k < day_end ; k++) {
var opt = document.createElement('option');
opt.value = k;
opt.innerHTML = k;
start.appendChild(opt);
}
for (k = day_start+1; k <= day_end ; k++) {
var opt = document.createElement('option');
opt.value = k;
opt.innerHTML = k;
end.appendChild(opt);
}
current = (div.children.length - 2) / 3;
var day_input = document.createElement("input");
day_input.setAttribute('name', div_id + '_day_' + current);
day_input.setAttribute('id', div_id + '_day_' + current);
day_input.setAttribute('type', 'hidden');
day_input.setAttribute('value', day.value);
var start_input = document.createElement("input");
start_input.setAttribute('name', div_id + '_start_' + current);
start_input.setAttribute('id', div_id + '_start_' + current);
start_input.setAttribute('type', 'hidden');
start_input.setAttribute('value', start.value);
var end_input = document.createElement("input");
end_input.setAttribute('name', div_id + '_end_' + current);
end_input.setAttribute('id', div_id + '_end_' + current);
end_input.setAttribute('type', 'hidden');
end_input.setAttribute('value', end.value);
hidden = document.getElementById('hidden');
hidden.appendChild(day_input);
hidden.appendChild(start_input);
hidden.appendChild(end_input);
command = 'document.getElementById("' + div_id + '_day_' + current + '").value = this.value;';
day.setAttribute('onchange', command);
command = 'document.getElementById("' + div_id + '_start_' + current + '").value = this.value;';
start.setAttribute('onchange', command);
command = 'document.getElementById("' + div_id + '_end_' + current + '").value = this.value;';
end.setAttribute('onchange', command);
div.appendChild(day);
div.appendChild(start);
div.appendChild(end);
}
function new_table() {
if (document.getElementById('person_0')) {
node = document.getElementById('busy_table');
while (node.hasChildNodes()) {
node.removeChild(node.lastChild);
}
node = document.getElementById('hidden');
while (node.hasChildNodes()) {
node.removeChild(node.lastChild);
}
}
num = document.forms[0].people.value;
for (i = 0; i < num; i++) {
new_block_button = document.createElement('button');
command = 'add("person_' + i + '")';
new_block_button.setAttribute('onclick', command);
new_block_button.setAttribute('type', 'button');
new_block_button.innerHTML = "Add busy block";
busy_table = document.getElementById('busy_table');
person = document.createElement('div');
person.setAttribute('id', 'person_' + i);
busy_table.appendChild(person);
person.appendChild(document.createElement('br'));
person.appendChild(new_block_button);
/* add('person_' + i); */
}
}
</script>
</head>
<body>
<h2>Generate new schedule</h2>
<p>
<?php
if (key_exists('failed', $_GET)) {
echo 'Bad input!';
}
?>
</p>
<form action="/generate.php" method="post">
<p>
<label for="day_start"> Day start: </label>
<input type="number" name="day_start" value=7 min=0 max=24><br/>
<label for="day_end"> Day end: </label>
<input type="number" name="day_end" value=19 min=0 max=24><br/>
<label for="positions"> Positions: </label>
<input type="number" name="positions" value=4 min=1><br/>
<label for="people"> People: </label>
<input type="number" name="people" value=8 min=0><br/>
<label for="position_hours"> Position hours: </label>
<input type="number" name="position_hours" value=8 min=1><br/>
<label for="work_hours"> Work hours: </label>
<input type="number" name="work_hours" value=20 min=1><br/>
</p>
<p>
<h3>Busy:</h3><br/>
<input type="button" value="New busy table" onclick="new_table()"/>
<div id="busy_table"> </div>
<div id="hidden"> </div>
</p>
<p>
<input type="submit" value="Submit">
</p>
</form>
</body>
</html>
Raw
schedule.php
<?php
/**
* 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();
}
}
}
}
return $schedule;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment