AOC day 15 Dijkstra's

day15.rs

use std::{
    cmp::Ordering,
    collections::{BinaryHeap, HashMap, HashSet},
    fs::read_to_string,
};

#[derive(Clone, Debug)]
struct Vertex {
    row: usize,
    column: usize,
    cost: i32,
}

impl Ord for Vertex {
    fn cmp(&self, other: &Self) -> Ordering {
        self.cost.cmp(&other.cost).reverse()
    }
}

impl PartialOrd for Vertex {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cost.cmp(&other.cost).reverse())
    }
}

impl PartialEq for Vertex {
    fn eq(&self, other: &Self) -> bool {
        self.cost == other.cost
    }
}

impl Eq for Vertex {}

#[derive(Clone, Debug)]
struct ShortestPath {
    cost: i32,
    prev: Option<(usize, usize)>,
}

#[derive(Clone, Debug)]
struct Adjacency {
    from: Option<(usize, usize)>,
    to: Option<(usize, usize)>,
    cost: i32,
}
impl Adjacency {
    fn new(from: Option<(usize, usize)>, to: Option<(usize, usize)>, cost: i32) -> Self {
        Adjacency { from, to, cost }
    }
}

impl Ord for Adjacency {
    fn cmp(&self, other: &Self) -> Ordering {
        self.cost.cmp(&other.cost).reverse()
    }
}

impl PartialOrd for Adjacency {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cost.cmp(&other.cost).reverse())
    }
}

impl PartialEq for Adjacency {
    fn eq(&self, other: &Self) -> bool {
        self.cost == other.cost
    }
}

impl Eq for Adjacency {}

fn get_input() -> Vec<Vec<i32>> {
    let str = read_to_string("input").unwrap();
    let vec: Vec<Vec<i32>> = str
        .split("\n")
        .map(|line| {
            line.trim()
                .split("")
                .filter(|s| !s.is_empty())
                .map(|s| s.parse().unwrap())
                .collect::<Vec<i32>>()
        })
        .collect();
    vec
}

fn main() {
    let mut heap: BinaryHeap<Adjacency> = BinaryHeap::new();
    let mut adjacency_list: HashMap<String, Vec<Adjacency>> = HashMap::new();

    let input = get_input();

    let mut shortest_path: Vec<Vec<Option<ShortestPath>>> =
        vec![vec![None; input[0].len()]; input.len()];

    let mut processed = HashSet::new();

    for row in 0..input.len() {
        for column in 0..input[0].len() {
            let key = format!("{},{}", row.to_string(), column.to_string());
            let _value = input[row][column];
            let map = adjacency_list.entry(key.clone()).or_default();

            if (row + 1) < input.len() {
                map.push(Adjacency::new(
                    Some((row, column)),
                    Some((row + 1, column)),
                    input[row + 1][column],
                ));
            }

            if row > 0 {
                map.push(Adjacency::new(
                    Some((row, column)),
                    Some((row - 1, column)),
                    input[row - 1][column],
                ));
            }

            if (column + 1) < input[row].len() {
                map.push(Adjacency::new(
                    Some((row, column)),
                    Some((row, column + 1)),
                    input[row][column + 1],
                ));
            }

            if column > 0 {
                map.push(Adjacency::new(
                    Some((row, column)),
                    Some((row, column - 1)),
                    input[row][column - 1],
                ));
            }
        }
    }

    let start = Adjacency::new(None, Some((0, 0)), 0);
    heap.push(start);

    shortest_path[0][0] = Some(ShortestPath {
        cost: 0,
        prev: None,
    });

    while heap.len() > 0 {
        let adjacency = heap.pop().unwrap();
        let (row, column) = adjacency.to.unwrap();
        let cost = adjacency.cost;

        let key = format!("{},{}", row.to_string(), column.to_string());

        if processed.contains(&key) {
            continue;
        }

        let value = cost;

        if adjacency_list.contains_key(&key) {
            for adj in &adjacency_list[&key] {
                heap.push(Adjacency {
                    cost: adj.cost + cost,
                    ..adj.clone()
                })
            }
        }

        processed.insert(key.clone());

        if let Some(prev_shortest) = &shortest_path[row][column] {
            if prev_shortest.cost > value {
                shortest_path[row][column] = Some(ShortestPath {
                    cost: value,
                    prev: adjacency.from,
                });
            }
        } else {
            shortest_path[row][column] = Some(ShortestPath {
                cost: value,
                prev: adjacency.from,
            });
        }
    }
    let ans = shortest_path
        .last()
        .unwrap()
        .last()
        .unwrap()
        .clone()
        .unwrap()
        .cost;

    println!("shortest path is {}", ans);
}