Skip to content

Instantly share code, notes, and snippets.

@tinaun
Created December 23, 2018 02:59
Show Gist options
  • Save tinaun/79aaf405c3d5558ccf11f8a5b848fe02 to your computer and use it in GitHub Desktop.
Save tinaun/79aaf405c3d5558ccf11f8a5b848fe02 to your computer and use it in GitHub Desktop.
#![allow(unused)]
mod prelude;
use self::prelude::*;
const DEPTH: usize = 8787;
const TARGET: (usize, usize) = (10, 725);
fn geo_index(x: usize, y: usize, world: &mut Map<(usize, usize), usize>) -> usize {
if let Some(&value) = world.get(&(x,y)) {
return value;
}
let value = if (x, y) == (0, 0) {
0
} else if (x, y) == TARGET {
0
} else if x == 0 {
y * 48271
} else if y == 0 {
x * 16807
} else {
erosion_level(x-1, y, world) * erosion_level(x, y - 1, world)
};
world.insert((x, y), value);
value
}
fn erosion_level(x: usize, y: usize, world: &mut Map<(usize, usize), usize>) -> usize {
(geo_index(x, y, world) + DEPTH) % 20183
}
#[derive(Copy, Clone, Debug, PartialEq)]
enum Cave {
Rocky,
Wet,
Narrow,
}
#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
enum Tool {
Gear,
Torch,
None,
}
fn man_dist(a: (usize, usize), b: (usize, usize)) -> usize {
let man = (a.0 as isize - b.0 as isize).abs() + (a.1 as isize - b.1 as isize).abs();
man as usize
}
pub fn advent() -> (impl Debug, impl Debug) {
let demo = include_str!("../demo.txt");
let input = include_str!("../input.txt");
let mut p1 = 0;
let mut p2 = 0;
let mut world = Map::new();
for y in 0..=TARGET.1 {
for x in 0..=TARGET.0 {
let ero = (geo_index(x, y, &mut world) + DEPTH) % 20183;
p1 += ero % 3;
}
}
let mut cave_system = vec![Cave::Rocky; 1000 * 1000];
for y in 0..1000 {
for x in 0..1000 {
let ero = (geo_index(x, y, &mut world) + DEPTH) % 20183;
cave_system[y * 1000 + x] = match ero % 3 {
1 => Cave::Wet,
2 => Cave::Narrow,
_ => {
continue;
},
};
}
}
println!("starting path");
let mut visited = Map::new();
let mut dist = Map::new();
dist.insert((0, 0, Tool::Torch), 0);
let mut current = (0, 0, Tool::Torch);
while !visited.contains_key(&(TARGET.0, TARGET.1, Tool::Torch)) ||
!visited.contains_key(&(TARGET.0, TARGET.1, Tool::Gear)) {
//dbg!(current);
let (x, y, tool) = current;
let mut possible_nodes = vec![(x + 1, y), (x, y+1)];
if x > 0 {
possible_nodes.push((x - 1, y));
}
if y > 0 {
possible_nodes.push((x, y - 1));
}
let base = *dist.get(&current).unwrap();
for node in possible_nodes {
if !visited.contains_key(&(node.0, node.1, tool)) {
let next_cave = cave_system[node.1 * 1000 + node.0];
let prev_cave = cave_system[y * 1000 + x];
let next_tool = match (prev_cave, next_cave) {
(Cave::Rocky, Cave::Wet) => Tool::Gear,
(Cave::Wet, Cave::Rocky) => Tool::Gear,
(Cave::Rocky, Cave::Narrow) => Tool::Torch,
(Cave::Narrow, Cave::Rocky) => Tool::Torch,
(Cave::Narrow, Cave::Wet) => Tool::None,
(Cave::Wet, Cave::Narrow) => Tool::None,
_ => tool,
};
let dv = if tool == next_tool {
1
} else {
8
};
let entry = dist.entry((node.0, node.1, next_tool)).or_insert((base + dv));
if *entry > base + dv {
*entry = base + dv;
}
}
}
visited.insert(current, (base, tool));
dist.remove(&current);
current = *dist.iter().min_by_key(|(k, &v)| v + man_dist((k.0, k.1), TARGET)).unwrap().0;
}
let (mut p2, tool) = visited.get(&(TARGET.0, TARGET.1, Tool::Torch)).unwrap();
if *tool != Tool::Torch {
p2 += 7;
}
(p1, p2)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment