149 lines
3.5 KiB
Rust
149 lines
3.5 KiB
Rust
use std::collections::BinaryHeap;
|
|
|
|
pub fn day15() {
|
|
// let input = r#"
|
|
// 1163751742
|
|
// 1381373672
|
|
// 2136511328
|
|
// 3694931569
|
|
// 7463417111
|
|
// 1319128137
|
|
// 1359912421
|
|
// 3125421639
|
|
// 1293138521
|
|
// 2311944581
|
|
// "#;
|
|
let input = include_str!("../input/day15.txt");
|
|
|
|
let g: Graph<1> = Graph { risks: [[8; 1]; 1] };
|
|
g.print_risks(5);
|
|
|
|
let graph: Graph<100> = input.into();
|
|
|
|
let path = dijkstra(&graph, graph.size(), &(0, 0), &graph.bottom_right());
|
|
// println!("found path: {:?}", path);
|
|
println!("path risk: {}", path_risk(&graph, &path.unwrap()));
|
|
|
|
let path = dijkstra(
|
|
&graph,
|
|
graph.size() * 5,
|
|
&(0, 0),
|
|
&(graph.size() * 5 - 1, graph.size() * 5 - 1),
|
|
);
|
|
// println!("{:?}", path);
|
|
println!("path risk: {}", path_risk(&graph, &path.unwrap()));
|
|
}
|
|
|
|
struct Graph<const N: usize> {
|
|
risks: [[usize; N]; N],
|
|
}
|
|
|
|
impl<const N: usize> Graph<N> {
|
|
fn risk(&self, p: &Point) -> usize {
|
|
let risk = self.risks[p.1 % N][p.0 % N] + (p.0 / N) + (p.1 / N);
|
|
if risk == 9 {
|
|
9
|
|
} else {
|
|
risk % 9
|
|
}
|
|
}
|
|
|
|
fn print_risks(&self, size: usize) {
|
|
for y in 0..size {
|
|
for x in 0..size {
|
|
print!("{}", self.risk(&(x, y)));
|
|
}
|
|
print!("\n");
|
|
}
|
|
}
|
|
|
|
fn size(&self) -> usize {
|
|
N
|
|
}
|
|
|
|
fn bottom_right(&self) -> Point {
|
|
(N - 1, N - 1)
|
|
}
|
|
}
|
|
|
|
impl<const N: usize> From<&str> for Graph<N> {
|
|
fn from(s: &str) -> Self {
|
|
assert_eq!(N, s.trim().lines().count());
|
|
let mut risks = [[0; N]; N];
|
|
for (y, l) in s.trim().lines().enumerate() {
|
|
assert_eq!(N, l.trim().chars().count());
|
|
for (x, c) in l.trim().chars().enumerate() {
|
|
risks[y][x] = c.to_digit(10).unwrap() as usize;
|
|
}
|
|
}
|
|
Graph { risks }
|
|
}
|
|
}
|
|
|
|
type Point = (usize, usize);
|
|
|
|
fn dijkstra<const N: usize>(
|
|
g: &Graph<N>,
|
|
size: usize,
|
|
source: &Point,
|
|
target: &Point,
|
|
) -> Option<Vec<Point>> {
|
|
let mut q: BinaryHeap<(isize, Point)> = BinaryHeap::new();
|
|
let mut dist = vec![vec![usize::MAX; size]; size];
|
|
let mut prev = vec![vec![None; size]; size];
|
|
|
|
dist[source.0][source.1] = 0;
|
|
q.push((0, *source));
|
|
|
|
while let Some((neg_cost, u)) = q.pop() {
|
|
let cost = -neg_cost as usize;
|
|
|
|
if u == *target {
|
|
let mut s = vec![];
|
|
let mut u = Some(u);
|
|
while let Some(p) = u {
|
|
s.insert(0, p);
|
|
u = prev[p.0][p.1];
|
|
}
|
|
return Some(s);
|
|
}
|
|
|
|
if cost > dist[u.0][u.1] {
|
|
continue;
|
|
}
|
|
|
|
for v in neighbors(u, size) {
|
|
let alt = dist[u.0][u.1] + g.risk(&v);
|
|
if alt < dist[v.0][v.1] {
|
|
dist[v.0][v.1] = alt;
|
|
prev[v.0][v.1] = Some(u);
|
|
q.push((-(alt as isize), v));
|
|
}
|
|
}
|
|
}
|
|
|
|
None
|
|
}
|
|
|
|
fn neighbors(point: Point, max: usize) -> Vec<Point> {
|
|
let mut points = vec![];
|
|
if point.0 > 0 {
|
|
points.push((point.0 - 1, point.1));
|
|
}
|
|
if point.0 < max - 1 {
|
|
points.push((point.0 + 1, point.1));
|
|
}
|
|
if point.1 > 0 {
|
|
points.push((point.0, point.1 - 1));
|
|
}
|
|
if point.1 < max - 1 {
|
|
points.push((point.0, point.1 + 1));
|
|
}
|
|
points
|
|
}
|
|
|
|
fn path_risk<const N: usize>(g: &Graph<N>, path: &[Point]) -> usize {
|
|
// first position is never counted
|
|
path.iter().skip(1).map(|p| g.risk(p)).sum()
|
|
}
|