From dee83f33c4281c7a01d390017d756d86715b1cb5 Mon Sep 17 00:00:00 2001
From: Greg Burri <greg.burri@gmail.com>
Date: Wed, 4 Dec 2024 11:27:53 +0100
Subject: [PATCH] Day 04

---
 src/day04.rs | 132 +++++++++++++++++++++++++++++++++++++++++++++++++++
 src/days.rs  |  10 ++++
 src/main.rs  |   4 +-
 3 files changed, 144 insertions(+), 2 deletions(-)
 create mode 100644 src/day04.rs

diff --git a/src/day04.rs b/src/day04.rs
new file mode 100644
index 0000000..a20b03e
--- /dev/null
+++ b/src/day04.rs
@@ -0,0 +1,132 @@
+use std::io::BufRead;
+
+type WordSearch = Vec<Vec<char>>;
+
+pub fn read_word_search<R>(reader: R) -> WordSearch
+where
+    R: BufRead,
+{
+    let mut word_search: WordSearch = Vec::new();
+    for l in reader.lines() {
+        word_search.push(l.unwrap().chars().collect());
+    }
+    word_search
+}
+
+const DIRECTIONS: [(i32, i32); 8] = [
+    (0, 1),
+    (1, 0),
+    (0, -1),
+    (-1, 0),
+    (1, 1),
+    (-1, 1),
+    (1, -1),
+    (-1, -1),
+];
+
+pub fn nb_of_word_occurences(word_search: &WordSearch, word: &str) -> i32 {
+    let mut n = 0;
+    for i in 0..word_search.len() {
+        for j in 0..word_search[i].len() {
+            'next_direction: for (di, dj) in DIRECTIONS {
+                for (k, c) in word.chars().enumerate() {
+                    let (pos_i, pos_j) = (i as i32 + k as i32 * di, j as i32 + k as i32 * dj);
+                    if pos_i < 0
+                        || pos_i >= word_search.len() as i32
+                        || pos_j < 0
+                        || pos_j >= word_search[i].len() as i32
+                        || word_search[pos_i as usize][pos_j as usize] != c
+                    {
+                        continue 'next_direction;
+                    }
+                }
+                n += 1;
+            }
+        }
+    }
+    n
+}
+
+const XMAS_CROSS_1: [(i32, i32, char); 5] = [
+    (0, 0, 'A'),
+    (1, 1, 'S'),
+    (-1, 1, 'S'),
+    (-1, -1, 'M'),
+    (1, -1, 'M'),
+];
+
+const XMAS_CROSS_2: [(i32, i32, char); 5] = [
+    (0, 0, 'A'),
+    (1, 1, 'M'),
+    (-1, 1, 'S'),
+    (-1, -1, 'S'),
+    (1, -1, 'M'),
+];
+
+const XMAS_CROSS_3: [(i32, i32, char); 5] = [
+    (0, 0, 'A'),
+    (1, 1, 'M'),
+    (-1, 1, 'M'),
+    (-1, -1, 'S'),
+    (1, -1, 'S'),
+];
+
+const XMAS_CROSS_4: [(i32, i32, char); 5] = [
+    (0, 0, 'A'),
+    (1, 1, 'S'),
+    (-1, 1, 'M'),
+    (-1, -1, 'M'),
+    (1, -1, 'S'),
+];
+
+const XMAS_CROSSES: [[(i32, i32, char); 5]; 4] =
+    [XMAS_CROSS_1, XMAS_CROSS_2, XMAS_CROSS_3, XMAS_CROSS_4];
+
+pub fn nb_of_mas_cross(word_search: &WordSearch) -> i32 {
+    let mut n = 0;
+    for i in 1..word_search.len() - 1 {
+        for j in 1..word_search[i].len() - 1 {
+            'next_cross: for cross in XMAS_CROSSES {
+                for (di, dj, c) in cross {
+                    let (pos_i, pos_j) = (i as i32 + di, j as i32 + dj);
+                    if word_search[pos_i as usize][pos_j as usize] != c {
+                        continue 'next_cross;
+                    }
+                }
+                n += 1;
+                break;
+            }
+        }
+    }
+    n
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    static WORD_SEARCH: &str = "MMMSXXMASM
+MSAMXMSMSA
+AMXSXMAAMM
+MSAMASMSMX
+XMASAMXAMM
+XXAMMXXAMA
+SMSMSASXSS
+SAXAMASAAA
+MAMMMXMMMM
+MXMXAXMASX";
+
+    #[test]
+    fn test_part1() {
+        let word_search = read_word_search(WORD_SEARCH.as_bytes());
+        let n = nb_of_word_occurences(&word_search, "XMAS");
+        assert_eq!(n, 18);
+    }
+
+    #[test]
+    fn test_part2() {
+        let word_search = read_word_search(WORD_SEARCH.as_bytes());
+        let n = nb_of_mas_cross(&word_search);
+        assert_eq!(n, 9);
+    }
+}
diff --git a/src/days.rs b/src/days.rs
index 1424849..5450666 100644
--- a/src/days.rs
+++ b/src/days.rs
@@ -31,3 +31,13 @@ pub fn day03() -> String {
         day03::execute_corrupted_program_dodont(&program)
     )
 }
+
+pub fn day04() -> String {
+    let f = fs::File::open("data/day04.input").unwrap();
+    let word_search = day04::read_word_search(BufReader::new(f));
+    format!(
+        "part1: {}, part2: {}",
+        day04::nb_of_word_occurences(&word_search, "XMAS"),
+        day04::nb_of_mas_cross(&word_search)
+    )
+}
diff --git a/src/main.rs b/src/main.rs
index 51cf7ce..f51a684 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -6,7 +6,7 @@ use rayon::prelude::*;
 mod day01;
 mod day02;
 mod day03;
-// mod day04;
+mod day04;
 // mod day05;
 // mod day06;
 // mod day07;
@@ -46,7 +46,7 @@ fn main() {
         days::day01,
         days::day02,
         days::day03,
-        // days::day04,
+        days::day04,
         // days::day05,
         // days::day06,
         // days::day07,
-- 
2.45.2