diff options
author | Justin Wernick <justin@worthe-it.co.za> | 2023-12-17 12:46:49 +0200 |
---|---|---|
committer | Justin Wernick <justin@worthe-it.co.za> | 2023-12-17 12:46:49 +0200 |
commit | 411454681b29bcdb2ac226a2d6ed7a2d988a8edc (patch) | |
tree | 37f58b04988f8c75dcbee0d158648f09f83d8a72 /2023/src | |
parent | 0b21e94cf7a84bf9b02a27b8eee8a8a5206e680c (diff) |
Day 17 part 1
Diffstat (limited to '2023/src')
-rw-r--r-- | 2023/src/bin/day_17.rs | 98 |
1 files changed, 82 insertions, 16 deletions
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)) +} |