Solve day9

5 files changed, 313 insertions, 0 deletions

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 <jan.tuomi@eficode.com>"]
+
+[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<Marble>,
+  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<Marble> = 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<String> = 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<String> = 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<u32> = 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