day15.rs

const DIRS: [Point; 4] = [Point(1, 0), Point(0, 1), Point(-1, 0), Point(0, -1)];
type FindPathResult = (Vec<Point>, usize);

#[derive(Debug, PartialEq, Eq, Hash, Copy, Clone, PartialOrd, Ord)]
pub struct Point(pub isize, pub isize);

impl Add for Point {
    type Output = Point;

    fn add(self, r: Point) -> <Self as std::ops::Add<Point>>::Output {
        Point(self.0 + r.0, self.1 + r.1)
    }
}

impl Sub for Point {
    type Output = Point;

    fn sub(self, rhs: Self) -> Self::Output {
        Point(self.0 - rhs.0, self.1 - rhs.1)
    }
}

impl Point {
    fn distance(&self, other: &Point) -> isize {
        let diff = Point((self.0 - other.0).abs(), (self.1 - other.1).abs());
        diff.sqr_mag()
    }

    fn sqr_mag(&self) -> isize {
        self.0 * self.0 + self.1 * self.1
    }
}

#[derive(PartialEq, Eq, Hash, Copy, Clone)]
struct Index(usize, usize);

impl Into<Index> for Point {
    fn into(self) -> Index {
        Index(self.0 as usize, self.1 as usize)
    }
}

impl Into<Point> for Index {
    fn into(self) -> Point {
        Point(self.0 as isize, self.1 as isize)
    }
}

#[derive(Default, Clone)]
pub struct Map {
    data: Vec<isize>,
    pub w: usize,
    pub h: usize,
}

impl Map {
    fn neighbours_pos<'a>(&self, point: Point) -> Box<dyn Iterator<Item = Point> + 'a> {
        let (w, h) = (self.w, self.h);
        Box::new(
            DIRS.iter()
                .map(move |&e| point + e)
                .filter(move |e| in_bounds(e, w, h)),
        )
    }

    fn get_risk(&self, index: &Index) -> isize {
        self.data[index.1 * self.w + index.0]
    }

    fn set(&mut self, index: &Index, val: isize) {
        self.data[index.1 * self.w + index.0] = val;
    }

    fn to_idx(&self, point: Point) -> usize {
        self.w * point.1 as usize + point.0 as usize
    }

    fn to_point(&self, idx: usize) -> Point {
        Point((idx / self.w) as isize, (idx % self.w) as isize)
    }

    pub fn grow(&mut self) {
        let mut grow_lookup = vec![self.data.clone()];
        grow_lookup.extend((1..9).map(|i| {
            self.data
                .iter()
                .map(|e| (e + i - 1) % 9 + 1)
                .collect::<Vec<isize>>()
        }));

        let w = self.w * 5;
        let h = self.h * 5;
        let mut nmap = vec![-1isize; w * h];

        for y in 0..5usize {
            for x in 0..5usize {
                let risk_offset = ((x % 5) + (y % 5)) as isize;
                let cp = &grow_lookup[risk_offset as usize];

                for yy in 0..self.h {
                    let idy = y * self.w + yy;
                    for xx in 0..self.w {
                        let idx = x * self.w + xx;
                        let val = cp[yy * self.w + xx];

                        nmap[idy * w + idx] = val;
                    }
                }
            }
        }

        self.w = w;
        self.h = h;
        self.data = nmap;
    }

    fn in_bounds(&self, point: &Point) -> bool {
        point.0 >= 0 && point.1 >= 0 && point.0 < self.w as isize && point.1 < self.h as isize
    }
}

fn in_bounds(point: &Point, w: usize, h: usize) -> bool {
    point.0 >= 0 && point.1 >= 0 && point.0 < w as isize && point.1 < h as isize
}

#[derive(Copy, Clone, Eq, PartialEq)]
struct Node {
    point: Point,
    tot_risk: isize,
}

impl Ord for Node {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.tot_risk.cmp(&self.tot_risk)
    }
}

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

#[derive(Default)]
pub struct AOC15 {
    pub map: Map,
}

impl Runner for AOC15 {
    fn parse(&mut self, input: &Vec<String>) {
        let data: Vec<isize> = input
            .iter()
            .map(|e| e.chars().map(|c| c as isize - 48).collect::<Vec<isize>>())
            .flatten()
            .collect();

        self.map = Map {
            w: input[0].len(),
            h: input.len(),
            data: data,
        };
    }

    fn run_p1(&self) -> usize {
        let end = Point(self.map.w as isize - 1, self.map.h as isize - 1);
        let risk_lookup = gen_risk_lookup(&self.map, end).unwrap();

        return get_risk(Point(0, 0), end, &self.map, &risk_lookup);
    }

    fn run_p2(&self) -> usize {
        let mut map = self.map.clone();
        map.grow();

        let end = Point(map.w as isize - 1, map.h as isize - 1);
        let risk_lookup = gen_risk_lookup(&map, end).unwrap();

        return get_risk(Point(0, 0), end, &map, &risk_lookup);
    }
}

// Retreive the path risk from the risk lookup
pub fn get_risk(start: Point, end: Point, map: &Map, risk_lookup: &Map) -> usize {
    return risk_lookup.get_risk(&start.into()) as usize + map.get_risk(&end.into()) as usize
        - map.get_risk(&Index(0, 0)) as usize;
}

pub fn gen_risk_lookup(map: &Map, end: Point) -> Result<Map, String> {
    if !map.in_bounds(&end) {
        return Err(format!("end point out of map bounds"));
    }

    let end = Node {
        point: end,
        tot_risk: 0,
    };

    let mut risk_lookup = Map {
        w: map.w,
        h: map.h,
        data: vec![1 << 32; map.data.len()],
    };

    let end_idx = risk_lookup.to_idx(end.point);
    risk_lookup.data[end_idx] = 0;

    let mut open: BinaryHeap<Node> = BinaryHeap::new();
    open.push(end);

    while let Some(curr) = open.pop() {
        for n in map.neighbours_pos(curr.point) {
            let n_risk = curr.tot_risk + map.get_risk(&n.into());

            if n_risk < risk_lookup.get_risk(&n.into()) {
                open.push(Node {
                    point: n,
                    tot_risk: n_risk,
                });
                risk_lookup.set(&n.into(), n_risk);
            }
        }
    }

    Ok(risk_lookup)
}