refactor: move to single year per repoHEADmain

1 files changed, 167 insertions, 0 deletions

diff --git a/src/day_12.rs b/src/day_12.rs
new file mode 100644
index 0000000..cf0dd98
--- /dev/null
+++ b/src/day_12.rs
@@ -0,0 +1,167 @@
+use anyhow::{Context, Result};
+use crate::{Problem, Solution};
+use std::collections::hash_map::Entry::{Occupied, Vacant};
+use std::{
+    cmp::Reverse,
+    collections::{BinaryHeap, HashMap, HashSet},
+    str::FromStr,
+};
+
+type Position = (usize, usize);
+
+#[derive(Debug, Default)]
+struct Map {
+    inner: Vec<Vec<char>>,
+}
+
+impl Map {
+    fn solve(self, start_char: char) -> Result<usize> {
+        let mut goal = None;
+        let mut starts = Vec::new();
+
+        for (y, l) in self.inner.iter().enumerate() {
+            for (x, ch) in l.iter().enumerate() {
+                if start_char == *ch {
+                    starts.push((x, y));
+                } else if *ch == 'E' {
+                    goal = Some((x, y));
+                }
+            }
+        }
+
+        let goal = &goal.context("No start position found")?;
+
+        let vertices = self.dijkstra(*goal);
+
+        starts
+            .iter()
+            .flat_map(|p| vertices.get(p))
+            .min()
+            .context(format!("No paths from {start_char} to {goal:?} found"))
+            .copied()
+    }
+
+    pub fn dijkstra(&self, start: Position) -> HashMap<Position, usize> {
+        let mut visited: HashSet<Position> = HashSet::new();
+        let mut scores = HashMap::from([(start, usize::default())]);
+        let mut visit_next = BinaryHeap::from([Reverse((usize::default(), start))]);
+
+        while let Some(Reverse((node_score, node))) = visit_next.pop() {
+            if visited.contains(&node) {
+                continue;
+            }
+
+            for next in self.neighbors(node) {
+                if visited.contains(&next) {
+                    continue;
+                }
+
+                let next_score = node_score + 1;
+
+                match scores.entry(next) {
+                    Occupied(entry) if next_score < *entry.get() => {
+                        *entry.into_mut() = next_score;
+                        visit_next.push(Reverse((next_score, next)));
+                    }
+                    Vacant(entry) => {
+                        entry.insert(next_score);
+                        visit_next.push(Reverse((next_score, next)));
+                    }
+                    _ => {}
+                }
+            }
+
+            visited.insert(node);
+        }
+
+        scores
+    }
+
+    fn neighbors(&self, (x, y): Position) -> Vec<Position> {
+        let value = self.inner[y][x];
+        let height = self.get_height(value);
+        [(-1, 0), (1, 0), (0, 1), (0, -1)]
+            .into_iter()
+            .filter_map(|(dx, dy): (isize, isize)| {
+                let neighbor = ((dx != -1 || x > 0) && (dy != -1 || y > 0))
+                    .then_some(((x as isize + dx) as usize, (y as isize + dy) as usize))?;
+
+                let neighbor_height = self
+                    .inner
+                    .get(neighbor.1)?
+                    .get(neighbor.0)
+                    .map(|c| self.get_height(*c))?;
+
+                (height as isize - neighbor_height as isize <= 1).then_some(neighbor)
+            })
+            .collect()
+    }
+
+    fn get_height(&self, ch: char) -> u8 {
+        match ch {
+            'S' => b'a',
+            'E' => b'z',
+            c => c as u8,
+        }
+    }
+}
+
+impl FromStr for Map {
+    type Err = anyhow::Error;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        Ok(Self {
+            inner: s.lines().map(|l| l.chars().collect()).collect(),
+        })
+    }
+}
+
+pub struct Day12;
+
+impl Problem for Day12 {
+    const DAY: u8 = 12;
+
+    const INPUT: &'static str = include_str!("../input/day_12.txt");
+}
+
+impl Solution for Day12 {
+    type Answer1 = usize;
+
+    type Answer2 = usize;
+
+    fn part_1(input: &str) -> Result<Self::Answer1, anyhow::Error> {
+        Map::from_str(input)?
+            .solve('S')
+            .context("No solution found")
+    }
+
+    fn part_2(input: &str) -> Result<Self::Answer2, anyhow::Error> {
+        Map::from_str(input)?
+            .solve('a')
+            .context("No solution found")
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use pretty_assertions::assert_eq;
+
+    const TEST_INPUT: &str = indoc::indoc! {r#"
+            Sabqponm
+            abcryxxl
+            accszExk
+            acctuvwj
+            abdefghi
+        "#};
+
+    #[test]
+    fn test_part_1_example() -> Result<(), anyhow::Error> {
+        Ok(assert_eq!(31, Day12::part_1(TEST_INPUT)?))
+    }
+
+    #[test]
+    fn test_part_2_example() -> Result<(), anyhow::Error> {
+        Ok(assert_eq!(29, Day12::part_2(TEST_INPUT)?))
+    }
+}