Add day04, 2021

3 files changed, 227 insertions, 1 deletions

diff --git a/2021/rust/Cargo.toml b/2021/rust/Cargo.toml
index ac7f9ee..aed5051 100644
--- a/2021/rust/Cargo.toml
+++ b/2021/rust/Cargo.toml
@@ -3,7 +3,7 @@ members = [
     "day01",
     "day02",
     "day03",
-#    "day04",
+    "day04",
 #    "day05",
 #    "day06",
 #    "day07",
diff --git a/2021/rust/day04/Cargo.toml b/2021/rust/day04/Cargo.toml
new file mode 100644
index 0000000..5f11cc4
--- /dev/null
+++ b/2021/rust/day04/Cargo.toml
@@ -0,0 +1,9 @@
+[package]
+name = "day04"
+version = "0.1.0"
+authors = ["cos <cos>"]
+edition = "2018"
+
+[dependencies]
+aoc = { path = "../../../common/rust/aoc" }
+anyhow = "1.0"
diff --git a/2021/rust/day04/src/main.rs b/2021/rust/day04/src/main.rs
new file mode 100644
index 0000000..e0457de
--- /dev/null
+++ b/2021/rust/day04/src/main.rs
@@ -0,0 +1,217 @@
+use {
+    anyhow::{
+        anyhow,
+        Context,
+        Result,
+    },
+    std::{
+        env::args,
+        fmt,
+        fmt::Display,
+        fs::File,
+        io::{
+            BufRead,
+            BufReader,
+        },
+        path::Path,
+    },
+};
+
+#[derive(Clone)]
+struct BingoBoard {
+    size: usize,
+    values: Vec<u8>,
+    called: Vec<bool>,
+    completed: Option<u8>,
+}
+
+impl BingoBoard {
+    fn new<'a, I: IntoIterator<Item = &'a u8> + Copy>(grid: I) -> Self {
+        let size = 5;
+        let values = (&grid).into_iter().copied().collect();
+        let called = vec![false; grid.into_iter().count()];
+        let completed = None;
+        Self {
+            size,
+            values,
+            called,
+            completed,
+        }
+    }
+
+    fn play(&mut self, num: &u8) -> Result<bool> {
+        if self.completed.is_some() {
+            return Ok(false);
+        }
+
+        for y in 0..self.size {
+            for x in 0..self.size {
+                let value = self.values.get(y * self.size + x)
+                    .ok_or(anyhow!("Invalid BingoBoard"))?;
+
+                if value == num {
+                    self.called[y * self.size + x] = true;
+                }
+            }
+        }
+        for y in 0..self.size {
+            let mut count = 0;
+            for x in 0..self.size {
+                if *self.called.get(y * self.size + x).ok_or(anyhow!("Invalid BingoBoard"))? {
+                    count += 1;
+                }
+                if count == self.size {
+                    self.completed = Some(*num);
+                    return Ok(true);
+                }
+            }
+        }
+        for x in 0..self.size {
+            let mut count = 0;
+            for y in 0..self.size {
+                if *self.called.get(y * self.size + x).ok_or(anyhow!("Invalid BingoBoard"))? {
+                    count += 1;
+                }
+                if count == self.size {
+                    self.completed = Some(*num);
+                    return Ok(true);
+                }
+            }
+        }
+        Ok(false)
+    }
+
+    fn sum_unmarked(&self) -> Result<usize> {
+        let mut sum = 0;
+        for y in 0..self.size {
+            for x in 0..self.size {
+                let value = self.values.get(y * self.size + x)
+                    .ok_or(anyhow!("Invalid BingoBoard"))?;
+
+                if ! *self.called.get(y * self.size + x).ok_or(anyhow!("Invalid BingoBoard"))? {
+                    sum += *value as usize;
+                }
+            }
+        }
+        Ok(sum)
+    }
+}
+
+impl Display for BingoBoard {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        let mut s = String::new();
+        for y in 0..self.size {
+            for x in 0..self.size {
+                let value = self.values.get(y * self.size + x).ok_or(std::fmt::Error)?;
+                if *self.called.get(y * self.size + x).ok_or(std::fmt::Error)? {
+                    s += &format!("[{:2}] ", value);
+                } else {
+                    s += &format!(" {:2}  ", value);
+                }
+            }
+            s += "\n";
+        }
+        if let Some(won) = self.completed {
+            s += &format!("Winning number: {}\n", won);
+        }
+        write!(f, "{}", s)
+    }
+}
+
+#[derive(Clone)]
+struct BingoGame {
+    numbers: Vec<u8>,
+    boards: Vec<BingoBoard>,
+}
+
+impl BingoGame {
+    fn new() -> Self {
+        Self {
+            numbers: vec![],
+            boards: vec![],
+        }
+    }
+}
+
+fn read_input<T: AsRef<Path>>(filename: T) -> Result<BingoGame> {
+    let reader = BufReader::new(File::open(filename)?);
+    let mut game = BingoGame::new();
+    let mut boards: Vec<BingoBoard> = vec![];
+
+    let mut lines = reader.lines();
+    let draw_line = lines.next().ok_or(anyhow!("Could not parse draw_line"))?
+        .map_err(|err| anyhow!("{}", err))?;
+    let mut buffer: Vec<u8> = vec![];
+    for line in lines {
+        let l = line?;
+        if l.is_empty() {
+            if ! buffer.is_empty() {
+                let board = BingoBoard::new(&buffer);
+                boards.push(board);
+            }
+            buffer = vec![];
+        } else {
+            buffer.append(&mut l.split_whitespace().map(|v| v.parse()
+                .map_err(|_| anyhow!("Parse error"))).collect::<Result<_>>()?);
+        }
+    }
+    let board = BingoBoard::new(&buffer);
+    boards.push(board);
+
+    game.numbers = draw_line.split(',').map(|v| v.parse().map_err(|err| anyhow!("{}", err)))
+        .collect::<Result<_>>()?;
+    game.boards = boards;
+
+    Ok(game)
+}
+
+fn part1(game: &BingoGame) -> Result<usize> {
+    let mut game_mut = game.clone();
+    for num in &game_mut.numbers {
+        for board in &mut game_mut.boards {
+            if board.play(num)? {
+                // println!("{}", board);
+                return Ok(board.sum_unmarked()? * *num as usize);
+            }
+        }
+    }
+    Err(anyhow!("No winner"))
+}
+
+fn part2(game: &BingoGame) -> Result<usize> {
+    let mut game_mut = game.clone();
+    let mut last_winner = None;
+    for num in &game_mut.numbers {
+        for (index, board) in &mut game_mut.boards.iter_mut().enumerate() {
+            if board.play(num)? {
+                last_winner = Some(index);
+            }
+        }
+    }
+    if let Some(winner) = last_winner {
+        let board = &game_mut.boards[winner];
+        let unmarked_sum = board.sum_unmarked()?;
+        let won = board.completed.ok_or(anyhow!("No winning number"))? as usize;
+        // println!("Winning board: {} ({} * {})", winner + 1, unmarked_sum, won);
+        // println!("{}", board);
+        Ok(unmarked_sum * won)
+    } else {
+        Err(anyhow!("No winner"))
+    }
+}
+
+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(())
+}