summaryrefslogtreecommitdiff
path: root/2018/src/bin/day_7.rs
diff options
context:
space:
mode:
Diffstat (limited to '2018/src/bin/day_7.rs')
-rw-r--r--2018/src/bin/day_7.rs135
1 files changed, 135 insertions, 0 deletions
diff --git a/2018/src/bin/day_7.rs b/2018/src/bin/day_7.rs
new file mode 100644
index 0000000..ec9d0be
--- /dev/null
+++ b/2018/src/bin/day_7.rs
@@ -0,0 +1,135 @@
+extern crate advent_of_code_2018;
+use advent_of_code_2018::*;
+
+use std::error::Error;
+use std::path::PathBuf;
+
+use std::collections::{HashMap, HashSet};
+
+// cargo watch -cs "cargo run --release --bin day_7"
+
+fn main() -> Result<(), Box<Error>> {
+ let input = read_file(&PathBuf::from("inputs/7.txt"))?;
+
+ //println!("Input: {:?}", input);
+
+ let (all_steps, blockers) = parse(&input);
+
+
+ let mut serial_ordered = Vec::new();
+ let mut remaining_steps = all_steps.clone();
+ let mut remaining_blockers = blockers.clone();
+
+ while !remaining_steps.is_empty() {
+ let mut unblocked: Vec<char> = remaining_steps.iter()
+ .filter(|c| remaining_blockers.get(c).map(|blockers| blockers.is_empty()).unwrap_or(true))
+ .cloned()
+ .collect();
+ unblocked.sort();
+
+ let next_step = unblocked.first().unwrap().clone();
+
+ serial_ordered.push(next_step);
+ remaining_steps.remove(&next_step);
+ for (_k, mut v) in &mut remaining_blockers {
+ v.retain(|c| *c != next_step);
+ }
+ }
+
+ debug!(serial_ordered);
+ for c in serial_ordered {
+ print!("{}", c);
+ }
+ println!();
+
+
+ let workers = 5;
+ let mut worker_tasks: Vec<Task> = Vec::new();
+ let mut parallel_ordered = Vec::new();
+ let mut remaining_steps = all_steps.clone();
+ let mut remaining_blockers = blockers.clone();
+ let mut current_time = 0;
+
+ while !remaining_steps.is_empty() {
+ let mut unblocked: Vec<char> = remaining_steps.iter()
+ .filter(|c|
+ remaining_blockers.get(c).map(|blockers| blockers.is_empty()).unwrap_or(true)
+ && !worker_tasks.iter().any(|w| w.t == **c)
+ )
+ .cloned()
+ .collect();
+ unblocked.sort();
+
+ let next_unblocked = if worker_tasks.len() < workers {
+ unblocked.first().cloned()
+ } else {
+ None
+ };
+
+ if let Some(next_task) = next_unblocked {
+ worker_tasks.push(Task {
+ t: next_task,
+ completion: current_time + time(next_task)
+ });
+ }
+ else {
+ //Advance time
+ worker_tasks.sort_by_key(|w| w.completion);
+ let complete = worker_tasks.swap_remove(0);
+ current_time = complete.completion;
+ let next_step = complete.t;
+
+ parallel_ordered.push(next_step);
+ remaining_steps.remove(&next_step);
+ for (_k, mut v) in &mut remaining_blockers {
+ v.retain(|c| *c != next_step);
+ }
+ }
+
+
+ }
+
+ debug!(parallel_ordered);
+ for c in parallel_ordered {
+ print!("{}", c);
+ }
+ println!();
+ debug!(current_time);
+
+
+ Ok(())
+}
+
+#[derive(Debug, Copy, Clone, PartialEq, Eq)]
+struct Task {
+ t: char,
+ completion: u32
+}
+
+
+fn parse(input: &Vec<String>) -> (HashSet<char>, HashMap<char, Vec<char>>) {
+ let mut blockers = HashMap::new();
+ let mut all_steps = HashSet::new();
+
+ for line in input {
+ //Step I must be finished before step C can begin.
+ let mut split = line.split_whitespace();
+ let blocker: char = split.nth(1).and_then(|x| x.chars().nth(0)).unwrap();
+ let blocked: char = split.nth(5).and_then(|x| x.chars().nth(0)).unwrap();
+
+ blockers.entry(blocked).or_insert(Vec::new()).push(blocker);
+ all_steps.insert(blocker);
+ all_steps.insert(blocked);
+ }
+
+ debug!(all_steps);
+ debug!(blockers);
+
+ (all_steps, blockers)
+}
+
+fn time(c: char) -> u32 {
+ let base_time = 60;
+ let char_time = c as u32 - 'A' as u32 + 1;
+ base_time + char_time
+}