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
|
use std::io;
use std::io::BufRead;
use std::cmp::Ordering;
use std::collections::BinaryHeap;
#[derive(PartialEq, Eq)]
struct Decreasing<T>(T);
impl<T: PartialOrd> PartialOrd for Decreasing<T> {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
other.0.partial_cmp(&self.0)
}
}
impl<T: Ord> Ord for Decreasing<T> {
fn cmp(&self, other: &Self) -> Ordering {
other.0.cmp(&self.0)
}
}
fn simulation(nexts: &[Vec<u8>], nelves: i32, basetime: i32, inctime: i32) -> (String, i32) {
let mut incoming = [0 as u8; 26];
for tos in nexts.iter() {
for &to in tos {
incoming[to as usize] += 1;
}
}
let mut sources = BinaryHeap::new();
for i in 0..26 {
if incoming[i as usize] == 0 {
sources.push(Decreasing(i as u8));
}
}
#[derive(PartialEq, Eq, PartialOrd, Ord)]
struct Completed {
time: i32,
job: u8,
};
let mut evqu = BinaryHeap::new();
let mut order = String::new();
let mut elves = nelves;
let mut current_time = 0;
loop {
while elves > 0 && sources.len() > 0 {
let Decreasing(job) = sources.pop().unwrap();
evqu.push(Decreasing(Completed {time: current_time + basetime + inctime * (job as i32 + 1), job}));
elves -= 1;
}
match evqu.pop() {
Some(Decreasing(event)) => {
current_time = event.time;
order.push(char::from(event.job + 65));
for &to in &nexts[event.job as usize] {
incoming[to as usize] -= 1;
if incoming[to as usize] == 0 {
sources.push(Decreasing(to));
}
}
elves += 1;
}
None => break
};
}
(order, current_time)
}
pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
let mut nexts: Vec<Vec<u8>> = vec![vec![]; 26];
for l in reader.lines().map(|l| l.unwrap()) {
let (from, to) = (l.as_bytes()[5] - 65, l.as_bytes()[36] - 65);
nexts[from as usize].push(to);
}
let part1 = simulation(&nexts, 1, 1, 0).0;
let part2 = simulation(&nexts, 4, 60, 1).1.to_string();
Ok((part1, part2))
}
|
