Day 15 Code

use std::env;
use std::io::{self, prelude::*, BufReader};
use std::fs::File;
use std::collections::{HashMap,HashSet};

use std::collections::BinaryHeap;
use std::cmp::Ordering;

use point2d::point2d::Point2D;

const MAP_MULTIPLIER: i64 = 5;

#[derive(PartialEq,Eq)]
struct Path {
    pt: Point2D,
    cost: i64,
}
impl Ord for Path {
    fn cmp(&self, other: &Self) -> Ordering {
        other.cost.cmp(&self.cost)
    }
}
impl PartialOrd for Path {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(other.cost.cmp(&self.cost))
    }
}

fn neighbor_addresses(pt: &Point2D) -> Vec<Point2D> {
    vec![Point2D { x: pt.x  , y: pt.y-1 },  // up
         Point2D { x: pt.x+1, y: pt.y   },  // right
         Point2D { x: pt.x  , y: pt.y+1 },  // down
         Point2D { x: pt.x-1, y: pt.y   }] // left
}

fn map_extents(map: &HashMap<Point2D,i64>) -> (i64,i64,i64,i64) {
    let xmin = &map.keys().map(|&pt| pt.x).min().unwrap();
    let ymin = &map.keys().map(|&pt| pt.y).min().unwrap();
    let xmax = &map.keys().map(|&pt| pt.x).max().unwrap();
    let ymax = &map.keys().map(|&pt| pt.y).max().unwrap();
    (*xmin,*ymin,*xmax,*ymax)
}

fn least_risky(map: &HashMap<Point2D,i64>) -> i64 {
    // Prepare
    let (xmin,ymin,xmax,ymax) = map_extents(&map);
    let mut visited: HashSet<Point2D> = HashSet::new();

    // Explore
    let mut heap: BinaryHeap<Path> = BinaryHeap::new();
    let start = Point2D { x: xmin, y: ymin };
    let end = Point2D { x: xmax, y: ymax };
    heap.push(Path{pt: start, cost: 0});
    while heap.len() > 0 {

        let path = heap.pop().unwrap();
        let (now,current_risk) = (path.pt, path.cost);

        'n_loop: for neighbor in neighbor_addresses(&now) {

            // Check already visited
            match visited.get(&neighbor) {
                Some(_) => { continue 'n_loop; },
                None => {},
            }
            visited.insert(neighbor);

            // Determine risk level
            let new_risk = match map.get(&neighbor) {
                Some(this_risk) => current_risk+this_risk,
                None => { continue 'n_loop; }, // off the map
            };

            // Found the end
            if neighbor == end {
                return new_risk;
            }
            heap.push(Path{pt: neighbor, cost: new_risk});
        }
    }
    i64::MAX
}

fn solve(input: &str) -> io::Result<()> {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    // Input
    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {}", err),
        Ok(result) => result,
    };

    // Build map (part 1)
    let mut risk_map: HashMap<Point2D,i64> = HashMap::new();
    for (y,line) in input.iter().enumerate() {
        for (x,risk) in line.chars().enumerate() {
            let pt = Point2D { x: x as i64, y: y as i64 };
            risk_map.insert(pt, risk.to_digit(10).unwrap().try_into().unwrap());
        }
    }

    // Build map (part 2)
    let mut risk_map2 = risk_map.clone();
    let (xmin,ymin,xmax,ymax) = map_extents(&risk_map2);
    for y in ymin..(ymax+1)*MAP_MULTIPLIER {
        for x in xmin..(xmax+1)*MAP_MULTIPLIER {
            let pt = &Point2D{x: x, y: y};
            match risk_map2.get(pt) {
                Some(_) => {}, // Already populated
                None => {
                    // New point
                    let ref_pt = if y <= ymax {
                        Point2D { x: x-xmax-1, y: y }  // Reference left
                    } else {
                        Point2D { x: x , y: y-ymax-1 } // Reference up
                    };
                    let new_value = match risk_map2.get(&ref_pt) {
                        Some(z @ 1..=8) => z + 1,
                        Some(9) => 1,
                        Some(_) | None => unreachable!(),
                    };
                    risk_map2.insert(*pt,new_value);
                },
            }
        }
    }

    let part1 = least_risky(&risk_map.clone());
    println!("Part 1: {}", part1); // 537

    let part2 = least_risky(&risk_map2.clone());
    println!("Part 2: {}", part2); // 2881
    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    solve(&filename).unwrap();
}