From 51321223176a80bf4c82a126c03a451665f8b435 Mon Sep 17 00:00:00 2001
From: Greg Burri <greg.burri@gmail.com>
Date: Sun, 8 Dec 2024 15:43:34 +0100
Subject: [PATCH] Day 08

---
 src/day08.rs | 145 +++++++++++++++++++++++++++++++++++++++++++++++++++
 src/days.rs  |  10 ++++
 src/main.rs  |   4 +-
 3 files changed, 157 insertions(+), 2 deletions(-)
 create mode 100644 src/day08.rs

diff --git a/src/day08.rs b/src/day08.rs
new file mode 100644
index 0000000..62f545b
--- /dev/null
+++ b/src/day08.rs
@@ -0,0 +1,145 @@
+use std::{collections::HashMap, io::BufRead};
+
+use itertools::Itertools;
+use nalgebra::DMatrix;
+
+type Antennae = DMatrix<char>;
+type Antinodes = DMatrix<bool>;
+
+const EMPTY: char = ' ';
+
+pub fn read<R>(reader: R) -> Antennae
+where
+    R: BufRead,
+{
+    let mut antennae = Antennae::default();
+
+    for (i, l) in reader.lines().enumerate() {
+        if antennae.nrows() < i + 1 {
+            antennae = antennae.insert_row(i, EMPTY);
+        }
+        for (j, c) in l.unwrap().chars().enumerate() {
+            if antennae.ncols() < j + 1 {
+                antennae = antennae.insert_column(j, EMPTY);
+            }
+            if c != '.' {
+                antennae[(i, j)] = c;
+            }
+        }
+    }
+
+    antennae
+}
+pub enum AntinodeMode {
+    TwoPerPair,
+    Unlimited,
+}
+
+fn antinode_positions(
+    pos: Vec<&(usize, usize)>,
+    mode: &AntinodeMode,
+    limits: (usize, usize),
+) -> Vec<(i32, i32)> {
+    let (p1x, p1y, p2x, p2y) = (
+        pos[0].0 as i32,
+        pos[0].1 as i32,
+        pos[1].0 as i32,
+        pos[1].1 as i32,
+    );
+    let (dx, dy) = (p1x - p2x, p1y - p2y);
+    match mode {
+        AntinodeMode::TwoPerPair => vec![(p1x + dx, p1y + dy), (p2x - dx, p2y - dy)],
+        AntinodeMode::Unlimited => {
+            let mut antinodes = Vec::new();
+            let (mut current1, mut current2) = ((p1x, p1y), (p2x, p2y));
+
+            while current1.0 >= 0
+                && current1.0 < limits.0 as i32
+                && current1.1 >= 0
+                && current1.1 < limits.1 as i32
+            {
+                antinodes.push(current1);
+                current1 = (current1.0 + dx, current1.1 + dy);
+            }
+
+            while current2.0 >= 0
+                && current2.0 < limits.0 as i32
+                && current2.1 >= 0
+                && current2.1 < limits.1 as i32
+            {
+                antinodes.push(current2);
+                current2 = (current2.0 - dx, current2.1 - dy);
+            }
+            antinodes
+        }
+    }
+}
+
+pub fn nb_antinodes(antennae: &Antennae, mode: AntinodeMode) -> i32 {
+    let mut antennae_positions: HashMap<char, Vec<(usize, usize)>> = HashMap::new();
+    let mut antinodes = Antinodes::repeat(antennae.nrows(), antennae.ncols(), false);
+    let mut nb_antinodes = 0;
+    let (nc, nr) = (antennae.ncols(), antennae.nrows());
+    for j in 0..nc {
+        for i in 0..nr {
+            let current = antennae[(i, j)];
+            if current != EMPTY {
+                antennae_positions
+                    .entry(current)
+                    .or_insert(Vec::new())
+                    .push((i, j));
+            }
+        }
+    }
+    for positions in antennae_positions.values() {
+        for (x, y) in positions
+            .iter()
+            .combinations(2)
+            .map(|positions| antinode_positions(positions, &mode, (nr, nc)))
+            .flatten()
+        {
+            if x < 0 || x >= nc as i32 || y < 0 || y >= nr as i32 {
+                continue;
+            }
+
+            if !antinodes[(x as usize, y as usize)] {
+                antinodes[(x as usize, y as usize)] = true;
+                nb_antinodes += 1;
+            }
+        }
+    }
+
+    nb_antinodes
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    static ANTENNAE: &str = "............
+........0...
+.....0......
+.......0....
+....0.......
+......A.....
+............
+............
+........A...
+.........A..
+............
+............";
+
+    #[test]
+    fn test_part1() {
+        let antennae = read(ANTENNAE.as_bytes());
+        let n = nb_antinodes(&antennae, AntinodeMode::TwoPerPair);
+        assert_eq!(n, 14);
+    }
+
+    #[test]
+    fn test_part2() {
+        let antennae = read(ANTENNAE.as_bytes());
+        let n = nb_antinodes(&antennae, AntinodeMode::Unlimited);
+        assert_eq!(n, 34);
+    }
+}
diff --git a/src/days.rs b/src/days.rs
index 3a91a0f..518c47a 100644
--- a/src/days.rs
+++ b/src/days.rs
@@ -71,3 +71,13 @@ pub fn day07() -> String {
         day07::sum_valid_equations_with_concat(&equations),
     )
 }
+
+pub fn day08() -> String {
+    let f = fs::File::open("data/day08.input").unwrap();
+    let antennae = day08::read(BufReader::new(f));
+    format!(
+        "part1: {}, part2: {}",
+        day08::nb_antinodes(&antennae, day08::AntinodeMode::TwoPerPair),
+        day08::nb_antinodes(&antennae, day08::AntinodeMode::Unlimited),
+    )
+}
diff --git a/src/main.rs b/src/main.rs
index 1a15e9e..b6edd9e 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -10,7 +10,7 @@ mod day04;
 mod day05;
 mod day06;
 mod day07;
-// mod day08;
+mod day08;
 // mod day09;
 // mod day10;
 // mod day11;
@@ -51,7 +51,7 @@ fn main() {
         days::day05,
         days::day06,
         days::day07,
-        // days::day08,
+        days::day08,
         // days::day09,
         // days::day10,
         // days::day11,
-- 
2.45.2