Day 24: bugs of life

1 files changed, 136 insertions, 0 deletions

diff --git a/src/bin/day_24.rs b/src/bin/day_24.rs
new file mode 100644
index 0000000..ef10ae8
--- /dev/null
+++ b/src/bin/day_24.rs
@@ -0,0 +1,136 @@
+use rpds::vector::Vector;
+use rpds::RedBlackTreeSet;
+use std::fmt;
+use std::io;
+use std::io::prelude::*;
+use std::iter;
+use std::iter::FromIterator;
+use std::process;
+use structopt::StructOpt;
+
+#[derive(Debug, StructOpt)]
+#[structopt(name = "Day 24: Planet of Discord")]
+/// Simulates the life and death of Eris bugs
+///
+/// See https://adventofcode.com/2019/day/24 for details.
+struct Opt {}
+
+fn main() {
+    let stdin = io::stdin();
+    let opt = Opt::from_args();
+
+    let initial_state: State = stdin
+        .lock()
+        .lines()
+        .map(|x| exit_on_failed_assertion(x, "Error reading input"))
+        .collect();
+
+    println!(
+        "{}",
+        initial_state.first_repeated_state().biodiversity_rating()
+    );
+}
+
+fn exit_on_failed_assertion<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
+    match data {
+        Ok(data) => data,
+        Err(e) => {
+            eprintln!("{}: {}", message, e);
+            process::exit(1);
+        }
+    }
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
+struct State {
+    grid: Vector<Vector<bool>>,
+}
+
+impl FromIterator<String> for State {
+    fn from_iter<T: IntoIterator<Item = String>>(iter: T) -> Self {
+        State {
+            grid: iter
+                .into_iter()
+                .map(|line| line.chars().map(|c| c == '#').collect::<Vector<_>>())
+                .collect(),
+        }
+    }
+}
+
+impl fmt::Display for State {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.grid
+            .iter()
+            .map(|row| {
+                writeln!(
+                    f,
+                    "{}",
+                    row.iter()
+                        .map(|alive| if *alive { '#' } else { '.' })
+                        .collect::<String>()
+                )
+            })
+            .collect()
+    }
+}
+
+impl State {
+    fn first_repeated_state(&self) -> State {
+        iter::successors(
+            Some((RedBlackTreeSet::new(), self.clone())),
+            |(seen, state)| {
+                eprintln!("{}", state);
+                Some((seen.insert(state.clone()), state.next()))
+            },
+        )
+        .find(|(seen, state)| seen.contains(state))
+        .unwrap()
+        .1
+    }
+
+    fn next(&self) -> State {
+        State {
+            grid: self
+                .grid
+                .iter()
+                .enumerate()
+                .map(|(y, row)| {
+                    row.iter()
+                        .enumerate()
+                        .map(|(x, alive)| {
+                            if *alive {
+                                self.count_alive_neighbours(x, y) == 1
+                            } else {
+                                self.count_alive_neighbours(x, y) == 1
+                                    || self.count_alive_neighbours(x, y) == 2
+                            }
+                        })
+                        .collect()
+                })
+                .collect(),
+        }
+    }
+
+    fn biodiversity_rating(&self) -> usize {
+        self.grid
+            .iter()
+            .flat_map(|row| row.iter())
+            .enumerate()
+            .map(|(i, state)| if *state { 2_usize.pow(i as u32) } else { 0 })
+            .sum()
+    }
+
+    fn count_alive_neighbours(&self, x: usize, y: usize) -> usize {
+        [(-1, 0), (1, 0), (0, -1), (0, 1)]
+            .into_iter()
+            .filter_map(|(dx, dy)| {
+                if (x > 0 || *dx >= 0) && (y > 0 || *dy >= 0) {
+                    Some(((x as i32 + dx) as usize, (y as i32 + dy) as usize))
+                } else {
+                    None
+                }
+            })
+            .filter(|(x, y)| self.grid.get(*y).and_then(|row| row.get(*x)).cloned() == Some(true))
+            .count()
+    }
+}