From add7534a2230149800a836a6a848f2143a5a5e2f Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Fri, 16 Dec 2022 05:07:14 -0500 Subject: day 16 --- benches/2022.rs | 5 + data/2022/16.txt | 57 +++++++++++ src/bin/2022/day16.rs | 274 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/bin/2022/main.rs | 2 + src/graph.rs | 30 ++++++ 5 files changed, 368 insertions(+) create mode 100644 data/2022/16.txt create mode 100644 src/bin/2022/day16.rs diff --git a/benches/2022.rs b/benches/2022.rs index 1bf0670..f6ebbc1 100644 --- a/benches/2022.rs +++ b/benches/2022.rs @@ -31,6 +31,8 @@ mod day13; mod day14; #[path = "../src/bin/2022/day15.rs"] mod day15; +#[path = "../src/bin/2022/day16.rs"] +mod day16; // NEXT MOD day!(2022, 1, day1); @@ -48,6 +50,7 @@ day!(2022, 12, day12); day!(2022, 13, day13); day!(2022, 14, day14); day!(2022, 15, day15); +day!(2022, 16, day16); // NEXT DAY fn bench_2022(c: &mut criterion::Criterion) { @@ -68,6 +71,7 @@ fn bench_2022(c: &mut criterion::Criterion) { day_combined!(2022, 13, day13); day_combined!(2022, 14, day14); day_combined!(2022, 15, day15); + day_combined!(2022, 16, day16); // NEXT DAY COMBINED }) }); @@ -91,5 +95,6 @@ criterion::criterion_main!( bench_2022day13, bench_2022day14, bench_2022day15, + bench_2022day16, // NEXT GROUP ); diff --git a/data/2022/16.txt b/data/2022/16.txt new file mode 100644 index 0000000..ca73ce3 --- /dev/null +++ b/data/2022/16.txt @@ -0,0 +1,57 @@ +Valve ED has flow rate=0; tunnels lead to valves PS, AW +Valve SI has flow rate=0; tunnels lead to valves AA, HX +Valve LX has flow rate=22; tunnels lead to valves DY, YH +Valve CR has flow rate=0; tunnels lead to valves BE, HX +Valve BI has flow rate=0; tunnels lead to valves GC, AY +Valve PB has flow rate=4; tunnels lead to valves IX, YG, RI, KR, BV +Valve YY has flow rate=0; tunnels lead to valves PH, GJ +Valve PH has flow rate=11; tunnels lead to valves YY, VE, ZG, MM +Valve DY has flow rate=0; tunnels lead to valves LX, AW +Valve SD has flow rate=0; tunnels lead to valves AY, EC +Valve SV has flow rate=24; tunnels lead to valves CC, GF +Valve RL has flow rate=0; tunnels lead to valves OW, IN +Valve GF has flow rate=0; tunnels lead to valves RQ, SV +Valve BE has flow rate=5; tunnels lead to valves CR, JC, MF, IT +Valve PR has flow rate=0; tunnels lead to valves BV, GJ +Valve AW has flow rate=21; tunnels lead to valves VE, DY, TR, ED +Valve FY has flow rate=17; tunnels lead to valves GG, KJ +Valve GC has flow rate=0; tunnels lead to valves BI, GJ +Valve RI has flow rate=0; tunnels lead to valves PB, AY +Valve RQ has flow rate=0; tunnels lead to valves HH, GF +Valve IT has flow rate=0; tunnels lead to valves MZ, BE +Valve XG has flow rate=0; tunnels lead to valves BL, AA +Valve MK has flow rate=0; tunnels lead to valves HX, DV +Valve IX has flow rate=0; tunnels lead to valves PB, JC +Valve BV has flow rate=0; tunnels lead to valves PR, PB +Valve TR has flow rate=0; tunnels lead to valves CD, AW +Valve PS has flow rate=0; tunnels lead to valves ED, AY +Valve HH has flow rate=12; tunnels lead to valves RQ, NL, ZQ +Valve AA has flow rate=0; tunnels lead to valves KR, SI, XG, EC, ZG +Valve FT has flow rate=0; tunnels lead to valves IN, YH +Valve YG has flow rate=0; tunnels lead to valves PB, HX +Valve HX has flow rate=14; tunnels lead to valves MK, ZQ, YG, SI, CR +Valve DV has flow rate=0; tunnels lead to valves MK, QR +Valve GJ has flow rate=3; tunnels lead to valves PR, CD, YY, GC, BL +Valve BL has flow rate=0; tunnels lead to valves GJ, XG +Valve CD has flow rate=0; tunnels lead to valves TR, GJ +Valve GG has flow rate=0; tunnels lead to valves FY, NL +Valve JC has flow rate=0; tunnels lead to valves IX, BE +Valve JN has flow rate=0; tunnels lead to valves OW, QR +Valve RM has flow rate=18; tunnel leads to valve KJ +Valve NL has flow rate=0; tunnels lead to valves GG, HH +Valve QR has flow rate=20; tunnels lead to valves CC, DV, PN, JN +Valve ZG has flow rate=0; tunnels lead to valves AA, PH +Valve AY has flow rate=6; tunnels lead to valves RI, PS, SD, BI, MM +Valve VE has flow rate=0; tunnels lead to valves PH, AW +Valve OW has flow rate=25; tunnels lead to valves MZ, RL, JN +Valve MM has flow rate=0; tunnels lead to valves AY, PH +Valve KJ has flow rate=0; tunnels lead to valves RM, FY +Valve MF has flow rate=0; tunnels lead to valves BE, PN +Valve YH has flow rate=0; tunnels lead to valves LX, FT +Valve ZQ has flow rate=0; tunnels lead to valves HX, HH +Valve KR has flow rate=0; tunnels lead to valves AA, PB +Valve PN has flow rate=0; tunnels lead to valves MF, QR +Valve CC has flow rate=0; tunnels lead to valves SV, QR +Valve MZ has flow rate=0; tunnels lead to valves OW, IT +Valve EC has flow rate=0; tunnels lead to valves SD, AA +Valve IN has flow rate=16; tunnels lead to valves RL, FT diff --git a/src/bin/2022/day16.rs b/src/bin/2022/day16.rs new file mode 100644 index 0000000..77ab621 --- /dev/null +++ b/src/bin/2022/day16.rs @@ -0,0 +1,274 @@ +#![allow(dead_code)] +#![allow(unused_variables)] + +use advent_of_code::prelude::*; + +#[derive(Debug)] +pub struct Map { + names: Vec, + connectivity: Vec>, + paths: Vec>, + flow: Vec, + pos: usize, + elephant: usize, +} + +impl advent_of_code::graph::Graph for Map { + type Edges = Vec; + + fn edges(&self, v: usize) -> Self::Edges { + self.connectivity[v].clone() + } + + fn edge(&self, v: usize, e: usize) -> (usize, u64) { + (e, 1) + } +} + +impl Map { + fn len(&self) -> usize { + self.flow.len() + } + + fn room(&self, elephant: bool) -> &str { + &self.names[self.pos(elephant)] + } + + fn can_stay(&self, elephant: bool) -> bool { + self.flow[self.pos(elephant)] > 0 + } + + fn done(&self) -> bool { + self.flow.iter().copied().all(|f| f == 0) + } + + fn pos(&self, elephant: bool) -> usize { + if elephant { + self.elephant + } else { + self.pos + } + } + + fn set_pos(&mut self, elephant: bool, pos: usize) { + if elephant { + self.elephant = pos; + } else { + self.pos = pos; + } + } + + fn flow(&self, elephant: bool) -> u16 { + self.flow[self.pos(elephant)] + } + + fn set_flow(&mut self, elephant: bool, flow: u16) { + let pos = self.pos(elephant); + self.flow[pos] = flow; + } + + fn neighbors(&self, elephant: bool) -> &[usize] { + &self.connectivity[self.pos(elephant)] + } +} + +pub fn parse(fh: File) -> Result { + let mut room_names = HashMap::new(); + let mut connectivity = vec![]; + let mut flow = vec![]; + let room_idx = |s, + room_names: &mut HashMap<_, _>, + connectivity: &mut Vec<_>, + flow: &mut Vec<_>| { + *room_names.entry(s).or_insert_with(|| { + connectivity.push(vec![]); + flow.push(0); + flow.len() - 1 + }) + }; + let mut pos = None; + for line in parse::raw_lines(fh) { + let cap = regex_captures!( + r"Valve ([^ ]+) has flow rate=(\d+); tunnels? leads? to valves? (.*)", + &line + ) + .ok_or_else(|| anyhow!("failed to parse"))?; + let node_name = cap[1].to_string(); + let node = room_idx( + node_name.clone(), + &mut room_names, + &mut connectivity, + &mut flow, + ); + if node_name == "AA" { + pos = Some(node); + } + flow[node] = cap[2].parse()?; + connectivity[node] = cap[3] + .split(", ") + .map(|s| { + room_idx( + s.to_string(), + &mut room_names, + &mut connectivity, + &mut flow, + ) + }) + .collect(); + } + let mut names = vec![]; + names.resize_with(flow.len(), Default::default); + for (name, idx) in room_names { + names[idx] = name; + } + let mut map = Map { + names, + connectivity, + paths: vec![], + flow, + pos: pos.unwrap(), + elephant: pos.unwrap(), + }; + for i in 0..map.connectivity.len() { + let mut paths = vec![0; map.connectivity.len()]; + let prevs = map.dijkstra_full(i); + for (from, (_, distance)) in map.dijkstra_full(i) { + paths[from] = distance; + } + map.paths.push(paths); + } + Ok(map) +} + +pub fn part1(mut map: Map) -> Result { + fn step(map: &mut Map, total: u64, time: u16) -> u64 { + if time >= 30 || map.done() { + return total; + } + + let mut max = 0; + if map.can_stay(false) { + let stay_value = map.flow(false) as u64 * (29 - time as u64); + let flow = map.flow(false); + map.set_flow(false, 0); + let value = step(map, total + stay_value, time + 1); + if value > max { + max = value; + } + map.set_flow(false, flow); + } else { + let pos = map.pos(false); + for idx in 0..map.len() { + if idx == pos || map.flow[idx] == 0 { + continue; + } + let distance = map.paths[pos][idx]; + map.set_pos(false, idx); + let value = step(map, total, time + distance as u16); + if value > max { + max = value; + } + map.set_pos(false, pos); + } + } + max + } + + Ok(step(&mut map, 0, 0)) +} + +pub fn part2(mut map: Map) -> Result { + fn step( + map: &mut Map, + elephant: bool, + total: u64, + time: u16, + transit: u64, + elephant_transit: u64, + ) -> u64 { + if time >= 26 || map.done() { + return total; + } + + if elephant { + let elephant_transit = elephant_transit.saturating_sub(1); + if elephant_transit > 0 { + return step( + map, + !elephant, + total, + if elephant { time + 1 } else { time }, + transit, + elephant_transit, + ); + } + } else { + let transit = transit.saturating_sub(1); + if transit > 0 { + return step( + map, + !elephant, + total, + if elephant { time + 1 } else { time }, + transit, + elephant_transit, + ); + } + } + + let mut max = 0; + if map.can_stay(elephant) { + let stay_value = map.flow(elephant) as u64 * (25 - time as u64); + let flow = map.flow(elephant); + map.set_flow(elephant, 0); + let value = step( + map, + !elephant, + total + stay_value, + if elephant { time + 1 } else { time }, + transit, + elephant_transit, + ); + if value > max { + max = value; + } + map.set_flow(elephant, flow); + } else { + let pos = map.pos(elephant); + for idx in 0..map.len() { + if idx == pos || map.flow[idx] == 0 { + continue; + } + let distance = map.paths[pos][idx]; + map.set_pos(elephant, idx); + let value = step( + map, + !elephant, + total, + if elephant { time + 1 } else { time }, + if elephant { transit } else { distance }, + if elephant { distance } else { elephant_transit }, + ); + if value > max { + max = value; + } + map.set_pos(elephant, pos); + } + } + max + } + + Ok(step(&mut map, false, 0, 0, 0, 0)) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2022, 16).unwrap()).unwrap()).unwrap(), + 2359 + ); + assert_eq!( + part2(parse(parse::data(2022, 16).unwrap()).unwrap()).unwrap(), + 2999 + ); +} diff --git a/src/bin/2022/main.rs b/src/bin/2022/main.rs index f295b53..dff9ae4 100644 --- a/src/bin/2022/main.rs +++ b/src/bin/2022/main.rs @@ -26,6 +26,7 @@ mod day12; mod day13; mod day14; mod day15; +mod day16; // NEXT MOD #[paw::main] @@ -47,6 +48,7 @@ fn main(opt: Opt) -> Result<()> { 13 => advent_of_code::day!(2022, opt.day, opt.puzzle, day13), 14 => advent_of_code::day!(2022, opt.day, opt.puzzle, day14), 15 => advent_of_code::day!(2022, opt.day, opt.puzzle, day15), + 16 => advent_of_code::day!(2022, opt.day, opt.puzzle, day16), // NEXT PART _ => panic!("unknown day {}", opt.day), } diff --git a/src/graph.rs b/src/graph.rs index 9312e7c..f8fbf3c 100644 --- a/src/graph.rs +++ b/src/graph.rs @@ -9,6 +9,36 @@ where fn edges(&self, v: Vertex) -> Self::Edges; fn edge(&self, v: Vertex, e: Edge) -> (Vertex, u64); + fn dijkstra_full(&self, start: Vertex) -> HashMap { + let mut to_visit = priority_queue::PriorityQueue::new(); + let mut prev = HashMap::new(); + prev.insert(start, (start, 0)); + to_visit.push(start, std::cmp::Reverse(0)); + while let Some((v, std::cmp::Reverse(distance))) = to_visit.pop() { + for e in self.edges(v) { + let (next, weight) = self.edge(v, e); + let visited = prev.contains_key(&next); + let new_distance = distance + weight; + if to_visit.get(&next).is_some() { + prev.insert(next, (v, new_distance)); + if new_distance < to_visit.get_priority(&next).unwrap().0 + { + to_visit.change_priority( + &next, + std::cmp::Reverse(new_distance), + ); + } + } else { + if !visited { + prev.insert(next, (v, new_distance)); + to_visit.push(next, std::cmp::Reverse(new_distance)); + } + } + } + } + prev + } + fn dijkstra bool>( &self, start: Vertex, -- cgit v1.2.3-54-g00ecf