From 93db8480e87b2dd9bbdd9c2980a6dc325ec7803c Mon Sep 17 00:00:00 2001
From: alex <>
Date: Wed, 18 Dec 2024 09:44:38 +0100
Subject: [PATCH] Day18 - part 1

---
 src/day18.rs | 154 +++++++++++++++++++++++++++++++++++++++++++++++++++
 src/main.rs  |   2 +
 2 files changed, 156 insertions(+)
 create mode 100644 src/day18.rs

diff --git a/src/day18.rs b/src/day18.rs
new file mode 100644
index 0000000..ebb8cab
--- /dev/null
+++ b/src/day18.rs
@@ -0,0 +1,154 @@
+use std::error::Error;
+use std::path::Path;
+use std::collections::{HashMap, HashSet};
+
+const HEIGHT: isize = 70;
+const WIDTH: isize = 70;
+
+struct Puzzle {
+    mem: HashSet<(isize, isize)>,
+    corrupted: HashMap<(isize, isize), usize>,
+    height: isize,
+    width: isize,
+    start: (isize, isize),
+    end: (isize, isize),
+}
+
+impl Puzzle {
+    pub fn new(input: &str, height: isize, width: isize) -> Self {
+        let mem: HashSet<(isize, isize)> = HashSet::new();
+        let corrupted: HashMap<(isize, isize), usize> = input.lines()
+            .enumerate()
+            .map(|(i, l)| {
+                let (x, y) = l.split_once(",").unwrap();
+                let (x, y) = (y.parse::<isize>().unwrap(), x.parse::<isize>().unwrap());
+                ((y, x), i)
+            })
+            .collect();
+        let start = (0, 0);
+        let end = (height, width);
+        Self { mem, corrupted, height, width, start, end }
+    }
+
+    fn build_mem(&mut self, corrupted_size: usize) {
+        self.mem = HashSet::new();
+        (0..=self.height).for_each(|row| {
+            (0..=self.width).for_each(|col| {
+                if !self.corrupted.contains_key(&(row, col)) ||
+                    *self.corrupted.get(&(row,col)).unwrap() >= corrupted_size {
+                    self.mem.insert((row, col));
+                }
+            });
+        });
+    }
+
+    fn steps(&self) -> u32 {
+        let mut next: Vec<(isize, isize)> = Vec::new();
+        next.push(self.start);
+        let mut visited: HashMap<(isize, isize), u32> = HashMap::new();
+        visited.insert(self.start, 0);
+        while let Some(pos) = next.pop() {
+            if pos == self.end {
+                break;
+            }
+            let dst_curr = visited.get(&pos).unwrap().clone();
+            [(-1, 0), (0, 1), (1, 0), (0, -1)].into_iter()
+                .map(|dir| (pos.0 + dir.0, pos.1 + dir.1))
+                .filter(|pos_next| self.mem.contains(&pos_next))
+                .for_each(|pos_next| {
+                    let dst_next = dst_curr + 1;
+                    if let Some(dst) = visited.get_mut(&pos_next) {
+                        if dst_next < *dst {
+                            *dst = dst_next;
+                            next.push(pos_next);
+                        }
+                    }
+                    else {
+                        visited.insert(pos_next, dst_next);
+                        next.push(pos_next);
+                    }
+                });
+            next.sort_by(|a,b| {
+                let na = visited.get(a).unwrap();
+                let nb = visited.get(b).unwrap();
+                nb.cmp(&na)
+            });
+        }
+        *visited.get(&self.end).unwrap()
+    }
+}
+
+fn run_part1(input: &str) -> Result<u32, Box<dyn Error>> {
+    println!("Running {} - part 1", get_day());
+
+    let corrupted_size = 1024;
+    let mut puzzle = Puzzle::new(input, HEIGHT, WIDTH);
+    puzzle.build_mem(corrupted_size);
+    Ok(puzzle.steps())
+}
+
+fn run_part2(input: &str) -> Result<u32, Box<dyn Error>> {
+    println!("Running {} - part 2", get_day());
+
+    Ok(0)
+}
+
+pub fn run(input: &str) -> Result<(), Box<dyn Error>> {
+    let res = run_part1(input)?;
+    println!("{res}");
+
+    let res = run_part2(input)?;
+    println!("{res}");
+
+    Ok(())
+}
+
+fn get_day() -> String {
+    let filename = file!();
+    Path::new(filename).file_stem().unwrap().to_str().unwrap().to_string()
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    static TEXT_INPUT: &str = "\
+5,4
+4,2
+4,5
+3,0
+2,1
+6,3
+2,4
+1,5
+0,6
+3,3
+2,6
+5,1
+1,2
+5,5
+2,5
+6,5
+1,4
+0,4
+6,4
+1,1
+6,1
+1,0
+0,5
+1,6
+2,0";
+
+    #[test]
+    fn test_part1() {
+        let mut puzzle = Puzzle::new(TEXT_INPUT, 6, 6);
+        let corrupted_size = 12;
+        puzzle.build_mem(corrupted_size);
+        assert_eq!(22, puzzle.steps());
+    }
+
+    #[test]
+    fn test_part2() {
+        assert_eq!(0, run_part2(TEXT_INPUT).unwrap());
+    }
+}
diff --git a/src/main.rs b/src/main.rs
index f34e9c0..6e295f8 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -21,6 +21,7 @@ pub mod day14;
 pub mod day15;
 pub mod day16;
 pub mod day17;
+pub mod day18;
 
 fn main() {
     let args: Vec<String> = env::args().collect();
@@ -60,6 +61,7 @@ fn run(day: &str, input_file: &str) -> Result<(), Box<dyn Error>> {
         "day15" => day15::run(&input)?,
         "day16" => day16::run(&input)?,
         "day17" => day17::run(&input)?,
+        "day18" => day18::run(&input)?,
         _ => return Err(format!("unknown or unimplemented day \"{day}\"").into()),
     }
     Ok(())
-- 
2.39.5