summaryrefslogtreecommitdiff
path: root/2018/src
diff options
context:
space:
mode:
authortomsmeding <tom.smeding@gmail.com>2018-12-09 11:44:17 +0100
committertomsmeding <tom.smeding@gmail.com>2018-12-09 11:44:17 +0100
commit50273ff5b02b11ac59ce7081695d927566ff4374 (patch)
treea0ed76b5e355527088a41df05d1474b9bbfbe976 /2018/src
parentd622aca0fed3043a74b1b9e42be83d88837b372c (diff)
Day 9
Diffstat (limited to '2018/src')
-rw-r--r--2018/src/day9.rs168
-rw-r--r--2018/src/main.rs4
2 files changed, 171 insertions, 1 deletions
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"))
}
}