diff options
-rw-r--r-- | 2022/inputs/day_16.txt | 58 | ||||
-rw-r--r-- | 2022/src/bin/day_16.rs | 236 |
2 files changed, 294 insertions, 0 deletions
diff --git a/2022/inputs/day_16.txt b/2022/inputs/day_16.txt new file mode 100644 index 0000000..2ab3e62 --- /dev/null +++ b/2022/inputs/day_16.txt @@ -0,0 +1,58 @@ +Valve QZ has flow rate=0; tunnels lead to valves IR, FA +Valve FV has flow rate=0; tunnels lead to valves AA, GZ +Valve GZ has flow rate=0; tunnels lead to valves FV, PO +Valve QL has flow rate=0; tunnels lead to valves MR, AA +Valve AA has flow rate=0; tunnels lead to valves QL, GQ, EV, FV +Valve SQ has flow rate=23; tunnel leads to valve ZG +Valve PK has flow rate=8; tunnels lead to valves MN, GN, WF, TY, CX +Valve GQ has flow rate=0; tunnels lead to valves AA, MT +Valve TI has flow rate=22; tunnels lead to valves GM, CS +Valve JU has flow rate=17; tunnels lead to valves TT, RR, UJ, JY +Valve YD has flow rate=7; tunnels lead to valves AT, ZS, BS +Valve YB has flow rate=0; tunnels lead to valves EA, MW +Valve FA has flow rate=0; tunnels lead to valves QZ, JT +Valve TN has flow rate=0; tunnels lead to valves ZS, PO +Valve MW has flow rate=0; tunnels lead to valves YB, YL +Valve XN has flow rate=0; tunnels lead to valves VL, VM +Valve MN has flow rate=0; tunnels lead to valves PK, TT +Valve IP has flow rate=9; tunnels lead to valves YC, SA, CH, PI +Valve PD has flow rate=0; tunnels lead to valves YZ, VM +Valve ZS has flow rate=0; tunnels lead to valves TN, YD +Valve PC has flow rate=0; tunnels lead to valves MR, XT +Valve VM has flow rate=13; tunnels lead to valves CX, XN, PD +Valve PO has flow rate=4; tunnels lead to valves GZ, TN, SA, XT, BM +Valve GN has flow rate=0; tunnels lead to valves PK, YL +Valve YL has flow rate=5; tunnels lead to valves MT, YZ, GN, SU, MW +Valve IR has flow rate=6; tunnels lead to valves LK, PI, BM, QZ, EV +Valve GM has flow rate=0; tunnels lead to valves TI, RH +Valve CS has flow rate=0; tunnels lead to valves UJ, TI +Valve EA has flow rate=18; tunnels lead to valves VL, YB, WF, JY +Valve LK has flow rate=0; tunnels lead to valves IR, MR +Valve BM has flow rate=0; tunnels lead to valves IR, PO +Valve JZ has flow rate=0; tunnels lead to valves RH, RR +Valve SA has flow rate=0; tunnels lead to valves IP, PO +Valve XT has flow rate=0; tunnels lead to valves PO, PC +Valve YC has flow rate=0; tunnels lead to valves IP, IL +Valve RH has flow rate=15; tunnels lead to valves WJ, JZ, GM +Valve CH has flow rate=0; tunnels lead to valves IP, BS +Valve JY has flow rate=0; tunnels lead to valves EA, JU +Valve TY has flow rate=0; tunnels lead to valves WJ, PK +Valve WJ has flow rate=0; tunnels lead to valves TY, RH +Valve IL has flow rate=0; tunnels lead to valves YC, MR +Valve BS has flow rate=0; tunnels lead to valves YD, CH +Valve AT has flow rate=0; tunnels lead to valves YD, UX +Valve UJ has flow rate=0; tunnels lead to valves CS, JU +Valve VL has flow rate=0; tunnels lead to valves EA, XN +Valve JT has flow rate=21; tunnels lead to valves ZG, FA +Valve UX has flow rate=10; tunnel leads to valve AT +Valve RR has flow rate=0; tunnels lead to valves JZ, JU +Valve TT has flow rate=0; tunnels lead to valves JU, MN +Valve MT has flow rate=0; tunnels lead to valves GQ, YL +Valve EV has flow rate=0; tunnels lead to valves AA, IR +Valve ZG has flow rate=0; tunnels lead to valves JT, SQ +Valve WF has flow rate=0; tunnels lead to valves EA, PK +Valve YZ has flow rate=0; tunnels lead to valves PD, YL +Valve MR has flow rate=3; tunnels lead to valves LK, IL, QL, SU, PC +Valve PI has flow rate=0; tunnels lead to valves IR, IP +Valve CX has flow rate=0; tunnels lead to valves VM, PK +Valve SU has flow rate=0; tunnels lead to valves YL, MR diff --git a/2022/src/bin/day_16.rs b/2022/src/bin/day_16.rs new file mode 100644 index 0000000..e35f04e --- /dev/null +++ b/2022/src/bin/day_16.rs @@ -0,0 +1,236 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{alpha1, line_ending, u32}, + combinator::map, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::{ + collections::{BTreeMap, BTreeSet}, + fs, +}; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_16.txt")?; + let nodes = Nodes::parser(&input).unwrap().1; + let mut condensed = nodes.condense(); + + let mut initial_open_valves = BTreeSet::new(); + initial_open_valves.insert(0); + + let initial_state = State { + actors: vec![Actor { + position: 0, + time_remaining: 30, + }], + open_valves: initial_open_valves.clone(), + }; + + dbg!(condensed.find_optimal_pressure_relieved(&initial_state)); + + let initial_state_with_elephant = State { + actors: vec![ + Actor { + position: 0, + time_remaining: 26 + }; + 2 + ], + open_valves: initial_open_valves, + }; + dbg!(condensed.find_optimal_pressure_relieved(&initial_state_with_elephant)); + + Ok(()) +} + +#[derive(Debug, Clone)] +struct Nodes { + nodes: BTreeMap<String, Node>, +} + +#[derive(Debug, Clone)] +struct Node { + id: String, + flow_rate: u32, + exits: BTreeMap<String, u32>, +} + +#[derive(Debug)] +struct CondensedNodes { + nodes: Vec<CondensedNode>, + cache: BTreeMap<State, u32>, +} + +#[derive(Debug, Clone)] +struct CondensedNode { + flow_rate: u32, + exits: Vec<u32>, +} + +impl Nodes { + fn parser(input: &str) -> IResult<&str, Self> { + map(separated_list1(line_ending, Node::parser), |nodes| Nodes { + nodes: nodes + .into_iter() + .map(|node| (node.id.clone(), node)) + .collect(), + })(input) + } + + fn condense(&self) -> CondensedNodes { + let node_ids: Vec<String> = self + .nodes + .values() + .filter(|n| n.id == "AA" || n.flow_rate > 0) + .map(|n| n.id.clone()) + .collect(); + + let mut condensed = CondensedNodes { + nodes: self + .nodes + .values() + .filter(|n| n.id == "AA" || n.flow_rate > 0) + .map(|n| CondensedNode { + flow_rate: n.flow_rate, + exits: Vec::new(), + }) + .collect(), + cache: BTreeMap::new(), + }; + + for (id, mut node) in condensed.nodes.iter_mut().enumerate() { + node.exits = node_ids + .iter() + .map(|original_destination_id| { + // +1 because in condensed it includes opening the valve + self.find_shortest_path(&node_ids[id], &original_destination_id) + 1 + }) + .collect() + } + + condensed + } + + fn find_shortest_path(&self, from: &str, to: &str) -> u32 { + let mut frontier: BTreeSet<&str> = BTreeSet::new(); + let mut explored: BTreeSet<&str> = BTreeSet::new(); + let mut distance = 0; + + explored.insert(from); + frontier.insert(from); + + while !frontier.is_empty() { + let mut next_frontier: BTreeSet<&str> = BTreeSet::new(); + distance += 1; + + for frontier_point in frontier { + for adjacent_point in self.nodes.get(frontier_point).unwrap().exits.keys() { + if adjacent_point == to { + return distance; + } + if !explored.contains(&adjacent_point.as_ref()) { + explored.insert(adjacent_point); + next_frontier.insert(adjacent_point); + } + } + } + + frontier = next_frontier; + } + panic!("Didn't reach end"); + } +} + +impl Node { + fn parser(input: &str) -> IResult<&str, Self> { + map( + tuple(( + tag("Valve "), + alpha1, + tag(" has flow rate="), + u32, + alt(( + tag("; tunnels lead to valves "), + tag("; tunnel leads to valve "), + )), + separated_list1(tag(", "), alpha1), + )), + |(_, id, _, flow_rate, _, exits): (_, &str, _, u32, _, Vec<&str>)| Node { + id: id.to_owned(), + flow_rate, + exits: exits + .into_iter() + .map(|destination| (destination.to_owned(), 1)) + .collect(), + }, + )(input) + } +} + +#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct State { + actors: Vec<Actor>, + open_valves: BTreeSet<usize>, +} + +#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct Actor { + position: usize, + time_remaining: u32, +} + +impl State { + fn sort_actors(&mut self) { + self.actors.sort() + } +} + +impl CondensedNodes { + fn find_optimal_pressure_relieved(&mut self, state: &State) -> u32 { + let cache_value = self.cache.get(state); + if let Some(cache_value) = cache_value { + return *cache_value; + } + + let mut computed_value = 0; + for (actor_i, actor) in state.actors.iter().enumerate() { + let exits_to_investigate: Vec<(usize, u32)> = self.nodes[actor.position] + .exits + .iter() + .enumerate() + .filter(|(destination, distance)| { + !state.open_valves.contains(destination) && **distance <= actor.time_remaining + }) + .map(|(destination, distance)| (destination.clone(), distance.clone())) + .collect(); + + for (destination, distance) in exits_to_investigate { + let mut open_valves = state.open_valves.clone(); + open_valves.insert(destination.clone()); + let new_actor = Actor { + time_remaining: actor.time_remaining - distance, + position: destination.clone(), + }; + let relief_from_this_valve = + self.nodes[destination].flow_rate * new_actor.time_remaining as u32; + let mut actors = state.actors.clone(); + actors[actor_i] = new_actor; + + let mut state_this_way = State { + actors, + open_valves, + }; + state_this_way.sort_actors(); + + let recursive_relief = self.find_optimal_pressure_relieved(&state_this_way); + let relief = relief_from_this_valve + recursive_relief; + computed_value = computed_value.max(relief); + } + } + + self.cache.insert(state.clone(), computed_value); + computed_value + } +} |