From 25a0973c66ad916029a277e57c506cf39cfde096 Mon Sep 17 00:00:00 2001 From: tomsmeding 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(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::>() + }; + + 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(day: i32, reader: T) -> io::Result<(String, String)> { match day { @@ -53,6 +54,7 @@ fn day_switch(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