Skip to content

Instantly share code, notes, and snippets.

@Refsa
Created December 16, 2021 12:16
Show Gist options
  • Save Refsa/66eacc2ef9750ebac033822356b146e5 to your computer and use it in GitHub Desktop.
Save Refsa/66eacc2ef9750ebac033822356b146e5 to your computer and use it in GitHub Desktop.
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)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment