summaryrefslogtreecommitdiff
path: root/2018/src
diff options
context:
space:
mode:
authortomsmeding <tom.smeding@gmail.com>2018-12-07 20:23:31 +0100
committertomsmeding <tom.smeding@gmail.com>2018-12-07 20:23:31 +0100
commit7c41554094bd50cb21937e71deec6dac411eb4f5 (patch)
tree683f3620a7751e5db9dafe946f90d22b93ac0089 /2018/src
parent2bf13506380721f0fd00be81b80792b0c0a001ca (diff)
Day 7
Diffstat (limited to '2018/src')
-rw-r--r--2018/src/day7.rs59
1 files changed, 42 insertions, 17 deletions
diff --git a/2018/src/day7.rs b/2018/src/day7.rs
index 1924916..e44bca1 100644
--- a/2018/src/day7.rs
+++ b/2018/src/day7.rs
@@ -4,22 +4,22 @@ use std::cmp::Ordering;
use std::collections::BinaryHeap;
#[derive(PartialEq, Eq)]
-struct DecreasingU8(u8);
+struct Decreasing<T>(T);
-impl PartialOrd for DecreasingU8 {
+impl<T: PartialOrd> PartialOrd for Decreasing<T> {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
- Some(self.cmp(other))
+ other.0.partial_cmp(&self.0)
}
}
-impl Ord for DecreasingU8 {
+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; 26];
+ let mut incoming = [0 as u8; 26];
for tos in nexts.iter() {
for &to in tos {
incoming[to as usize] += 1;
@@ -29,23 +29,47 @@ fn simulation(nexts: &[Vec<u8>], nelves: i32, basetime: i32, inctime: i32) -> (S
let mut sources = BinaryHeap::new();
for i in 0..26 {
if incoming[i as usize] == 0 {
- sources.push(DecreasingU8(i));
+ 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();
- while sources.len() > 0 {
- let DecreasingU8(i) = sources.pop().unwrap();
- order.push(char::from(i + 65));
- for &to in &nexts[i as usize] {
- incoming[to as usize] -= 1;
- if incoming[to as usize] == 0 {
- sources.push(DecreasingU8(to));
- }
+ 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, 0)
+ (order, current_time)
}
pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
@@ -55,7 +79,8 @@ pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
nexts[from as usize].push(to);
}
- let (part1, _) = simulation(&nexts, 1, 1, 0);
+ let part1 = simulation(&nexts, 1, 1, 0).0;
+ let part2 = simulation(&nexts, 4, 60, 1).1.to_string();
- Ok((part1, String::new()))
+ Ok((part1, part2))
}