From 6a483ed6ee8a597cd0e315fe86f9ec2564eb4134 Mon Sep 17 00:00:00 2001 From: Justin Worthe Date: Fri, 7 Dec 2018 07:44:34 +0200 Subject: Day 7: Task scheduling --- inputs/7.txt | 101 ++++++++++++++++++++++++++++++++++++++++++++++ src/bin/day_7.rs | 119 ++++++++++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 219 insertions(+), 1 deletion(-) create mode 100644 inputs/7.txt diff --git a/inputs/7.txt b/inputs/7.txt new file mode 100644 index 0000000..3fe80cb --- /dev/null +++ b/inputs/7.txt @@ -0,0 +1,101 @@ +Step E must be finished before step Y can begin. +Step Y must be finished before step T can begin. +Step I must be finished before step C can begin. +Step G must be finished before step F can begin. +Step C must be finished before step P can begin. +Step B must be finished before step Q can begin. +Step Z must be finished before step N can begin. +Step J must be finished before step W can begin. +Step W must be finished before step P can begin. +Step K must be finished before step D can begin. +Step Q must be finished before step L can begin. +Step V must be finished before step D can begin. +Step O must be finished before step M can begin. +Step A must be finished before step P can begin. +Step M must be finished before step L can begin. +Step R must be finished before step S can begin. +Step D must be finished before step X can begin. +Step X must be finished before step N can begin. +Step P must be finished before step T can begin. +Step F must be finished before step N can begin. +Step S must be finished before step L can begin. +Step U must be finished before step N can begin. +Step T must be finished before step L can begin. +Step N must be finished before step H can begin. +Step L must be finished before step H can begin. +Step N must be finished before step L can begin. +Step X must be finished before step F can begin. +Step P must be finished before step F can begin. +Step P must be finished before step H can begin. +Step B must be finished before step D can begin. +Step V must be finished before step H can begin. +Step X must be finished before step S can begin. +Step Q must be finished before step O can begin. +Step Z must be finished before step T can begin. +Step K must be finished before step N can begin. +Step S must be finished before step H can begin. +Step M must be finished before step P can begin. +Step Q must be finished before step D can begin. +Step R must be finished before step U can begin. +Step J must be finished before step P can begin. +Step P must be finished before step S can begin. +Step V must be finished before step U can begin. +Step R must be finished before step T can begin. +Step F must be finished before step S can begin. +Step D must be finished before step T can begin. +Step E must be finished before step N can begin. +Step J must be finished before step N can begin. +Step J must be finished before step A can begin. +Step K must be finished before step U can begin. +Step V must be finished before step N can begin. +Step V must be finished before step S can begin. +Step U must be finished before step L can begin. +Step F must be finished before step U can begin. +Step I must be finished before step T can begin. +Step J must be finished before step L can begin. +Step E must be finished before step T can begin. +Step T must be finished before step N can begin. +Step I must be finished before step G can begin. +Step R must be finished before step D can begin. +Step E must be finished before step B can begin. +Step X must be finished before step H can begin. +Step P must be finished before step L can begin. +Step Z must be finished before step J can begin. +Step O must be finished before step L can begin. +Step E must be finished before step H can begin. +Step F must be finished before step T can begin. +Step A must be finished before step F can begin. +Step U must be finished before step H can begin. +Step F must be finished before step H can begin. +Step C must be finished before step W can begin. +Step A must be finished before step L can begin. +Step V must be finished before step M can begin. +Step U must be finished before step T can begin. +Step E must be finished before step P can begin. +Step Y must be finished before step U can begin. +Step W must be finished before step R can begin. +Step E must be finished before step X can begin. +Step Q must be finished before step U can begin. +Step I must be finished before step F can begin. +Step V must be finished before step F can begin. +Step V must be finished before step T can begin. +Step R must be finished before step P can begin. +Step B must be finished before step A can begin. +Step S must be finished before step T can begin. +Step M must be finished before step F can begin. +Step Y must be finished before step F can begin. +Step C must be finished before step K can begin. +Step D must be finished before step S can begin. +Step O must be finished before step S can begin. +Step M must be finished before step U can begin. +Step Z must be finished before step S can begin. +Step R must be finished before step H can begin. +Step C must be finished before step O can begin. +Step G must be finished before step Q can begin. +Step Z must be finished before step D can begin. +Step B must be finished before step N can begin. +Step I must be finished before step H can begin. +Step I must be finished before step P can begin. +Step E must be finished before step J can begin. +Step V must be finished before step L can begin. +Step B must be finished before step U can begin. diff --git a/src/bin/day_7.rs b/src/bin/day_7.rs index 3e65fb4..ec9d0be 100644 --- a/src/bin/day_7.rs +++ b/src/bin/day_7.rs @@ -4,15 +4,132 @@ 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> { let input = read_file(&PathBuf::from("inputs/7.txt"))?; - println!("Input: {:?}", input); + //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 = 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 = 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 = 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) -> (HashSet, HashMap>) { + 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 +} -- cgit v1.2.3