From 50273ff5b02b11ac59ce7081695d927566ff4374 Mon Sep 17 00:00:00 2001
From: tomsmeding <tom.smeding@gmail.com>
Date: Sun, 9 Dec 2018 11:44:17 +0100
Subject: Day 9

---
 2018/input/9.txt |   1 +
 2018/src/day9.rs | 168 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2018/src/main.rs |   4 +-
 3 files changed, 172 insertions(+), 1 deletion(-)
 create mode 100644 2018/input/9.txt
 create mode 100644 2018/src/day9.rs

diff --git a/2018/input/9.txt b/2018/input/9.txt
new file mode 100644
index 0000000..fa06400
--- /dev/null
+++ b/2018/input/9.txt
@@ -0,0 +1 @@
+432 players; last marble is worth 71019 points
diff --git a/2018/src/day9.rs b/2018/src/day9.rs
new file mode 100644
index 0000000..2432007
--- /dev/null
+++ b/2018/src/day9.rs
@@ -0,0 +1,168 @@
+use std::io;
+use std::io::BufRead;
+use std::fmt;
+
+struct Chain<T: Copy> {
+    left: Vec<T>,
+    right: Vec<T>,
+}
+
+impl<T: Copy> Chain<T> {
+    fn new() -> Self {
+        Chain { left: Vec::new(), right: Vec::new() }
+    }
+
+    fn redistribute(&mut self) {
+        // println!("redistribute: left {}, right {}", self.left.len(), self.right.len());
+
+        let large;
+        let small;
+        if self.left.len() > self.right.len() {
+            large = &mut self.left;
+            small = &mut self.right;
+        } else {
+            large = &mut self.right;
+            small = &mut self.left;
+        }
+
+        if large.len() == 0 {
+            return;
+        }
+        let mut temp = Vec::new();
+        temp.append(small);
+
+        // This seems fast in my tests, for some reason
+        let denominator = 10;
+        let nmoved = (large.len() * (denominator - 1) + denominator - 1) / denominator;
+        for i in 0..nmoved {
+            small.push(large[nmoved - 1 - i]);
+        }
+
+        large.splice(..nmoved, std::iter::empty());
+        small.append(&mut temp);
+
+        // println!("              left {}, right {}", self.left.len(), self.right.len());
+    }
+
+    fn rot_left(&mut self) {
+        if self.left.len() + self.right.len() == 0 {
+            return;
+        }
+        if self.left.len() == 0 {
+            self.redistribute();
+        }
+
+        self.right.push(*self.left.last().unwrap());
+        self.left.pop();
+    }
+
+    fn rot_right(&mut self) {
+        if self.left.len() + self.right.len() == 0 {
+            return;
+        }
+        if self.right.len() == 0 {
+            self.redistribute();
+        }
+
+        self.left.push(*self.right.last().unwrap());
+        self.right.pop();
+    }
+
+    fn current(&self) -> T {
+        if self.left.len() == 0 {
+            *self.right.first().unwrap()
+        } else {
+            *self.left.last().unwrap()
+        }
+    }
+
+    fn rotate(&mut self, amt: i32) {
+        if amt < 0 {
+            for _ in 0..-amt { self.rot_left(); }
+        } else {
+            for _ in 0..amt { self.rot_right(); }
+        }
+    }
+
+    fn insert_after(&mut self, val: T) {
+        self.left.push(val);
+    }
+
+    #[used]
+    fn insert_before(&mut self, val: T) {
+        if self.left.len() == 0 {
+            if self.right.len() == 0 {
+                self.left.push(val);
+                return;
+            }
+            self.redistribute();
+        }
+        self.left.insert(self.left.len() - 1, val);
+    }
+
+    fn remove_current(&mut self) {
+        if self.left.len() == 0 {
+            self.right.remove(0);
+        } else {
+            self.left.pop();
+        }
+    }
+}
+
+impl<T: Copy + fmt::Display> fmt::Display for Chain<T> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        if self.left.len() == 0 {
+            if self.right.len() == 0 { return Ok(()); }
+            write!(f, "({})", self.right[0])?;
+            for i in 0..self.right.len()-1 {
+                write!(f, " {}", self.right[self.right.len() - 1 - i])?;
+            }
+        } else {
+            for val in self.left.iter().take(self.left.len() - 1) {
+                write!(f, "{} ", val)?;
+            }
+            write!(f, "({})", self.left.last().unwrap())?;
+            for i in 0..self.right.len() {
+                write!(f, " {}", self.right[self.right.len() - 1 - i])?;
+            }
+        }
+        Ok(())
+    }
+}
+
+fn simulate(nplayers: i64, lastmarble: i64) -> i64 {
+    let mut scores = vec![0; nplayers as usize];
+
+    let mut chain: Chain<i64> = Chain::new();
+    chain.insert_after(0);
+    // println!("{}", chain);
+
+    for marble in 1..lastmarble+1 {
+        if marble % 23 != 0 {
+            chain.rotate(1);
+            chain.insert_after(marble);
+        } else {
+            scores[(marble % nplayers) as usize] += marble;
+            chain.rotate(-7);
+            scores[(marble % nplayers) as usize] += chain.current();
+            chain.remove_current();
+            chain.rotate(1);
+        }
+
+        // println!("{}", chain);
+    }
+
+    *scores.iter().max().unwrap()
+}
+
+pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
+    let input = reader.lines().next().unwrap().unwrap();
+    let input_split: Vec<&str> = input.split(' ').collect();
+    let nplayers: i64 = input_split[0].parse().unwrap();
+    let lastmarble: i64 = input_split[6].parse().unwrap();
+
+    let part1 = simulate(nplayers, lastmarble).to_string();
+    let part2 = simulate(nplayers, lastmarble * 100).to_string();
+
+    Ok((part1, part2))
+}
diff --git a/2018/src/main.rs b/2018/src/main.rs
index 8d2f368..1e01f55 100644
--- a/2018/src/main.rs
+++ b/2018/src/main.rs
@@ -17,8 +17,9 @@ mod day5;
 mod day6;
 mod day7;
 mod day8;
+mod day9;
 
-static NUM_DAYS: i32 = 8;
+static NUM_DAYS: i32 = 9;
 
 fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> {
     match day {
@@ -30,6 +31,7 @@ fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> {
         6 => day6::main(reader),
         7 => day7::main(reader),
         8 => day8::main(reader),
+        9 => day9::main(reader),
         _ => Err(Error::new(ErrorKind::Other, "Invalid day"))
     }
 }
-- 
cgit v1.2.3-54-g00ecf