Solve day7

7 files changed, 310 insertions, 0 deletions

diff --git a/day7/.vscode/launch.json b/day7/.vscode/launch.json
new file mode 100644
index 0000000..1d370e8
--- /dev/null
+++ b/day7/.vscode/launch.json
@@ -0,0 +1,43 @@
+{
+  // Use IntelliSense to learn about possible attributes.
+  // Hover to view descriptions of existing attributes.
+  // For more information, visit: https://go.microsoft.com/fwlink/?linkid=830387
+  "version": "0.2.0",
+  "configurations": [
+    {
+      "type": "lldb",
+      "request": "launch",
+      "name": "Debug executable 'day7'",
+      "cargo": {
+        "args": [
+          "build",
+          "--bin=day7",
+          "--package=day7"
+        ],
+        "filter": {
+          "kind": "bin"
+        }
+      },
+      "args": ["input_ex.txt"],
+      "cwd": "${workspaceFolder}"
+    },
+    {
+      "type": "lldb",
+      "request": "launch",
+      "name": "Debug unit tests in executable 'day7'",
+      "cargo": {
+        "args": [
+          "test",
+          "--no-run",
+          "--bin=day7",
+          "--package=day7"
+        ],
+        "filter": {
+          "kind": "bin"
+        }
+      },
+      "args": [],
+      "cwd": "${workspaceFolder}"
+    }
+  ]
+}
\ No newline at end of file
diff --git a/day7/Cargo.lock b/day7/Cargo.lock
new file mode 100644
index 0000000..a262d55
--- /dev/null
+++ b/day7/Cargo.lock
@@ -0,0 +1,14 @@
+[[package]]
+name = "day7"
+version = "0.1.0"
+dependencies = [
+ "text_io 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "text_io"
+version = "0.1.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[metadata]
+"checksum text_io 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)" = "9658b61ebd1d2a40c276ba2335890b9eb6550b67458a6fbce2022e58c3350a50"
diff --git a/day7/Cargo.toml b/day7/Cargo.toml
new file mode 100644
index 0000000..3f8c455
--- /dev/null
+++ b/day7/Cargo.toml
@@ -0,0 +1,7 @@
+[package]
+name = "day7"
+version = "0.1.0"
+authors = ["Jan Tuomi <jan.tuomi@eficode.com>"]
+
+[dependencies]
+text_io = "0.1.7"
diff --git a/day7/input_ex.txt b/day7/input_ex.txt
new file mode 100644
index 0000000..1dfd2ea
--- /dev/null
+++ b/day7/input_ex.txt
@@ -0,0 +1,7 @@
+Step C must be finished before step A can begin.
+Step C must be finished before step F can begin.
+Step A must be finished before step B can begin.
+Step A must be finished before step D can begin.
+Step B must be finished before step E can begin.
+Step D must be finished before step E can begin.
+Step F must be finished before step E can begin.
\ No newline at end of file
diff --git a/day7/src/main.rs b/day7/src/main.rs
new file mode 100644
index 0000000..f79f5fe
--- /dev/null
+++ b/day7/src/main.rs
@@ -0,0 +1,83 @@
+use std::env;
+use std::io::BufReader;
+use std::io::BufRead;
+use std::fs::File;
+use std::process;
+use std::collections::HashSet;
+
+#[macro_use] extern crate text_io;
+
+mod topo_order;
+mod schedule;
+
+type Vertex = char;
+type Edge = (Vertex, Vertex);
+
+fn main() {
+  let args: Vec<String> = env::args().collect();
+  if args.len() != 3 {
+    println!("Wrong number of arguments. Provide a file name and worker count.");
+    process::exit(1);
+  }
+  let filename = &args[1];
+  let worker_count: u32 = args[2].parse().expect("Cannot parse worker count.");
+  println!("Using file {} as input.", filename);
+  let f = match File::open(filename) {
+    Ok(file) => file,
+    Err(e) => {
+      println!("Failed to open file {}. {:?}", filename, e);
+      process::exit(1);
+    }
+  };
+  let file = BufReader::new(&f);
+  let lines: Vec<String> = file.lines()
+    .map(|line| line.expect("Could not parse line."))
+    .collect();
+
+  let mut V: HashSet<Vertex> = HashSet::new();
+  let mut E: HashSet<Edge> = HashSet::new();
+  let mut V_sources: HashSet<Vertex> = HashSet::new();
+  let mut V_sinks: HashSet<Vertex> = HashSet::new();
+  for line in &lines {
+    let (s1, s2): (String, String);
+    scan!(line.bytes() => "Step {} must be finished before step {} can begin.", s1, s2);
+    assert_eq!(s1.len(), 1);
+    assert_eq!(s2.len(), 1);
+    let ch1: Vec<char> = s1.chars().collect();
+    let ch2: Vec<char> = s2.chars().collect();
+    let v1 = ch1[0] as Vertex;
+    let v2 = ch2[0] as Vertex;
+    let e = (v1, v2) as Edge;
+
+    V.insert(v1);
+    V.insert(v2);
+    E.insert(e);
+  }
+
+  for v in &V {
+    let edges_where_source: Vec<&Edge> = E.iter()
+      .filter(|&(v1, _v2)| *v1 == *v)
+      .collect();
+    if edges_where_source.len() == 0 {
+      V_sinks.insert(*v);
+    }
+
+    let edges_where_sink: Vec<&Edge> = E.iter()
+      .filter(|&(_v1, v2)| *v2 == *v)
+      .collect();
+    if edges_where_sink.len() == 0 {
+      V_sources.insert(*v);
+    }
+  }
+
+  println!("V_sources len: {}", V_sources.len());
+  println!("V_sinks len: {}", V_sinks.len());
+  println!("V len: {}", V.len());
+  println!("E len: {}", E.len());
+
+  let result_1 = topo_order::find(&V, &E, &V_sources);
+  println!("1. Result: {}", result_1);
+
+  let result_2 = schedule::find(&V, &E, &V_sources, worker_count);
+  println!("2. Result: {}", result_2);
+}
\ No newline at end of file
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
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
+}