-
Notifications
You must be signed in to change notification settings - Fork 0
/
solution.php
executable file
·113 lines (103 loc) · 4.18 KB
/
solution.php
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#!/usr/bin/env php
<?php
include("common.php");
$lines = read_input();
define('TASK_WORKER_COUNT', 5); // should be 5 in production
define('TASK_MIN_DURATION', 60); // should be 60 in production
$c=0;
$nodeIDs = []; $edges = [];
foreach($lines as $line){
if(preg_match_all("/Step (.) must be finished before step (.) can begin/", $line, $b)){
[$s,$e]=[$b[1][0], $b[2][0]];
$nodeIDs[]=$s;
$nodeIDs[]=$e;
$edges[]=[$s,$e];
}
$c++;
}
$nodeIDs=array_unique($nodeIDs); sort($nodeIDs);
[$tasks,$taskBlocks]=topological_sort($nodeIDs,$edges);
printf("Part 1 task order should be %s\n", join("", $tasks));
$times = array_flip($nodeIDs);
foreach($times as $k=>&$v)$v+=TASK_MIN_DURATION;
$nWorkers = TASK_WORKER_COUNT; $workers=[]; for($i=0; $i<$nWorkers; $i++) $workers[$i]=['.', 0];
$t=-1; $done=[]; $doing = []; $uncompleted = $tasks;
while(true){
if(count($uncompleted)===0)break;
if($t>99999)break;
$t++;
$runningWorkers = 0;
foreach($workers as $wi=>&$worker){
$unblockedTasks = array_diff(Akeys(array_filter($taskBlocks, function($x){ return count($x)===0; })), $doing); $nRemainingTasks = count($unblockedTasks);
$cTask = $worker[0];
if($worker[1]===0){
if($cTask!=='.'){
unset($taskBlocks[ $cTask ]); foreach($taskBlocks as &$tlist) $tlist = array_diff($tlist, [$cTask]);
$done["t{$t}w{$wi}"] = $cTask;
$doing = array_filter($doing, function($e) use($cTask) { return ($cTask !== $e);} );
$uncompleted = array_filter($uncompleted, function($e) use ($cTask) { return $cTask !== $e; } );
$worker = ['.', 0];
$unblockedTasks = array_diff(Akeys(array_filter($taskBlocks, function($x){ return count($x)===0; })), $doing); $nRemainingTasks = count($unblockedTasks);
}
if($nRemainingTasks>0){
$cTask = array_shift($unblockedTasks); $nRemainingTasks--;
$worker[0] = $cTask;
$worker[1] = $times[$cTask];
$doing["w{$wi}"]=$cTask;
$runningWorkers++;
}else{
$worker = ['.', 0];
}
}else{
$worker[1]--;
$runningWorkers++;
}
}
//printf("t: %3d | RW: %d | workers: [ %6s ] | done: [ %-10s ]\n", $t, $runningWorkers, join('', Acolumn($workers,0)), join('',Avals($done)));
}
printf("Part 2 total time: %d\n",$t);
///////////////////////////////////////////////////////////////////////////////////////////////////////////
/// Uses topological_sort/2 from https://stackoverflow.com/questions/11953021/topological-sorting-in-php
function topological_sort(array $nodeIDs, array $edges): array {
$L = $S = $nodes = array();
// remove duplicate nodes
$nodeIDs= array_unique($nodeIDs);
// remove duplicate edges
$hashes = array(); foreach($edges as $k=>$e) {
$hash = md5(serialize($e));
if (in_array($hash, $hashes)) { unset($edges[$k]); }
else { $hashes[] = $hash; };
}
foreach($nodeIDs as $id) {
$nodes[$id] = array('in'=>array(), 'out'=>array());
foreach($edges as $e) {
if ($id==$e[1]) { $nodes[$id]['in'][]=$e[0]; }
if ($id==$e[0]) { $nodes[$id]['out'][]=$e[1]; }
}
}
function blockedBy($nodes, $nid){
$in = $input = $nodes[$nid]['in'];
if(count($in) === 0) return [];
$result = $in; foreach( $in as $pid ) {
$result = array_merge($result, blockedBy($nodes, $pid));
}
return array_unique($result);
}
$blocks = []; foreach($nodeIDs as $id) $blocks[ $id ] = blockedBy($nodes, $id);
foreach ($nodes as $id=>$n) { if (empty($n['in'])) $S[]=$id; }
while (!empty($S)) {
sort($S);
$L[] = $id = array_shift($S);
foreach($nodes[$id]['out'] as $m) {
$nodes[$m]['in'] = array_diff($nodes[$m]['in'], array($id));
if (empty($nodes[$m]['in'])) { $S[] = $m; }
}
$nodes[$id]['out'] = array();
}
foreach($nodes as $n) {
if (!empty($n['in']) or !empty($n['out'])) {
return null; // not sortable as graph is cyclic
}
}
return [$L, $blocks];
}