From 8bd6463a93520ddc7d4d1af110db1989d156a84a Mon Sep 17 00:00:00 2001 From: Greg Burri Date: Fri, 16 Dec 2022 16:04:32 +0100 Subject: [PATCH] Day 16 part 1 --- data/day16.input | 55 ++++++++++++++++++ src/day16.rs | 143 +++++++++++++++++++++++++++++++++++++++++++++++ src/days.rs | 9 +++ src/main.rs | 2 + 4 files changed, 209 insertions(+) create mode 100644 data/day16.input create mode 100644 src/day16.rs diff --git a/data/day16.input b/data/day16.input new file mode 100644 index 0000000..79c2b81 --- /dev/null +++ b/data/day16.input @@ -0,0 +1,55 @@ +Valve SW has flow rate=0; tunnels lead to valves LX, LD +Valve VS has flow rate=0; tunnels lead to valves JO, OO +Valve OO has flow rate=10; tunnels lead to valves KK, HD, VS, KI +Valve DZ has flow rate=8; tunnels lead to valves KV, GX, WQ, BA, PK +Valve GX has flow rate=0; tunnels lead to valves AA, DZ +Valve IF has flow rate=0; tunnels lead to valves OI, DW +Valve BO has flow rate=0; tunnels lead to valves UJ, ZT +Valve KI has flow rate=0; tunnels lead to valves OO, KU +Valve JT has flow rate=3; tunnels lead to valves FC, AM, KV, XP, XZ +Valve TQ has flow rate=0; tunnels lead to valves AA, DW +Valve KK has flow rate=0; tunnels lead to valves QW, OO +Valve NR has flow rate=0; tunnels lead to valves UG, XM +Valve VO has flow rate=0; tunnels lead to valves YR, AA +Valve MS has flow rate=17; tunnels lead to valves LT, LX +Valve JO has flow rate=0; tunnels lead to valves YR, VS +Valve ZB has flow rate=0; tunnels lead to valves UJ, LT +Valve ZT has flow rate=0; tunnels lead to valves XM, BO +Valve YR has flow rate=9; tunnels lead to valves VO, FY, WB, JO +Valve QS has flow rate=0; tunnels lead to valves QW, FY +Valve UD has flow rate=0; tunnels lead to valves CA, JB +Valve AP has flow rate=0; tunnels lead to valves CA, DW +Valve KV has flow rate=0; tunnels lead to valves JT, DZ +Valve JH has flow rate=0; tunnels lead to valves IK, UJ +Valve LD has flow rate=15; tunnels lead to valves IK, SW +Valve XK has flow rate=0; tunnels lead to valves XZ, BH +Valve XM has flow rate=11; tunnels lead to valves XP, CJ, ZT, NR +Valve FY has flow rate=0; tunnels lead to valves YR, QS +Valve GI has flow rate=22; tunnel leads to valve TI +Valve JB has flow rate=14; tunnels lead to valves WB, UD, WQ, HD +Valve DW has flow rate=6; tunnels lead to valves AP, TQ, NQ, IF, PK +Valve UJ has flow rate=13; tunnels lead to valves JH, ZB, BO +Valve KU has flow rate=0; tunnels lead to valves CA, KI +Valve WQ has flow rate=0; tunnels lead to valves JB, DZ +Valve BA has flow rate=0; tunnels lead to valves BH, DZ +Valve AA has flow rate=0; tunnels lead to valves YX, TQ, VO, GX, QP +Valve TI has flow rate=0; tunnels lead to valves GI, UG +Valve FC has flow rate=0; tunnels lead to valves QP, JT +Valve CA has flow rate=18; tunnels lead to valves KU, UD, AP +Valve QW has flow rate=25; tunnels lead to valves QS, KK +Valve XZ has flow rate=0; tunnels lead to valves JT, XK +Valve YX has flow rate=0; tunnels lead to valves AA, CJ +Valve OI has flow rate=0; tunnels lead to valves IF, BH +Valve NQ has flow rate=0; tunnels lead to valves AM, DW +Valve QP has flow rate=0; tunnels lead to valves AA, FC +Valve AM has flow rate=0; tunnels lead to valves NQ, JT +Valve XP has flow rate=0; tunnels lead to valves XM, JT +Valve BH has flow rate=12; tunnels lead to valves BA, XK, OI +Valve HD has flow rate=0; tunnels lead to valves OO, JB +Valve LT has flow rate=0; tunnels lead to valves MS, ZB +Valve LX has flow rate=0; tunnels lead to valves MS, SW +Valve CJ has flow rate=0; tunnels lead to valves XM, YX +Valve PK has flow rate=0; tunnels lead to valves DW, DZ +Valve IK has flow rate=0; tunnels lead to valves LD, JH +Valve WB has flow rate=0; tunnels lead to valves YR, JB +Valve UG has flow rate=21; tunnels lead to valves TI, NR \ No newline at end of file diff --git a/src/day16.rs b/src/day16.rs new file mode 100644 index 0000000..ae2920f --- /dev/null +++ b/src/day16.rs @@ -0,0 +1,143 @@ +use std::collections::HashMap; + +use itertools::Itertools; +use regex::{self, Regex}; + +#[derive(Debug)] +pub struct Valve { + neighbours: Vec, + flow: i32, +} + +pub fn parse(input: &str) -> (i32, Vec) { + let regex = + Regex::new(r"Valve (\w{2}) has flow rate=(\d+); tunnels? leads? to valves? (.+)").unwrap(); + + let mut valve_aa = 0; + + let mut names = HashMap::::new(); + let lines = input + .lines() + .enumerate() + .map(|(i, l)| { + let captures = regex.captures(l).unwrap(); + let i = i as i32; + + if &captures[1] == "AA" { + valve_aa = i; + } + + names.insert(captures[1].to_string(), i); + + ( + captures[2].parse::().unwrap(), + captures[3] + .split(", ") + .map(str::to_string) + .collect::>(), + ) + }) + .collect_vec(); + + let mut valves = Vec::new(); + + for (flow, neigbours) in lines { + valves.push(Valve { + neighbours: neigbours.iter().map(|n| names[n]).collect(), + flow, + }); + } + + (valve_aa, valves) +} + +pub fn most_pressure(start: i32, time: i32, valves: &[Valve]) -> i32 { + let n = valves.len(); + let mut times_tables = vec![vec![0; n]; n]; + for i in 0..valves.len() { + let mut visited = vec![false; n]; + let mut to_visit = Vec::new(); + let mut next_to_visit = vec![i as i32]; + let mut l = 0; + while !next_to_visit.is_empty() { + std::mem::swap(&mut to_visit, &mut next_to_visit); + while let Some(n) = to_visit.pop() { + if !visited[n as usize] { + visited[n as usize] = true; + times_tables[i as usize][n as usize] = l; + next_to_visit.extend_from_slice(&valves[n as usize].neighbours) + } + } + l += 1; + } + } + + let non_broken_valves: Vec = valves + .iter() + .enumerate() + .filter_map(|(i, v)| if v.flow > 0 { Some(i as i32) } else { None }) + .collect(); + + fn best_score( + time_left: i32, + current_path: Vec, + non_broken_valves: &[i32], + times_tables: &[Vec], + valves: &[Valve], + ) -> i32 { + non_broken_valves + .iter() + .map(|v| { + if !current_path.contains(v) { + let time = times_tables[*current_path.last().unwrap() as usize][*v as usize]; + // -1 is the time to open the valve. + let time_left_after_v = time_left - time - 1; + if time_left_after_v > 0 { + let mut path_cloned = current_path.clone(); + path_cloned.push(*v); + time_left_after_v * valves[*v as usize].flow + + best_score( + time_left_after_v, + path_cloned, + non_broken_valves, + times_tables, + valves, + ) + } else { + 0 + } + } else { + 0 + } + }) + .max() + .unwrap() + } + + best_score(time, vec![start], &non_broken_valves, ×_tables, valves) +} + +#[cfg(test)] +mod tests { + use super::*; + + static VALVES: &str = "Valve AA has flow rate=0; tunnels lead to valves DD, II, BB + Valve BB has flow rate=13; tunnels lead to valves CC, AA + Valve CC has flow rate=2; tunnels lead to valves DD, BB + Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE + Valve EE has flow rate=3; tunnels lead to valves FF, DD + Valve FF has flow rate=0; tunnels lead to valves EE, GG + Valve GG has flow rate=0; tunnels lead to valves FF, HH + Valve HH has flow rate=22; tunnel leads to valve GG + Valve II has flow rate=0; tunnels lead to valves AA, JJ + Valve JJ has flow rate=21; tunnel leads to valve II"; + + #[test] + fn part1() { + let (start, valves) = parse(VALVES); + assert_eq!(most_pressure(start, 30, &valves), 1651); + } + + #[test] + fn part2() {} +} diff --git a/src/days.rs b/src/days.rs index 45a6b9b..3168dea 100644 --- a/src/days.rs +++ b/src/days.rs @@ -160,3 +160,12 @@ pub fn day15() -> String { day15::tuning_frequency(&sensors, 4_000_000) ) } + +pub fn day16() -> String { + let (start, valves) = day16::parse(&fs::read_to_string("data/day16.input").unwrap()); + format!( + "part1: {}, part2: {}", + day16::most_pressure(start, 30, &valves), + 0 + ) +} diff --git a/src/main.rs b/src/main.rs index c56644b..1086131 100644 --- a/src/main.rs +++ b/src/main.rs @@ -18,6 +18,7 @@ mod day12; mod day13; mod day14; mod day15; +mod day16; mod days; #[derive(Parser, Debug)] @@ -49,6 +50,7 @@ fn main() { days::day13, days::day14, days::day15, + days::day16, ]; let args = Args::parse(); -- 2.45.2