feat(wip): impl day 10, off by 20

3 files changed, 363 insertions, 2 deletions

diff --git a/src/day_10.rs b/src/day_10.rs
new file mode 100644
index 0000000..00d26d7
--- /dev/null
+++ b/src/day_10.rs
@@ -0,0 +1,353 @@
+use std::{
+    cmp::Ordering,
+    collections::{BTreeMap, HashMap},
+};
+
+use anyhow::Context;
+
+use crate::{Problem, Solution};
+
+pub struct Day10;
+
+impl Problem for Day10 {
+    const DAY: u8 = 10;
+
+    const INPUT: &'static str = include_str!("../input/day_10.txt");
+}
+
+impl Solution for Day10 {
+    type Answer1 = usize;
+
+    type Answer2 = usize;
+
+    fn part_1(input: &str) -> anyhow::Result<Self::Answer1> {
+        let graph: Graph = input.parse()?;
+
+        let mut path = Vec::new();
+        let mut pos = graph.start;
+        let mut c = &'S';
+        let mut next_edge = Edge::ALL.into_iter().find(|e| {
+            e.traverse(pos)
+                .and_then(|p| graph.inner.get(&p))
+                .map(|c| e.valid_edge(c))
+                .unwrap_or_default()
+        });
+
+        while let Some(edge) = next_edge {
+            path.push((edge, c));
+            pos = edge.traverse(pos).context("Out-of-bounds move")?;
+            c = graph.inner.get(&pos).context("Failed to get postion")?;
+            next_edge = edge.exit(c);
+            if c == &'S' {
+                break;
+            }
+        }
+
+        Ok(path.len() / 2)
+    }
+
+    fn part_2(input: &str) -> anyhow::Result<Self::Answer2> {
+        let mut graph: Graph = input.parse()?;
+        graph.solve()?;
+
+        println!("{graph}");
+        Ok(graph
+            .inner
+            .iter()
+            .filter(|(pos, _)| graph.is_included(pos))
+            .count())
+
+        // 543 >
+    }
+}
+
+type Position = (usize, usize);
+type Path = BTreeMap<usize, BTreeMap<usize, char>>;
+
+#[derive(Default)]
+struct Graph {
+    inner: HashMap<Position, char>,
+    start: Position,
+    path: Path,
+}
+
+impl Graph {
+    fn solve(&mut self) -> anyhow::Result<()> {
+        let mut pos = self.start;
+        let mut next_edge = Edge::ALL.into_iter().find(|e| {
+            e.traverse(pos)
+                .and_then(|p| self.inner.get(&p))
+                .map(|c| e.valid_edge(c))
+                .unwrap_or_default()
+        });
+        let mut c = &'S';
+        let start_edge = next_edge.to_owned().unwrap();
+
+        while let Some(edge) = next_edge {
+            self.path
+                .entry(pos.0)
+                .and_modify(|v: &mut BTreeMap<usize, char>| {
+                    v.insert(pos.1, *c);
+                })
+                .or_insert(BTreeMap::from([(pos.1, *c)]));
+            pos = edge.traverse(pos).context("Out-of-bounds move")?;
+            c = self.inner.get(&pos).context("Failed to get postion")?;
+            if c == &'S' {
+                self.path
+                    .entry(pos.0)
+                    .and_modify(|v: &mut BTreeMap<usize, char>| {
+                        assert_eq!(
+                            Some('S'),
+                            v.insert(pos.1, edge.as_char(&start_edge).unwrap())
+                        );
+                    });
+                break;
+            }
+            next_edge = edge.exit(c);
+        }
+        Ok(())
+    }
+
+    fn is_included(&self, pos: &Position) -> bool {
+        let mut seg_start = ' ';
+        let mut left = 0;
+        let mut right = 0;
+
+        let line = match self.path.get(&pos.0) {
+            Some(b) if b.get(&pos.1).is_none() => b,
+            _ => return false,
+        };
+
+        for (col, c) in line.iter() {
+            let count = match col.cmp(&pos.1) {
+                Ordering::Less => &mut left,
+                Ordering::Greater => &mut right,
+                Ordering::Equal if left % 2 != 0 => return true,
+                Ordering::Equal => continue,
+            };
+
+            match c {
+                '|' => *count += 1,
+                'F' => seg_start = 'F',
+                'L' => seg_start = 'L',
+                'J' if seg_start == 'F' => *count += 1,
+                '7' if seg_start == 'L' => *count += 1,
+                'J' if seg_start == 'L' => seg_start = ' ',
+                '7' if seg_start == 'F' => seg_start = ' ',
+                _ => {}
+            }
+        }
+
+        left % 2 != 0 || right % 2 != 0
+    }
+}
+
+impl std::str::FromStr for Graph {
+    type Err = anyhow::Error;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        let inner = s
+            .trim()
+            .lines()
+            .enumerate()
+            .flat_map(|(row, line)| {
+                line.trim()
+                    .chars()
+                    .enumerate()
+                    .map(move |(col, char)| ((row, col), char))
+            })
+            .collect::<HashMap<_, _>>();
+
+        let start = inner
+            .iter()
+            .find_map(|(pos, c)| (c == &'S').then_some(pos))
+            .context("Failed to find start")?;
+
+        Ok(Graph {
+            start: *start,
+            inner,
+            ..Default::default()
+        })
+    }
+}
+
+impl std::fmt::Debug for Graph {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        let (height, width) = self.inner.keys().max().unwrap();
+        for row in 0..height + 1 {
+            let Some(btree) = self.path.get(&row) else {
+                writeln!(f)?;
+                continue;
+            };
+            let mut output = String::new();
+            for col in 0..width + 1 {
+                match btree.get(&col) {
+                    Some(c) => output.push(*c),
+                    None if self.is_included(&(row, col)) => output.push('I'),
+                    None => output.push('O'),
+                };
+            }
+            writeln!(f, "{output}")?
+        }
+        Ok(())
+    }
+}
+
+impl std::fmt::Display for Graph {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        let (height, width) = self.inner.keys().max().unwrap();
+        for row in 0..height + 1 {
+            let Some(btree) = self.path.get(&row) else {
+                writeln!(f)?;
+                continue;
+            };
+            let mut output = String::new();
+            for col in 0..width + 1 {
+                match btree.get(&col) {
+                    Some('|') => output.push('│'),
+                    Some('-') => output.push('─'),
+                    Some('L') => output.push('└'),
+                    Some('J') => output.push('┘'),
+                    Some('7') => output.push('┐'),
+                    Some('F') => output.push('┌'),
+                    Some(c) => output.push(*c),
+                    None if self.is_included(&(row, col)) => output.push('I'),
+                    None => output.push('O'),
+                };
+            }
+            writeln!(f, "{output}")?
+        }
+        Ok(())
+    }
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+enum Edge {
+    Up,
+    Down,
+    Left,
+    Right,
+}
+
+impl Edge {
+    const ALL: [Edge; 4] = [Self::Up, Self::Down, Self::Left, Self::Right];
+
+    fn traverse(&self, (row, col): Position) -> Option<Position> {
+        Some(match self {
+            Edge::Up => (row.checked_sub(1)?, col),
+            Edge::Down => (row.checked_add(1)?, col),
+            Edge::Left => (row, col.checked_sub(1)?),
+            Edge::Right => (row, col.checked_add(1)?),
+        })
+    }
+
+    fn valid_edge(&self, &c: &char) -> bool {
+        match self {
+            Edge::Up => c == '|' || c == '7' || c == 'F',
+            Edge::Down => c == '|' || c == 'J' || c == 'L',
+            Edge::Left => c == '-' || c == 'F' || c == 'L',
+            Edge::Right => c == '-' || c == 'J' || c == '7',
+        }
+    }
+
+    fn exit(&self, &c: &char) -> Option<Self> {
+        Some(match (self, c) {
+            (Edge::Up, '|') => Edge::Up,
+            (Edge::Up, '7') => Edge::Left,
+            (Edge::Up, 'F') => Edge::Right,
+            (Edge::Down, '|') => Edge::Down,
+            (Edge::Down, 'J') => Edge::Left,
+            (Edge::Down, 'L') => Edge::Right,
+            (Edge::Left, '-') => Edge::Left,
+            (Edge::Left, 'F') => Edge::Down,
+            (Edge::Left, 'L') => Edge::Up,
+            (Edge::Right, '-') => Edge::Right,
+            (Edge::Right, 'J') => Edge::Up,
+            (Edge::Right, '7') => Edge::Down,
+            _ => None?,
+        })
+    }
+
+    fn as_char(&self, other: &Edge) -> Option<char> {
+        Some(match (self, other) {
+            (Edge::Up, Edge::Down) | (Edge::Down, Edge::Up) => '|',
+            (Edge::Up, Edge::Left) | (Edge::Left, Edge::Up) => 'J',
+            (Edge::Up, Edge::Right) | (Edge::Right, Edge::Up) => 'L',
+            (Edge::Down, Edge::Left) | (Edge::Left, Edge::Down) => '7',
+            (Edge::Down, Edge::Right) | (Edge::Right, Edge::Down) => 'F',
+            (Edge::Left, Edge::Right) | (Edge::Right, Edge::Left) => '-',
+            _ => None?,
+        })
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_part_1() -> anyhow::Result<()> {
+        const INPUT: &str = indoc::indoc! {"
+            ..F7.
+            .FJ|.
+            SJ.L7
+            |F--J
+            LJ...
+        "};
+
+        Ok(assert_eq!(8, Day10::part_1(INPUT)?))
+    }
+
+    #[test]
+    fn test_part_2_1() -> anyhow::Result<()> {
+        const INPUT: &str = indoc::indoc! {"
+            FF7FSF7F7F7F7F7F---7
+            L|LJ||||||||||||F--J
+            FL-7LJLJ||||||LJL-77
+            F--JF--7||LJLJ7F7FJ-
+            L---JF-JLJ.||-FJLJJ7
+            |F|F-JF---7F7-L7L|7|
+            |FFJF7L7F-JF7|JL---7
+            7-L-JL7||F7|L7F-7F7|
+            L.L7LFJ|||||FJL7||LJ
+            L7JLJL-JLJLJL--JLJ.L
+        "};
+
+        Ok(assert_eq!(10, Day10::part_2(INPUT)?))
+    }
+
+    #[test]
+    fn test_part_2_2() -> anyhow::Result<()> {
+        const INPUT: &str = indoc::indoc! {"
+            .F----7F7F7F7F-7....
+            .|F--7||||||||FJ....
+            .||.FJ||||||||L7....
+            FJL7L7LJLJ||LJ.L-7..
+            L--J.L7...LJS7F-7L7.
+            ....F-J..F7FJ|L7L7L7
+            ....L7.F7||L7|.L7L7|
+            .....|FJLJ|FJ|F7|.LJ
+            ....FJL-7.||.||||...
+            ....L---J.LJ.LJLJ...
+        "};
+
+        Ok(assert_eq!(8, Day10::part_2(INPUT)?))
+    }
+
+    #[test]
+    fn test_part_2_3() -> anyhow::Result<()> {
+        const INPUT: &str = indoc::indoc! {"
+            ...........
+            .S-------7.
+            .|F-----7|.
+            .||.....||.
+            .||.....||.
+            .|L-7.F-J|.
+            .|..|.|..|.
+            .L--J.L--J.
+            ...........
+        "};
+
+        Ok(assert_eq!(4, Day10::part_2(INPUT)?))
+    }
+}
diff --git a/src/lib.rs b/src/lib.rs
index 97b4b74..d38ead1 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1,4 +1,10 @@
-#![feature(iterator_try_collect, iter_array_chunks, array_windows, let_chains)]
+#![feature(
+    iterator_try_collect,
+    iter_array_chunks,
+    array_windows,
+    array_chunks,
+    let_chains
+)]
 
 pub mod day_01;
 pub mod day_02;
@@ -9,6 +15,7 @@ pub mod day_06;
 pub mod day_07;
 pub mod day_08;
 pub mod day_09;
+pub mod day_10;
 
 pub trait Problem {
     const DAY: u8;
diff --git a/src/main.rs b/src/main.rs
index fa19b95..ad87f73 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,6 +1,6 @@
 use aoc_2023::{
     day_01::Day01, day_02::Day02, day_03::Day03, day_04::Day04, day_05::Day05, day_06::Day06,
-    day_07::Day07, day_08::Day08, day_09::Day09, Solution,
+    day_07::Day07, day_08::Day08, day_09::Day09, day_10::Day10, Solution,
 };
 
 fn main() -> anyhow::Result<()> {
@@ -13,6 +13,7 @@ fn main() -> anyhow::Result<()> {
     Day07::solve()?;
     Day08::solve()?;
     Day09::solve()?;
+    Day10::solve()?;
 
     Ok(())
 }