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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
extern crate advent_of_code_2018;
use advent_of_code_2018::*;
use std::error::Error;
use std::path::PathBuf;
use std::collections::{HashMap, HashSet};
// cargo watch -cs "cargo run --release --bin day_7"
fn main() -> Result<(), Box<Error>> {
let input = read_file(&PathBuf::from("inputs/7.txt"))?;
//println!("Input: {:?}", input);
let (all_steps, blockers) = parse(&input);
let mut serial_ordered = Vec::new();
let mut remaining_steps = all_steps.clone();
let mut remaining_blockers = blockers.clone();
while !remaining_steps.is_empty() {
let mut unblocked: Vec<char> = remaining_steps.iter()
.filter(|c| remaining_blockers.get(c).map(|blockers| blockers.is_empty()).unwrap_or(true))
.cloned()
.collect();
unblocked.sort();
let next_step = unblocked.first().unwrap().clone();
serial_ordered.push(next_step);
remaining_steps.remove(&next_step);
for (_k, mut v) in &mut remaining_blockers {
v.retain(|c| *c != next_step);
}
}
debug!(serial_ordered);
for c in serial_ordered {
print!("{}", c);
}
println!();
let workers = 5;
let mut worker_tasks: Vec<Task> = Vec::new();
let mut parallel_ordered = Vec::new();
let mut remaining_steps = all_steps.clone();
let mut remaining_blockers = blockers.clone();
let mut current_time = 0;
while !remaining_steps.is_empty() {
let mut unblocked: Vec<char> = remaining_steps.iter()
.filter(|c|
remaining_blockers.get(c).map(|blockers| blockers.is_empty()).unwrap_or(true)
&& !worker_tasks.iter().any(|w| w.t == **c)
)
.cloned()
.collect();
unblocked.sort();
let next_unblocked = if worker_tasks.len() < workers {
unblocked.first().cloned()
} else {
None
};
if let Some(next_task) = next_unblocked {
worker_tasks.push(Task {
t: next_task,
completion: current_time + time(next_task)
});
}
else {
//Advance time
worker_tasks.sort_by_key(|w| w.completion);
let complete = worker_tasks.swap_remove(0);
current_time = complete.completion;
let next_step = complete.t;
parallel_ordered.push(next_step);
remaining_steps.remove(&next_step);
for (_k, mut v) in &mut remaining_blockers {
v.retain(|c| *c != next_step);
}
}
}
debug!(parallel_ordered);
for c in parallel_ordered {
print!("{}", c);
}
println!();
debug!(current_time);
Ok(())
}
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
struct Task {
t: char,
completion: u32
}
fn parse(input: &Vec<String>) -> (HashSet<char>, HashMap<char, Vec<char>>) {
let mut blockers = HashMap::new();
let mut all_steps = HashSet::new();
for line in input {
//Step I must be finished before step C can begin.
let mut split = line.split_whitespace();
let blocker: char = split.nth(1).and_then(|x| x.chars().nth(0)).unwrap();
let blocked: char = split.nth(5).and_then(|x| x.chars().nth(0)).unwrap();
blockers.entry(blocked).or_insert(Vec::new()).push(blocker);
all_steps.insert(blocker);
all_steps.insert(blocked);
}
debug!(all_steps);
debug!(blockers);
(all_steps, blockers)
}
fn time(c: char) -> u32 {
let base_time = 60;
let char_time = c as u32 - 'A' as u32 + 1;
base_time + char_time
}
|
