From 411454681b29bcdb2ac226a2d6ed7a2d988a8edc Mon Sep 17 00:00:00 2001
From: Justin Wernick <justin@worthe-it.co.za>
Date: Sun, 17 Dec 2023 12:46:49 +0200
Subject: Day 17 part 1

---
 2023/src/bin/day_17.rs | 98 +++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 82 insertions(+), 16 deletions(-)

(limited to '2023/src')

diff --git a/2023/src/bin/day_17.rs b/2023/src/bin/day_17.rs
index 9cd6d76..99d828b 100644
--- a/2023/src/bin/day_17.rs
+++ b/2023/src/bin/day_17.rs
@@ -5,7 +5,7 @@ use nom::{
     multi::{many1, separated_list1},
     IResult,
 };
-use std::fs;
+use std::{collections::HashSet, fs};
 
 fn main() -> Result<(), Box<dyn std::error::Error>> {
     let input = fs::read_to_string("inputs/day_17.txt")?;
@@ -18,10 +18,10 @@ fn main() -> Result<(), Box<dyn std::error::Error>> {
 #[derive(Debug)]
 struct HeatlossMap(DMatrix<u32>);
 
-#[derive(Debug)]
+#[derive(Debug, Hash, PartialEq, Eq, Clone)]
 struct Position {
-    pos: Point2<usize>,
-    facing: Unit<Vector2<usize>>,
+    pos: Point2<isize>,
+    facing: Unit<Vector2<isize>>,
     duration_with_facing: usize,
 }
 
@@ -44,25 +44,91 @@ impl HeatlossMap {
         )(input)
     }
 
-    fn find_shortest_heatloss_path(&self) -> usize {
+    fn find_shortest_heatloss_path(&self) -> u32 {
         let start = Position {
             pos: Point2::new(0, 0),
             facing: Vector2::x_axis(),
             duration_with_facing: 0,
         };
+        let end_pos = self.end();
+
+        let mut frontier = vec![(0, start.clone())];
+        let mut visited = HashSet::new();
+        visited.insert(start);
+
+        let mut distance_to_end = None;
+        while distance_to_end.is_none() && frontier.len() > 0 {
+            // shortest distance is now at the end
+            frontier
+                .sort_unstable_by(|(distance_a, _), (distance_b, _)| distance_b.cmp(distance_a));
+            let (front_distance, front_position) = frontier.pop().unwrap();
+
+            let mut next_points: Vec<Position> = Vec::new();
+            {
+                let facing = rotate_left(&front_position.facing);
+                let pos = front_position.pos + *facing;
+                next_points.push(Position {
+                    pos,
+                    facing,
+                    duration_with_facing: 1,
+                });
+            }
+            {
+                let facing = rotate_right(&front_position.facing);
+                let pos = front_position.pos + *facing;
+                next_points.push(Position {
+                    pos,
+                    facing,
+                    duration_with_facing: 1,
+                });
+            }
+            if front_position.duration_with_facing < 3 {
+                let pos = front_position.pos + *front_position.facing;
+                next_points.push(Position {
+                    pos,
+                    facing: front_position.facing.clone(),
+                    duration_with_facing: front_position.duration_with_facing + 1,
+                });
+            }
+
+            for next_point in next_points {
+                if let Some(step_distance) = self.get(&next_point.pos) {
+                    if !visited.contains(&next_point) {
+                        visited.insert(next_point.clone());
+
+                        let distance = front_distance + step_distance;
+
+                        if next_point.pos == end_pos {
+                            distance_to_end = Some(distance);
+                        }
+                        frontier.push((distance, next_point));
+                    }
+                }
+            }
+        }
 
-        dbg!(&start);
-        dbg!(self.0.get((start.pos.x, start.pos.y)));
+        distance_to_end.unwrap()
+    }
+
+    fn end(&self) -> Point2<isize> {
+        Point2::new(self.0.ncols() as isize - 1, self.0.nrows() as isize - 1)
+    }
 
-        let moved_pos = start.pos + *start.facing;
-        dbg!(&moved_pos);
-        dbg!(self.0.get((moved_pos.x, moved_pos.y)));
-        // start is 0,0
-        // end is max,max
-        // can't go more than 3 in a straight line
-        // can only turn left or right, not go backwards
-        //
+    fn get(&self, pos: &Point2<isize>) -> Option<u32> {
+        let x: Option<usize> = pos.x.try_into().ok();
+        let y: Option<usize> = pos.y.try_into().ok();
 
-        todo!()
+        match (x, y) {
+            (Some(x), Some(y)) => self.0.get((x, y)).copied(),
+            _ => None,
+        }
     }
 }
+
+fn rotate_left(facing: &Unit<Vector2<isize>>) -> Unit<Vector2<isize>> {
+    Unit::new_unchecked(Vector2::new(-facing.y, facing.x))
+}
+
+fn rotate_right(facing: &Unit<Vector2<isize>>) -> Unit<Vector2<isize>> {
+    Unit::new_unchecked(Vector2::new(facing.y, -facing.x))
+}
-- 
cgit v1.2.3