Day 22

3 files changed, 143 insertions, 1 deletions

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"))
     }
 }