From 25a0973c66ad916029a277e57c506cf39cfde096 Mon Sep 17 00:00:00 2001
From: tomsmeding <tom.smeding@gmail.com>
Date: Sat, 22 Dec 2018 11:43:22 +0100
Subject: Day 22
---
2018/input/22.txt | 2 +
2018/src/day22.rs | 138 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
2018/src/main.rs | 4 +-
3 files changed, 143 insertions(+), 1 deletion(-)
create mode 100644 2018/input/22.txt
create mode 100644 2018/src/day22.rs
diff --git a/2018/input/22.txt b/2018/input/22.txt
new file mode 100644
index 0000000..485426c
--- /dev/null
+++ b/2018/input/22.txt
@@ -0,0 +1,2 @@
+depth: 8103
+target: 9,758
diff --git a/2018/src/day22.rs b/2018/src/day22.rs
new file mode 100644
index 0000000..497498b
--- /dev/null
+++ b/2018/src/day22.rs
@@ -0,0 +1,138 @@
+use std::io;
+use std::io::BufRead;
+use std::collections::BinaryHeap;
+use std::collections::HashSet;
+
+const MOD: usize = 20183;
+
+pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
+ let mut lines = reader.lines();
+ let depth: usize = lines.next().unwrap().unwrap().split(' ').skip(1).next().unwrap().parse().unwrap();
+ let target: (usize, usize) = {
+ let line = lines.next().unwrap().unwrap();
+ let mut iter = line.split(' ').skip(1).next().unwrap().split(',');
+ let x = iter.next().unwrap().parse().unwrap();
+ let y = iter.next().unwrap().parse().unwrap();
+ (x, y)
+ };
+
+ // I believe the route can never go beyond target / 2 * 7 from the entrance, but
+ // I don't trust the factor 2 and I don't want to deal with rounding issues.
+ let w = 8 * target.0;
+ let h = 8 * target.1;
+
+ let terrain = {
+ let mut erosion = vec![0; w * h];
+
+ for x in 0..w {
+ erosion[x] = (16807 * x + depth) % MOD;
+ }
+
+ for y in 1..h {
+ erosion[w*y] = (48271 * y + depth) % MOD;
+ }
+
+ for y in 1..h {
+ for x in 1..w {
+ if x == target.0 && y == target.1 {
+ erosion[w*y+x] = depth % MOD;
+ } else {
+ erosion[w*y+x] = (erosion[w*y+x-1] * erosion[w*(y-1)+x] + depth) % MOD;
+ }
+ }
+ }
+
+ erosion.iter().map(|val| val % 3).collect::<Vec<_>>()
+ };
+
+ let part1 = {
+ let mut total_risk = 0;
+ for y in 0..target.1+1 {
+ for x in 0..target.0+1 {
+ total_risk += terrain[w*y+x];
+ }
+ }
+ total_risk
+ };
+
+ let w = w as isize;
+ let h = h as isize;
+
+ // terrain = {0 = rocky, 1 = wet, 2 = narrow}
+ // tool = {0 = neither, 1 = torch, 2 = climbing gear}
+
+ let can_traverse = |tool, (x, y)| x >= 0 && y >= 0 && match terrain[(w*y+x) as usize] {
+ 0 => tool >= 1,
+ 1 => tool != 1,
+ 2 => tool != 2,
+ _ => unreachable!(),
+ };
+ let neighbours = |(x, y)| [(x-1, y), (x, y-1), (x+1, y), (x, y+1)];
+
+ // for &pt in neighbours((0, 0)).iter().filter(|&&pt| can_traverse(0, pt)) {
+ // println!("{:?}", pt);
+ // }
+
+ let mut pqu = BinaryHeap::new();
+ pqu.push((-0, 1, 0, 0));
+
+ let mut distmap = vec![isize::max_value(); (3 * w * h) as usize]; // w*h*tool + w*y + x
+ distmap[(w*h*1 + w*0 + 0) as usize] = 0;
+
+ // let mut parent = vec![(-1, -1, -1); (3 * w * h) as usize];
+
+ let mut seen = HashSet::new();
+
+ let part2;
+
+ loop {
+ let (mdist, tool, x, y) = match pqu.pop() {
+ Some(val) => val,
+ None => panic!("Pqu empty!"),
+ };
+ let dist = -mdist;
+
+ if seen.contains(&(tool, x, y)) {
+ continue;
+ }
+
+ seen.insert((tool, x, y));
+
+ // println!("Expanding dist={} tool={} pos={:?}", dist, tool, (x, y));
+
+ if tool == 1 && x == target.0 as isize && y == target.1 as isize {
+ part2 = dist;
+
+ /* println!("Path:");
+ let mut at = (tool, x, y);
+ while at.0 != -1 {
+ println!(" tool={} pos=({}, {})", at.0, at.1, at.2);
+ at = parent[(w*h*at.0 + w*at.2 + at.1) as usize];
+ } */
+
+ break;
+ }
+
+ distmap[(w*h*tool + w*y + x) as usize] = dist;
+
+ for &pt in neighbours((x, y)).iter().filter(|&&pt| can_traverse(tool, pt)) {
+ if dist + 1 < distmap[(w*h*tool + w*pt.1 + pt.0) as usize] {
+ pqu.push((-(dist + 1), tool, pt.0, pt.1));
+ distmap[(w*h*tool + w*pt.1 + pt.0) as usize] = dist + 1;
+ // parent[(w*h*tool + w*pt.1 + pt.0) as usize] = (tool, x, y);
+ }
+ }
+
+ for t in 0..3 {
+ if t == tool { continue; }
+ if !can_traverse(t, (x, y)) { continue; }
+ if dist + 7 < distmap[(w*h*t + w*y + x) as usize] {
+ pqu.push((-(dist + 7), t, x, y));
+ distmap[(w*h*t + w*y + x) as usize] = dist + 7;
+ // parent[(w*h*t + w*y + x) as usize] = (tool, x, y);
+ }
+ }
+ }
+
+ Ok((part1.to_string(), part2.to_string()))
+}
diff --git a/2018/src/main.rs b/2018/src/main.rs
index fa1cab8..c45b084 100644
--- a/2018/src/main.rs
+++ b/2018/src/main.rs
@@ -27,8 +27,9 @@ mod day18;
mod day19;
mod day20;
mod day21;
+mod day22;
-static NUM_DAYS: i32 = 21;
+static NUM_DAYS: i32 = 22;
fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> {
match day {
@@ -53,6 +54,7 @@ fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> {
19 => day19::main(reader),
20 => day20::main(reader),
21 => day21::main(reader),
+ 22 => day22::main(reader),
_ => Err(Error::new(ErrorKind::Other, "Invalid day"))
}
}
--
cgit v1.2.3-70-g09d2