🎄Day 18

tguichaoua · Dec 18, 2024 · 2a825ee · 2a825ee
1 parent 7bdd6b3
commit 2a825ee
Show file tree

Hide file tree

Showing 4 changed files with 190 additions and 2 deletions.
diff --git a/README.md b/README.md
@@ -50,6 +50,7 @@ Solutions for [Advent of Code](https://adventofcode.com/) in [Rust](https://www.
 | [Day 15](./src/bin/15.rs) | `921.2µs` | `1.6ms` |
 | [Day 16](./src/bin/16.rs) | `8.5ms` | `7.3s` |
 | [Day 17](./src/bin/17.rs) | `551.0ns` | `-` |
+| [Day 18](./src/bin/18.rs) | `522.4µs` | `244.7ms` |
 
-**Total: 8869.62ms**
+**Total: 9114.84ms**
 <!--- benchmarking table --->
diff --git a/data/examples/18.txt b/data/examples/18.txt
@@ -0,0 +1,25 @@
+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
diff --git a/src/bin/18.rs b/src/bin/18.rs
@@ -0,0 +1,124 @@
+use std::collections::{HashSet, VecDeque};
+
+use advent_of_code::four_direction_bounded;
+use glam::{uvec2, UVec2};
+
+advent_of_code::solution!();
+
+fn parse(input: &str) -> impl Iterator<Item = UVec2> + '_ {
+    input.lines().map(|line| {
+        let (x, y) = line.split_once(',').unwrap();
+        let x = x.parse().unwrap();
+        let y = y.parse().unwrap();
+        uvec2(x, y)
+    })
+}
+
+pub fn part_one(input: &str) -> Option<u32> {
+    Some(solve_one(input, uvec2(71, 71), 1024))
+}
+
+fn solve_one(input: &str, bounds: UVec2, fallen_bytes: usize) -> u32 {
+    struct Explorer {
+        pos: UVec2,
+        distance: u32,
+    }
+
+    let mut visited = HashSet::new();
+    let mut to_explore = VecDeque::new();
+
+    to_explore.push_back(Explorer {
+        pos: uvec2(0, 0),
+        distance: 0,
+    });
+    visited.insert(uvec2(0, 0));
+
+    let goal = bounds - uvec2(1, 1);
+    let walls: HashSet<_> = parse(input).take(fallen_bytes).collect();
+
+    while let Some(explorer) = to_explore.pop_front() {
+        for pos in four_direction_bounded(explorer.pos, bounds) {
+            if pos == goal {
+                return explorer.distance + 1;
+            }
+
+            if !walls.contains(&pos) && visited.insert(pos) {
+                to_explore.push_back(Explorer {
+                    pos,
+                    distance: explorer.distance + 1,
+                });
+            }
+        }
+    }
+
+    unreachable!()
+}
+
+/* -------------------------------------------------------------------------- */
+
+fn solve_two(input: &str, bounds: UVec2) -> String {
+    let falling_bytes = parse(input);
+
+    let mut walls = HashSet::new();
+
+    let mut visited = HashSet::new();
+    let mut to_explore = Vec::new();
+
+    let goal = bounds - uvec2(1, 1);
+
+    'falling_bytes: for byte in falling_bytes {
+        walls.insert(byte);
+
+        visited.clear();
+        to_explore.clear();
+
+        to_explore.push(uvec2(0, 0));
+        visited.insert(uvec2(0, 0));
+
+        while let Some(pos) = to_explore.pop() {
+            for pos in four_direction_bounded(pos, bounds) {
+                if pos == goal {
+                    continue 'falling_bytes;
+                }
+
+                if !walls.contains(&pos) && visited.insert(pos) {
+                    to_explore.push(pos);
+                }
+            }
+        }
+
+        return format!("{},{}", byte.x, byte.y);
+    }
+
+    unreachable!();
+}
+
+pub fn part_two(input: &str) -> Option<String> {
+    Some(solve_two(input, uvec2(71, 71)))
+}
+
+/* -------------------------------------------------------------------------- */
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_part_one() {
+        let result = solve_one(
+            &advent_of_code::template::read_file("examples", DAY),
+            uvec2(7, 7),
+            12,
+        );
+        assert_eq!(result, 22);
+    }
+
+    #[test]
+    fn test_part_two() {
+        let result = solve_two(
+            &advent_of_code::template::read_file("examples", DAY),
+            uvec2(7, 7),
+        );
+        assert_eq!(result, "6,1");
+    }
+}
diff --git a/src/lib.rs b/src/lib.rs
@@ -9,8 +9,8 @@ pub mod array2d;
 use std::cmp::Ordering;
 
 use array2d::Array2D;
-use glam::UVec2;
 pub use glam::{ivec2 as pos, IVec2 as Pos};
+use glam::{uvec2, UVec2};
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 pub struct MapSize(glam::IVec2);
@@ -268,3 +268,41 @@ pub fn cmp_uvec2(a: &UVec2, b: &UVec2) -> Ordering {
 }
 
 /* -------------------------------------------------------------------------- */
+
+#[inline]
+pub fn four_direction_bounded(
+    pos: glam::UVec2,
+    bounds: glam::UVec2,
+) -> impl Iterator<Item = glam::UVec2> {
+    let mut directions = [None; 4];
+
+    // left
+    if let Some(x) = pos.x.checked_sub(1) {
+        directions[0] = Some(uvec2(x, pos.y));
+    }
+
+    // top
+    if let Some(y) = pos.y.checked_sub(1) {
+        directions[1] = Some(uvec2(pos.x, y));
+    }
+
+    // right
+    {
+        let x = pos.x + 1;
+        if x < bounds.x {
+            directions[2] = Some(uvec2(x, pos.y));
+        }
+    }
+
+    // down
+    {
+        let y = pos.y + 1;
+        if y < bounds.y {
+            directions[3] = Some(uvec2(pos.x, y));
+        }
+    }
+
+    directions.into_iter().flatten()
+}
+
+/* -------------------------------------------------------------------------- */
-Original file line number
+Diff line change
@@ -0,0 +1,25 @@
+,4
+,2
+,5
+,0
+,1
+,3
+,4
+,5
+,6
+,3
+,6
+,1
+,2
+,5
+,5
+,5
+,4
+,4
+,4
+,1
+,1
+,0
+,5
+,6
+,0