From e415080d2c87d398340aeca9a76bdc7e83e99734 Mon Sep 17 00:00:00 2001
From: Jan Tuomi <jan.tuomi@eficode.com>
Date: Sat, 8 Dec 2018 18:17:25 +0200
Subject: Solve day7

---
 day7/src/topo_order.rs | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 54 insertions(+)
 create mode 100644 day7/src/topo_order.rs

(limited to 'day7/src/topo_order.rs')

diff --git a/day7/src/topo_order.rs b/day7/src/topo_order.rs
new file mode 100644
index 0000000..abb0738
--- /dev/null
+++ b/day7/src/topo_order.rs
@@ -0,0 +1,54 @@
+use std::collections::HashSet;
+use {Vertex, Edge};
+
+pub fn find(V: &HashSet<Vertex>, E: &HashSet<Edge>, V_sources: &HashSet<Vertex>) -> String {
+  let mut sources_vec: Vec<Vertex> = V_sources.iter().map(|&v| v).collect();
+  sources_vec.sort();
+
+  let sources_repr: String = sources_vec.iter().collect();
+  println!("sources_repr: {}", sources_repr);
+
+  let mut result: Vec<char> = Vec::new();
+  let mut ready: Vec<Vertex> = sources_vec;
+  loop {
+    if ready.len() == 0 {
+      break;
+    }
+
+    let v: Vertex = ready[0];
+    ready.remove(0);
+
+    if !result.contains(&v) {
+      result.push(v);
+    }
+
+    let destinations: Vec<Vertex> = E.iter()
+      .filter(|&(v1, _v2)| *v1 == v)
+      .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 !result.contains(&s) {
+          ok = false;
+          break;
+        }
+      }
+
+      if ok {
+        ready.push(*dest_v);
+      }
+    }
+
+    ready.sort();
+  }
+
+  let result_repr: String = result.into_iter().collect();
+  result_repr
+}
-- 
cgit v1.3