Solve day7

1 files changed, 102 insertions, 0 deletions

diff --git a/day7/src/schedule.rs b/day7/src/schedule.rs
new file mode 100644
index 0000000..cddc926
--- /dev/null
+++ b/day7/src/schedule.rs
@@ -0,0 +1,102 @@
+use std::collections::HashSet;
+use {Vertex, Edge};
+
+#[derive(Copy, Clone)]
+struct Task {
+  vertex: Vertex,
+  duration: u32
+}
+
+static ASCII: [char; 26] = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I',
+                            'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R',
+                            'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];
+
+fn vertex_to_duration(v: &Vertex) -> u32 {
+  let index = ASCII.iter().position(|a| a == v).expect("Vertex not in list");
+  (index + 60 + 1) as u32
+}
+
+fn print_vertices(msg: &str, vertices: &Vec<Vertex>) {
+  println!("{}", msg);
+  print!("[");
+  for v in vertices {
+    print!("{}, ", &v);
+  }
+  print!("]\n");
+}
+
+fn print_tasks(msg: &str, tasks: &Vec<Task>) {
+  println!("{}", msg);
+  print!("[");
+  for t in tasks {
+    print!("({}, {}), ", &t.vertex, &t.duration);
+  }
+  print!("]\n");
+}
+
+pub fn find(V: &HashSet<Vertex>, E: &HashSet<Edge>, V_sources: &HashSet<Vertex>, worker_count: u32) -> u32 {
+  let mut done: Vec<Vertex> = Vec::new();
+  let mut ready: Vec<Task> = V_sources.iter()
+    .map(|&vertex| Task {vertex, duration: vertex_to_duration(&vertex) })
+    .collect();
+  let mut worked_on: Vec<Task> = Vec::new();
+
+  ready.sort_by(|t1, t2| t1.vertex.cmp(&t2.vertex));
+  let mut time: u32 = 0;
+
+  let n = V.len();
+  while done.len() != n {
+    print_vertices("done: ", &done);
+    print_tasks("worked_on: ", &worked_on);
+    print_tasks("ready: ", &ready);
+    while worked_on.len() < worker_count as usize && ready.len() > 0 {
+      let task = ready[0];
+      worked_on.push(task);
+      ready.remove(0);
+    }
+
+    let mut done_on_tick: Vec<Vertex> = Vec::new();
+    let mut new_worked_on: Vec<Task> = Vec::new();
+    for task in &worked_on {
+      let new_duration = task.duration - 1;
+      if new_duration == 0 {
+        done_on_tick.push(task.vertex);
+        done.push(task.vertex);
+      } else {
+        new_worked_on.push(Task { vertex: task.vertex, duration: new_duration });
+      }
+    }
+    worked_on = new_worked_on;
+
+    for vertex in &done_on_tick {
+      let destinations: Vec<Vertex> = E.iter()
+        .filter(|&(v1, _v2)| v1 == vertex)
+        .map(|&(_v1, v2)| v2)
+        .collect();
+
+      for dest_v in &destinations {
+        let sources: Vec<Vertex> = E.iter()
+          .filter(|&(_v1, v2)| *v2 == *dest_v)
+          .map(|&(v1, _v2)| v1)
+          .collect();
+
+        let mut ok = true;
+        for s in &sources {
+          if !done.contains(&s) {
+            ok = false;
+            break;
+          }
+        }
+
+        if ok {
+          ready.push(Task { vertex: *dest_v, duration: vertex_to_duration(&dest_v) });
+        }
+      }
+    }
+
+    ready.sort_by(|t1, t2| t1.vertex.cmp(&t2.vertex));
+    time += 1;
+  }
+
+  time
+}
\ No newline at end of file