Day 7

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))
 }