Add day11, 2021

3 files changed, 322 insertions, 1 deletions

diff --git a/2021/rust/Cargo.toml b/2021/rust/Cargo.toml
index 6015d2b..9d8c085 100644
--- a/2021/rust/Cargo.toml
+++ b/2021/rust/Cargo.toml
@@ -10,7 +10,7 @@ members = [
     "day08",
     "day09",
     "day10",
-#    "day11",
+    "day11",
 #    "day12",
 #    "day13",
 #    "day14",
diff --git a/2021/rust/day11/Cargo.toml b/2021/rust/day11/Cargo.toml
new file mode 100644
index 0000000..fdd0c53
--- /dev/null
+++ b/2021/rust/day11/Cargo.toml
@@ -0,0 +1,11 @@
+[package]
+name = "day11"
+version = "0.1.0"
+authors = ["cos <cos>"]
+edition = "2021"
+
+[dependencies]
+aoc = { path = "../../../common/rust/aoc" }
+anyhow = "1.0"
+termion = "1.5"
+num = "0.4"
diff --git a/2021/rust/day11/src/main.rs b/2021/rust/day11/src/main.rs
new file mode 100644
index 0000000..79972e3
--- /dev/null
+++ b/2021/rust/day11/src/main.rs
@@ -0,0 +1,310 @@
+use {
+    anyhow::{
+        anyhow,
+        Context,
+        Result,
+    },
+    num::cast::AsPrimitive,
+    std::{
+        env::args,
+        fmt::{
+            Display,
+            Formatter,
+            Result as FmtResult,
+            Write,
+        },
+        fs::File,
+        io::{
+            BufRead,
+            BufReader,
+        },
+        path::Path,
+    },
+    termion::style,
+};
+
+#[derive(Clone,Copy,Debug)]
+enum Direction {
+    North,
+    NorthEast,
+    East,
+    SouthEast,
+    South,
+    SouthWest,
+    West,
+    NorthWest,
+}
+
+impl Direction {
+    // FIXME Returning an unordered collection sush as e.g. HashSet<Direction> could possibly be
+    //       cleaner, but meh!
+    fn all() -> Vec<Direction> {
+        [
+            Direction::North,
+            Direction::NorthEast,
+            Direction::East,
+            Direction::SouthEast,
+            Direction::South,
+            Direction::SouthWest,
+            Direction::West,
+            Direction::NorthWest,
+        ].into_iter().collect()
+    }
+}
+
+#[derive(Clone,Copy,Debug)]
+struct Point {
+    x: usize,
+    y: usize,
+}
+
+impl Point {
+    fn neighbour(&self, dir: Direction) -> Point {
+        match dir {
+            Direction::North => Point {
+                x: self.x,
+                y: self.y.overflowing_sub(1).0
+            },
+            Direction::NorthEast => Point {
+                x: self.x + 1,
+                y: self.y.overflowing_sub(1).0
+            },
+            Direction::East => Point {
+                x: self.x + 1,
+                y: self.y
+            },
+            Direction::SouthEast => Point {
+                x: self.x + 1,
+                y: self.y + 1
+            },
+            Direction::South => Point {
+                x: self.x,
+                y: self.y + 1
+            },
+            Direction::SouthWest => Point {
+                x: self.x.overflowing_sub(1).0,
+                y: self.y + 1
+            },
+            Direction::West => Point {
+                x: self.x.overflowing_sub(1).0,
+                y: self.y
+            },
+            Direction::NorthWest => Point {
+                x: self.x.overflowing_sub(1).0,
+                y: self.y.overflowing_sub(1).0
+            },
+        }
+    }
+}
+
+#[derive(Copy,Clone,Debug)]
+struct Dumbo {
+    energy: u8,
+    flashed: bool,
+}
+
+impl Dumbo {
+    fn new(e: impl AsPrimitive<u8>) -> Result<Self> {
+        let energy = e.as_();
+        let flashed = false;
+        Ok(Self {
+            energy,
+            flashed,
+        })
+    }
+
+    fn step(&mut self) {
+        self.energy += 1;
+    }
+
+    fn flash(&mut self) -> bool {
+        if self.energy > 9 && !self.flashed {
+            self.flashed = true;
+            true
+        } else {
+            false
+        }
+    }
+
+    fn _reset(&mut self) {
+        if self.flashed {
+            self.energy = 0;
+            self.flashed = false;
+        }
+    }
+
+    fn reset_energy(&mut self) {
+        if self.flashed {
+            self.energy = 0;
+        }
+    }
+
+    fn reset_flashed(&mut self) {
+        self.flashed = false;
+    }
+}
+
+impl Display for Dumbo {
+    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
+        if self.flashed {
+            write!(f, "{}", style::Bold)?;
+        }
+        write!(f, "{}", self.energy)?;
+        write!(f, "{}", style::Reset)
+    }
+}
+
+#[derive(Clone)]
+struct CaveMap {
+    size: Point,
+    dumbos: Vec<Dumbo>,
+}
+
+impl CaveMap {
+    fn dumbo_mut(&mut self, pos: &Point) -> Option<&mut Dumbo> {
+        if pos.x < self.size.x && pos.y < self.size.y {
+            self.dumbos.get_mut(pos.y * self.size.y + pos.x)
+        } else {
+            None
+        }
+    }
+
+    fn step(&mut self) -> usize {
+        let mut flash_count = 0;
+        let mut done = false;
+
+        for y in 0..self.size.y {
+            for x in 0..self.size.x {
+                if let Some(dumbo) = self.dumbos.get_mut(y * self.size.y + x) {
+                    dumbo.step();
+                }
+            }
+        }
+
+        while !done {
+            done = true;
+            for y in 0..self.size.y {
+                for x in 0..self.size.x {
+                    if let Some(dumbo) = self.dumbo_mut(&Point {x, y}) {
+                        if dumbo.flash() {
+                            done = false;
+                            flash_count += 1;
+                            for dir in Direction::all() {
+                                let pos = Point {x, y};
+                                let neighbour = pos.neighbour(dir);
+                                if let Some(recipient) = self.dumbo_mut(&neighbour) {
+                                    recipient.step();
+                                }
+                            }
+                        }
+                    }
+                }
+            }
+        }
+
+        for y in 0..self.size.y {
+            for x in 0..self.size.x {
+                if let Some(dumbo) = self.dumbo_mut(&Point {x, y}) {
+                    dumbo.reset_energy();
+                }
+            }
+        }
+        flash_count
+    }
+
+    fn reset(&mut self) {
+        for y in 0..self.size.y {
+            for x in 0..self.size.x {
+                if let Some(dumbo) = self.dumbo_mut(&Point {x, y}) {
+                    dumbo.reset_flashed();
+                }
+            }
+        }
+    }
+}
+
+impl Display for CaveMap {
+    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
+        let mut s = String::new();
+
+        for y in 0..self.size.y {
+            for x in 0..self.size.x {
+                if let Some(d) = self.dumbos.get(y * self.size.y + x) {
+                    write!(&mut s, "{}", d)?;
+                }
+            }
+            writeln!(&mut s)?;
+        }
+        write!(f, "{}", s)
+    }
+}
+
+fn read_input<T: AsRef<Path>>(filename: T) -> Result<CaveMap> {
+    let reader = BufReader::new(File::open(filename)?);
+    let mut x_opt = None;
+    let mut y = 0;
+
+    let dumbos = reader.lines().map( |v| {
+        let s = v?;
+        let dumbo_row: Vec<Dumbo> = s.chars().map(|c| Dumbo::new(c.to_digit(10)
+            .ok_or_else(|| anyhow!("Invalid digit: {}", c))?)).collect::<Result<Vec<_>>>()?;
+        match (x_opt, dumbo_row.len()) {
+            (None, len) => x_opt = Some(len),
+            (Some(this), other) => if this != other {
+                return Err(anyhow!("Inconsistent map width encountered: {} != {}", this, other));
+            },
+        }
+        y += 1;
+        Ok(dumbo_row)
+    }).collect::<Result<Vec<Vec<_>>>>()?.into_iter().flatten().collect();
+
+    let x = x_opt.ok_or(anyhow!("Could not determine size of cave map."))?;
+    let size = Point {
+        x,
+        y,
+    };
+    Ok(CaveMap {
+        size,
+        dumbos,
+    })
+}
+
+fn part1(input: &CaveMap) -> Result<usize> {
+    let mut cave = (*input).clone();
+    let mut flash_count = 0;
+    // println!("Before any steps\n{}", cave);
+    for _step in 1..=100 {
+        flash_count += cave.step();
+        // println!("After step: {}\n{}", _step, cave);
+        cave.reset();
+    }
+    Ok(flash_count)
+}
+
+fn part2(input: &CaveMap) -> Result<usize> {
+    let mut cave = (*input).clone();
+    let mut step = 1;
+    while cave.step() != cave.size.x * cave.size.y {
+        // println!("After step: {}\n{}", step, cave);
+        step += 1;
+        cave.reset();
+    }
+    // println!("After step: {}\n{}", step, cave);
+    Ok(step)
+}
+
+fn main() -> Result<()> {
+    let ( do_part_1, do_part_2 ) = aoc::do_parts();
+
+    let filename = args().nth(1).ok_or(anyhow!("Missing input filename"))?;
+    let input = read_input(filename).context("Could not read input")?;
+    if do_part_1 {
+        let solution = part1(&input).context("No solution for part 1")?;
+        println!("Part1, solution found to be: {}", solution);
+    }
+    if do_part_2 {
+        let solution = part2(&input).context("No solution for part 2")?;
+        println!("Part2, solution found to be: {}", solution);
+    }
+    Ok(())
+}