From 4c00416128d4d8ffd4bea638a60faffb491a4cae Mon Sep 17 00:00:00 2001
From: Justin Wernick <j.wernick@eyeo.com>
Date: Tue, 13 Dec 2022 09:28:39 +0200
Subject: Day 12

---
 2022/src/bin/day_12.rs | 174 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 174 insertions(+)
 create mode 100644 2022/src/bin/day_12.rs

(limited to '2022/src')

diff --git a/2022/src/bin/day_12.rs b/2022/src/bin/day_12.rs
new file mode 100644
index 0000000..9190113
--- /dev/null
+++ b/2022/src/bin/day_12.rs
@@ -0,0 +1,174 @@
+use nom::{
+    character::complete::{line_ending, satisfy},
+    combinator::map,
+    multi::{many1, separated_list1},
+    IResult,
+};
+use std::{
+    collections::{BTreeMap, BTreeSet},
+    fs,
+};
+
+fn main() -> Result<(), Box<dyn std::error::Error>> {
+    let input = fs::read_to_string("inputs/day_12.txt")?;
+    let map = HeightMap::parser(&input).unwrap().1;
+
+    let distance_map = MapExploration::explore(&map);
+
+    dbg!(distance_map.distance_to.get(&map.start));
+
+    let min_distance_start = map
+        .heights
+        .iter()
+        .enumerate()
+        .flat_map(|(y, row)| {
+            row.iter()
+                .enumerate()
+                .filter(|(_x, height)| **height == 0)
+                .map(move |(x, _)| Point { x, y })
+        })
+        .filter_map(|p| distance_map.distance_to.get(&p))
+        .min();
+    dbg!(min_distance_start);
+
+    Ok(())
+}
+
+#[derive(Debug, Clone)]
+struct HeightMap {
+    heights: Vec<Vec<u8>>,
+    start: Point,
+    end: Point,
+}
+
+#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)]
+struct Point {
+    x: usize,
+    y: usize,
+}
+
+impl HeightMap {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(
+            separated_list1(line_ending, many1(satisfy(|c| c.is_ascii_alphabetic()))),
+            |height_chars| {
+                let mut start = Point::default();
+                let mut end = Point::default();
+                let mut heights = Vec::new();
+                for y in 0..height_chars.len() {
+                    let mut new_row = Vec::new();
+                    for x in 0..height_chars[y].len() {
+                        let height = match height_chars[y][x] {
+                            'S' => {
+                                start = Point { x, y };
+                                0
+                            }
+                            'E' => {
+                                end = Point { x, y };
+                                25
+                            }
+                            a if a.is_ascii_lowercase() => height_chars[y][x] as u8 - b'a',
+                            a => panic!("Unexpected character {}", a),
+                        };
+                        new_row.push(height);
+                    }
+                    heights.push(new_row);
+                }
+
+                HeightMap {
+                    heights,
+                    start,
+                    end,
+                }
+            },
+        )(input)
+    }
+
+    fn adjacent_to(&self, p: &Point) -> Vec<Point> {
+        let current_height = self
+            .heights
+            .get(p.y)
+            .and_then(|row| row.get(p.x))
+            .cloned()
+            .unwrap_or(0);
+
+        p.adjacent()
+            .into_iter()
+            .filter(|other_p| {
+                let other_height = self
+                    .heights
+                    .get(other_p.y)
+                    .and_then(|row| row.get(other_p.x));
+
+                match other_height {
+                    None => false,
+                    Some(&other_height) => other_height + 1 >= current_height,
+                }
+            })
+            .collect()
+    }
+}
+
+impl Point {
+    fn adjacent(&self) -> Vec<Point> {
+        let mut result = Vec::new();
+        if self.x > 0 {
+            result.push(Point {
+                x: self.x - 1,
+                y: self.y,
+            });
+        }
+        if self.x < usize::MAX {
+            result.push(Point {
+                x: self.x + 1,
+                y: self.y,
+            });
+        }
+        if self.y > 0 {
+            result.push(Point {
+                x: self.x,
+                y: self.y - 1,
+            });
+        }
+        if self.y < usize::MAX {
+            result.push(Point {
+                x: self.x,
+                y: self.y + 1,
+            });
+        }
+        result
+    }
+}
+
+struct MapExploration {
+    distance_to: BTreeMap<Point, u32>,
+}
+
+impl MapExploration {
+    fn explore(map: &HeightMap) -> MapExploration {
+        let mut frontier = BTreeSet::new();
+        let mut distance_to = BTreeMap::new();
+        let mut distance = 0;
+
+        distance_to.insert(map.end.clone(), distance);
+        frontier.insert(map.end.clone());
+
+        while !frontier.is_empty() {
+            let mut next_frontier = BTreeSet::new();
+            distance += 1;
+
+            for frontier_point in frontier {
+                for adjacent_point in map.adjacent_to(&frontier_point) {
+                    if !distance_to.contains_key(&adjacent_point) {
+                        distance_to.insert(adjacent_point.clone(), distance);
+                        next_frontier.insert(adjacent_point);
+                    }
+                }
+            }
+
+            frontier = next_frontier;
+        }
+
+        MapExploration { distance_to }
+    }
+}
-- 
cgit v1.2.3