From e415080d2c87d398340aeca9a76bdc7e83e99734 Mon Sep 17 00:00:00 2001 From: Jan Tuomi Date: Sat, 8 Dec 2018 18:17:25 +0200 Subject: Solve day7 --- day7/.vscode/launch.json | 43 ++++++++++++++++++++ day7/Cargo.lock | 14 +++++++ day7/Cargo.toml | 7 ++++ day7/input_ex.txt | 7 ++++ day7/src/main.rs | 83 ++++++++++++++++++++++++++++++++++++++ day7/src/schedule.rs | 102 +++++++++++++++++++++++++++++++++++++++++++++++ day7/src/topo_order.rs | 54 +++++++++++++++++++++++++ 7 files changed, 310 insertions(+) create mode 100644 day7/.vscode/launch.json create mode 100644 day7/Cargo.lock create mode 100644 day7/Cargo.toml create mode 100644 day7/input_ex.txt create mode 100644 day7/src/main.rs create mode 100644 day7/src/schedule.rs create mode 100644 day7/src/topo_order.rs (limited to 'day7') 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 "] + +[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 = 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 = file.lines() + .map(|line| line.expect("Could not parse line.")) + .collect(); + + let mut V: HashSet = HashSet::new(); + let mut E: HashSet = HashSet::new(); + let mut V_sources: HashSet = HashSet::new(); + let mut V_sinks: HashSet = 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 = s1.chars().collect(); + let ch2: Vec = 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) { + println!("{}", msg); + print!("["); + for v in vertices { + print!("{}, ", &v); + } + print!("]\n"); +} + +fn print_tasks(msg: &str, tasks: &Vec) { + println!("{}", msg); + print!("["); + for t in tasks { + print!("({}, {}), ", &t.vertex, &t.duration); + } + print!("]\n"); +} + +pub fn find(V: &HashSet, E: &HashSet, V_sources: &HashSet, worker_count: u32) -> u32 { + let mut done: Vec = Vec::new(); + let mut ready: Vec = V_sources.iter() + .map(|&vertex| Task {vertex, duration: vertex_to_duration(&vertex) }) + .collect(); + let mut worked_on: Vec = 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 = Vec::new(); + let mut new_worked_on: Vec = 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 = E.iter() + .filter(|&(v1, _v2)| v1 == vertex) + .map(|&(_v1, v2)| v2) + .collect(); + + for dest_v in &destinations { + let sources: Vec = 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, E: &HashSet, V_sources: &HashSet) -> String { + let mut sources_vec: Vec = 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 = Vec::new(); + let mut ready: Vec = 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 = E.iter() + .filter(|&(v1, _v2)| *v1 == v) + .map(|&(_v1, v2)| v2) + .collect(); + + for dest_v in &destinations { + let sources: Vec = 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