155 lines
3.9 KiB
Rust
155 lines
3.9 KiB
Rust
use std::cmp::Ordering;
|
|
use std::collections::BinaryHeap;
|
|
use std::collections::HashMap;
|
|
use std::collections::HashSet;
|
|
use std::error::Error;
|
|
use std::fs::File;
|
|
use std::io::{self, BufRead};
|
|
use std::vec::Vec;
|
|
|
|
fn get_risk(x: i32, y: i32, map: &Vec<Vec<u32>>) -> Option<u32> {
|
|
let tw = map[0].len() as i32;
|
|
let th = map.len() as i32;
|
|
let mw = tw * 5;
|
|
let mh = th * 5;
|
|
|
|
if y >= 0 && y < mh as i32 && x >= 0 && x < mw as i32 {
|
|
let tile_x = x / tw;
|
|
let tile_y = y / th;
|
|
let mx = x % tw;
|
|
let my = y % th;
|
|
|
|
let mut risk = map[my as usize][mx as usize] + tile_x as u32 + tile_y as u32;
|
|
while risk > 9 {
|
|
risk -= 9;
|
|
}
|
|
|
|
Some(risk)
|
|
} else {
|
|
None
|
|
}
|
|
}
|
|
|
|
#[derive(Copy, Clone, Eq, PartialEq, Debug)]
|
|
struct Point {
|
|
risk: u32,
|
|
x: i32,
|
|
y: i32,
|
|
}
|
|
|
|
impl Ord for Point {
|
|
fn cmp(&self, other: &Self) -> Ordering {
|
|
other
|
|
.risk
|
|
.cmp(&self.risk)
|
|
.then_with(|| self.x.cmp(&other.x))
|
|
.then_with(|| self.y.cmp(&other.y))
|
|
}
|
|
}
|
|
|
|
// `PartialOrd` needs to be implemented as well.
|
|
impl PartialOrd for Point {
|
|
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
|
|
Some(self.cmp(other))
|
|
}
|
|
}
|
|
|
|
fn do_the_dijkstra(
|
|
start_x: i32,
|
|
start_y: i32,
|
|
target_x: i32,
|
|
target_y: i32,
|
|
map: &Vec<Vec<u32>>,
|
|
) -> u32 {
|
|
let mut unexplored: HashSet<(i32, i32)> = HashSet::new();
|
|
|
|
let mut path_risk: HashMap<(i32, i32), u32> = HashMap::new();
|
|
path_risk.insert((start_x, start_y), 0);
|
|
|
|
let mut heap: BinaryHeap<Point> = BinaryHeap::new();
|
|
heap.push(Point {
|
|
x: start_x,
|
|
y: start_y,
|
|
risk: 0,
|
|
});
|
|
|
|
for x in 0..target_x + 1 {
|
|
for y in 0..target_y + 1 {
|
|
unexplored.insert((x as i32, y as i32));
|
|
}
|
|
}
|
|
|
|
while !unexplored.is_empty() {
|
|
let point = heap.pop().unwrap();
|
|
|
|
let cur_node = (point.x, point.y);
|
|
let cur_risk = point.risk;
|
|
|
|
if cur_risk > path_risk[&cur_node] {
|
|
continue;
|
|
}
|
|
|
|
println!("{:?} {}", cur_node, unexplored.len());
|
|
|
|
unexplored.remove(&cur_node);
|
|
|
|
if cur_node.0 == target_x && cur_node.1 == target_y {
|
|
println!("Found my target!");
|
|
return cur_risk;
|
|
}
|
|
|
|
for (dx, dy) in [(1, 0), (0, 1), (-1, 0), (0, -1)] {
|
|
let neighboor = (cur_node.0 + dx, cur_node.1 + dy);
|
|
if let Some(enter_risk) = get_risk(neighboor.0, neighboor.1, &map) {
|
|
let alt_risk = path_risk[&cur_node] + enter_risk;
|
|
if !path_risk.contains_key(&neighboor) {
|
|
path_risk.insert(neighboor, alt_risk);
|
|
heap.push(Point {
|
|
x: neighboor.0,
|
|
y: neighboor.1,
|
|
risk: alt_risk,
|
|
});
|
|
} else if alt_risk < path_risk[&neighboor] {
|
|
path_risk.insert(neighboor, alt_risk);
|
|
heap.push(Point {
|
|
x: neighboor.0,
|
|
y: neighboor.1,
|
|
risk: alt_risk,
|
|
});
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
fn main() -> Result<(), Box<dyn Error>> {
|
|
let file = File::open("inputs/day15.txt")?;
|
|
let map: Vec<Vec<u32>> = io::BufReader::new(file)
|
|
.lines()
|
|
.map(|l| {
|
|
l.unwrap()
|
|
.chars()
|
|
.map(|c| c.to_string().parse().unwrap())
|
|
.collect()
|
|
})
|
|
.collect();
|
|
|
|
let target_x = map[0].len() as i32 - 1;
|
|
let target_y = map.len() as i32 - 1;
|
|
|
|
let answer1 = do_the_dijkstra(0, 0, target_x, target_y, &map);
|
|
|
|
let target2_x = (map[0].len() * 5) as i32 - 1;
|
|
let target2_y = (map.len() * 5) as i32 - 1;
|
|
|
|
let answer2 = do_the_dijkstra(0, 0, target2_x, target2_y, &map);
|
|
|
|
println!("Answer1: {}", answer1);
|
|
|
|
println!("Answer2: {}", answer2);
|
|
|
|
Ok(())
|
|
}
|