From b8e9c88da10835a32c82891c93023eb6eda952ed Mon Sep 17 00:00:00 2001 From: Jan Tuomi Date: Mon, 10 Dec 2018 15:44:07 +0200 Subject: Solve day9 --- day9/Cargo.lock | 154 +++++++++++++++++++++++++++++++++++++++++++++++++++++ day9/Cargo.toml | 8 +++ day9/input_ex1.txt | 1 + day9/input_ex2.txt | 1 + day9/src/main.rs | 149 +++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 313 insertions(+) create mode 100644 day9/Cargo.lock create mode 100644 day9/Cargo.toml create mode 100644 day9/input_ex1.txt create mode 100644 day9/input_ex2.txt create mode 100644 day9/src/main.rs diff --git a/day9/Cargo.lock b/day9/Cargo.lock new file mode 100644 index 0000000..79ca838 --- /dev/null +++ b/day9/Cargo.lock @@ -0,0 +1,154 @@ +[[package]] +name = "day9" +version = "0.1.0" +dependencies = [ + "flame 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)", + "text_io 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "flame" +version = "0.2.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "lazy_static 0.2.11 (registry+https://github.com/rust-lang/crates.io-index)", + "serde 1.0.81 (registry+https://github.com/rust-lang/crates.io-index)", + "serde_derive 1.0.81 (registry+https://github.com/rust-lang/crates.io-index)", + "serde_json 1.0.33 (registry+https://github.com/rust-lang/crates.io-index)", + "thread-id 3.3.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "itoa" +version = "0.4.3" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "lazy_static" +version = "0.2.11" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "libc" +version = "0.2.44" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "proc-macro2" +version = "0.4.24" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "unicode-xid 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "quote" +version = "0.6.10" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "proc-macro2 0.4.24 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "redox_syscall" +version = "0.1.43" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "ryu" +version = "0.2.7" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "serde" +version = "1.0.81" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "serde_derive" +version = "1.0.81" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "proc-macro2 0.4.24 (registry+https://github.com/rust-lang/crates.io-index)", + "quote 0.6.10 (registry+https://github.com/rust-lang/crates.io-index)", + "syn 0.15.22 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "serde_json" +version = "1.0.33" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "itoa 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)", + "ryu 0.2.7 (registry+https://github.com/rust-lang/crates.io-index)", + "serde 1.0.81 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "syn" +version = "0.15.22" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "proc-macro2 0.4.24 (registry+https://github.com/rust-lang/crates.io-index)", + "quote 0.6.10 (registry+https://github.com/rust-lang/crates.io-index)", + "unicode-xid 0.1.0 (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" + +[[package]] +name = "thread-id" +version = "3.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "libc 0.2.44 (registry+https://github.com/rust-lang/crates.io-index)", + "redox_syscall 0.1.43 (registry+https://github.com/rust-lang/crates.io-index)", + "winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "unicode-xid" +version = "0.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "winapi" +version = "0.3.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", + "winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "winapi-i686-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "winapi-x86_64-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[metadata] +"checksum flame 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "1fc2706461e1ee94f55cab2ed2e3d34ae9536cfa830358ef80acff1a3dacab30" +"checksum itoa 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)" = "1306f3464951f30e30d12373d31c79fbd52d236e5e896fd92f96ec7babbbe60b" +"checksum lazy_static 0.2.11 (registry+https://github.com/rust-lang/crates.io-index)" = "76f033c7ad61445c5b347c7382dd1237847eb1bce590fe50365dcb33d546be73" +"checksum libc 0.2.44 (registry+https://github.com/rust-lang/crates.io-index)" = "10923947f84a519a45c8fefb7dd1b3e8c08747993381adee176d7a82b4195311" +"checksum proc-macro2 0.4.24 (registry+https://github.com/rust-lang/crates.io-index)" = "77619697826f31a02ae974457af0b29b723e5619e113e9397b8b82c6bd253f09" +"checksum quote 0.6.10 (registry+https://github.com/rust-lang/crates.io-index)" = "53fa22a1994bd0f9372d7a816207d8a2677ad0325b073f5c5332760f0fb62b5c" +"checksum redox_syscall 0.1.43 (registry+https://github.com/rust-lang/crates.io-index)" = "679da7508e9a6390aeaf7fbd02a800fdc64b73fe2204dd2c8ae66d22d9d5ad5d" +"checksum ryu 0.2.7 (registry+https://github.com/rust-lang/crates.io-index)" = "eb9e9b8cde282a9fe6a42dd4681319bfb63f121b8a8ee9439c6f4107e58a46f7" +"checksum serde 1.0.81 (registry+https://github.com/rust-lang/crates.io-index)" = "c91eb5b0190ae87b4e2e39cbba6e3bed3ac6186935fe265f0426156c4c49961b" +"checksum serde_derive 1.0.81 (registry+https://github.com/rust-lang/crates.io-index)" = "477b13b646f5b5b56fc95bedfc3b550d12141ce84f466f6c44b9a17589923885" +"checksum serde_json 1.0.33 (registry+https://github.com/rust-lang/crates.io-index)" = "c37ccd6be3ed1fdf419ee848f7c758eb31b054d7cd3ae3600e3bae0adf569811" +"checksum syn 0.15.22 (registry+https://github.com/rust-lang/crates.io-index)" = "ae8b29eb5210bc5cf63ed6149cbf9adfc82ac0be023d8735c176ee74a2db4da7" +"checksum text_io 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)" = "9658b61ebd1d2a40c276ba2335890b9eb6550b67458a6fbce2022e58c3350a50" +"checksum thread-id 3.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "c7fbf4c9d56b320106cd64fd024dadfa0be7cb4706725fc44a7d7ce952d820c1" +"checksum unicode-xid 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "fc72304796d0818e357ead4e000d19c9c174ab23dc11093ac919054d20a6a7fc" +"checksum winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)" = "92c1eb33641e276cfa214a0522acad57be5c56b10cb348b3c5117db75f3ac4b0" +"checksum winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6" +"checksum winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f" diff --git a/day9/Cargo.toml b/day9/Cargo.toml new file mode 100644 index 0000000..0254f94 --- /dev/null +++ b/day9/Cargo.toml @@ -0,0 +1,8 @@ +[package] +name = "day9" +version = "0.1.0" +authors = ["Jan Tuomi "] + +[dependencies] +text_io = "0.1.7" +flame = "0.2.2" diff --git a/day9/input_ex1.txt b/day9/input_ex1.txt new file mode 100644 index 0000000..9c074c1 --- /dev/null +++ b/day9/input_ex1.txt @@ -0,0 +1 @@ +10 players; last marble is worth 1618 points diff --git a/day9/input_ex2.txt b/day9/input_ex2.txt new file mode 100644 index 0000000..2ee4c70 --- /dev/null +++ b/day9/input_ex2.txt @@ -0,0 +1 @@ +9 players; last marble is worth 25 points diff --git a/day9/src/main.rs b/day9/src/main.rs new file mode 100644 index 0000000..49d89ad --- /dev/null +++ b/day9/src/main.rs @@ -0,0 +1,149 @@ +use std::env; +use std::io::BufReader; +use std::io::BufRead; +use std::fs::File; +use std::process; + +// extern crate flame; +#[macro_use] extern crate text_io; + +type Marble = u32; + +struct Circle { + marbles: Vec, + current_i: i32, + n: i32 +} + +impl Circle { + fn get(&self, pos: i32) -> (i32, Marble) { + // let _guard = flame::start_guard("get"); + let n = self.marbles.len() as i32; + let i = (pos % n + n) % n; + (i, self.marbles[i as usize]) + } + + fn set_current(&mut self, pos: i32) { + // let _guard = flame::start_guard("set_current"); + let i = (pos % self.n + self.n) % self.n; + self.current_i = i; + } + + fn get_current(&self) -> (i32, Marble) { + // let _guard = flame::start_guard("get_current"); + let cur = self.marbles[self.current_i as usize]; + + (self.current_i, cur) + } + + fn go_around(&self, delta: i32) -> (i32, Marble) { + // let _guard = flame::start_guard("go_around"); + self.get(self.current_i as i32 + delta) + } + + fn clockwise(&mut self, delta: i32) -> (i32, Marble) { + // let _guard = flame::start_guard("clockwise"); + self.go_around(delta) + } + + fn counterclockwise(&mut self, delta: i32) -> (i32, Marble) { + // let _guard = flame::start_guard("counterclockwise"); + self.go_around(-delta) + } + + fn insert(&mut self, pos: i32, marble: Marble) { + // let _guard = flame::start_guard("insert"); + let i = (pos % self.n + self.n) % self.n + 1; + self.marbles.insert(i as usize, marble); + self.n += 1; + } + + fn remove(&mut self, pos: i32) { + // let _guard = flame::start_guard("remove"); + let (i, m) = self.get(pos); + let (_cur_i, cur) = self.get_current(); + if m == cur { + panic!("Removed current marble!"); + } + + self.marbles.remove(i as usize); + self.n -= 1; + } +} + +fn build_circle() -> Circle { + // let _guard = flame::start_guard("build_circle"); + let init_marbles: Vec = vec![0; 1]; + let circle = Circle { marbles: init_marbles, current_i: 0, n: 1 }; + circle +} + +fn print_state(circle: &Circle, turn: usize) { + print!("[{}] ", turn); + for marble in &circle.marbles { + let (_cur_i, cur) = circle.get_current(); + if &cur == marble { + print!(" ({}) ", marble); + } else { + print!(" {} ", marble); + } + } + print!("\n") +} + +fn main() { + let args: Vec = env::args().collect(); + if args.len() != 2 { + println!("Wrong number of arguments. Provide a file name and worker count."); + process::exit(1); + } + let filename = &args[1]; + + 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(); + + assert_eq!(lines.len(), 1); + + let line = &lines[0]; + let (player_count, marble_count): (usize, usize); + scan!(line.bytes() => "{} players; last marble is worth {} points", player_count, marble_count); + + let mut scores: Vec = vec![0; player_count]; + let mut circle = build_circle(); + let mut turn: usize = 0; + for marble in 1..(marble_count + 1) as Marble { + if marble % 23 == 0 { + scores[turn] += marble; + let (rem_i, rem_m): (i32, Marble) = circle.counterclockwise(7); + circle.remove(rem_i); + scores[turn] += rem_m; + let (new_cur_i, _new_cur) = circle.get(rem_i as i32); + circle.set_current(new_cur_i); + } else { + let (clockwise_i, _clockwise_m) = circle.clockwise(1); + circle.insert(clockwise_i, marble); + circle.set_current(clockwise_i + 1); + } + + // print_state(&circle, turn + 1); + if marble % 1000 == 0 { + let progress = 100.0 * (marble as f32) / marble_count as f32; + println!("Debug: Progress: {} %, Processed {} / {}", progress, marble, marble_count); + } + turn = (turn + 1) % player_count; + } + + let max_score: &u32 = scores.iter().max().expect("No scores in vector"); + println!("Max score: {}", max_score); + // flame::dump_html(&mut File::create("flame-graph.html").unwrap()).unwrap(); +} \ No newline at end of file -- cgit v1.3