use std::collections::{HashSet, VecDeque}; #[derive(Clone, Debug, PartialEq)] struct Floor<'a> { generators: HashSet<&'a str>, microchips: HashSet<&'a str>, } #[derive(Clone, Debug, PartialEq)] struct State<'a> { // Elevator's current location (index into `floors') elevator: usize, // Generators and microchips on each floor floors: [Floor<'a>; 4], } impl<'a> State<'a> { // We need to serialize states into a hashable type // to get O(1) membership tests in the history log. // `HashSet' isn't hashable, so no `Hash' trait here. fn serialize(&self) -> String { let mut result = format!("{} ", self.elevator); for f in &self.floors { let mut gkeys: Vec<&&str> = f.generators.iter().collect(); gkeys.sort(); for gk in gkeys { result.push_str(gk); } result.push(' '); let mut mkeys: Vec<&&str> = f.microchips.iter().collect(); mkeys.sort(); for mk in mkeys { result.push_str(mk); } result.push(','); } result } } fn solve_puzzle(start: State) -> usize { let mut visited = HashSet::from([start.serialize()]); // O(1) `contains()' let mut queue = VecDeque::from([(start, 0)]); // Breadth-first search of the state space, where nodes are legal states // and edges are legal moves. The space is large, so this takes a minute. loop { let (state, depth) = queue.pop_front().unwrap(); // Abbreviation for current floor let ce = state.elevator; let cf = &state.floors[ce]; // End condition: are all floors empty, except the top one? if state.elevator == 3 { let mut others_empty = true; for f in &state.floors[0..3] { others_empty &= f.generators.len() == 0 && f.microchips.len() == 0; } if others_empty { return depth; } } // Generate item choices to take into elevator for next step let mut choices = Vec::new(); for &g1 in &cf.generators { // Pick one generator `g1' choices.push(Floor { generators: HashSet::from([g1]), microchips: HashSet::new(), }); // Pick two generators `g1' and `g2' for &g2 in &cf.generators { choices.push(Floor { generators: HashSet::from([g1, g2]), microchips: HashSet::new(), }); } // Pick one generator `g1' and one microchip `m1' for &m1 in &cf.microchips { choices.push(Floor { generators: HashSet::from([g1]), microchips: HashSet::from([m1]), }); } } for &m1 in &cf.microchips { // Pick one microchip `m1' choices.push(Floor { generators: HashSet::new(), microchips: HashSet::from([m1]), }); // Pick two microchips `m1' and `m2' for &m2 in &cf.microchips { choices.push(Floor { generators: HashSet::new(), microchips: HashSet::from([m1, m2]), }); } } // Possible next locations of elevator (one floor up or down) let mut new_elevs = Vec::new(); if state.elevator < 3 { new_elevs.push(state.elevator + 1); } if state.elevator > 0 { new_elevs.push(state.elevator - 1); } let mut candidates = Vec::new(); 'choices: for choice in choices { // If we picked one generator and one microchip, they must be compatible. // The puzzle description is actually unclear on if this is a legal move, // i.e. is the elevator ride long enough to fry an incompatible chip? // I assumed yes, and got the right answer, so... if choice.generators.len() == 1 && choice.microchips.len() == 1 { for m in &choice.microchips { // runs once if !choice.generators.contains(m) { continue 'choices; } } } // Convert `choice' into `candidates' for new states for &ne in &new_elevs { let mut cand = state.clone(); cand.elevator = ne; for g in &choice.generators { cand.floors[ce].generators.remove(g); cand.floors[ne].generators.insert(g); } for m in &choice.microchips { cand.floors[ce].microchips.remove(m); cand.floors[ne].microchips.insert(m); } // Check if this new state is allowed let mut is_legal = true; // Do we leave behing the old/current floor in a valid configuration? if cand.floors[ce].generators.len() > 0 { for m in &cand.floors[ce].microchips { if !cand.floors[ce].generators.contains(m) { is_legal = false; break; } } } // Will the new floor be in a valid configuration? if cand.floors[ne].generators.len() > 0 { for m in &cand.floors[ne].microchips { if !cand.floors[ne].generators.contains(m) { is_legal = false; break; } } } if is_legal { candidates.push(cand); } } } // Breadth-first search stuff: add unexplored nodes to queue for cand in candidates { let ser = cand.serialize(); if !visited.contains(&ser) { visited.insert(ser); queue.push_back((cand, depth + 1)); } } } } fn main() { // Unlike all other days with an `input.txt' file, I just hardcode // my input here, because I'm too lazy to parse natural language. let floor1_part1 = Floor { generators: HashSet::from(["Pm"]), microchips: HashSet::from(["Pm"]), }; let floor2 = Floor { generators: HashSet::from(["Co", "Cm", "Ru", "Pu"]), microchips: HashSet::new(), }; let floor3 = Floor { generators: HashSet::new(), microchips: HashSet::from(["Co", "Cm", "Ru", "Pu"]), }; let floor4 = Floor { generators: HashSet::new(), microchips: HashSet::new(), }; // Part 1 gives 33 for me println!( "Part 1 solution: {}", solve_puzzle(State { elevator: 0, floors: [floor1_part1, floor2.clone(), floor3.clone(), floor4.clone()], }) ); let floor1_part2 = Floor { generators: HashSet::from(["Pm", "El", "Di"]), microchips: HashSet::from(["Pm", "El", "Di"]), }; // Part 2 gives 57 for me println!( "Part 2 solution: {}", solve_puzzle(State { elevator: 0, floors: [floor1_part2, floor2.clone(), floor3.clone(), floor4.clone()], }) ); } #[cfg(test)] mod tests { use super::*; #[test] fn part1_example1() { let floor1 = Floor { generators: HashSet::new(), microchips: HashSet::from(["H", "Li"]), }; let floor2 = Floor { generators: HashSet::from(["H"]), microchips: HashSet::new(), }; let floor3 = Floor { generators: HashSet::from(["Li"]), microchips: HashSet::new(), }; let floor4 = Floor { generators: HashSet::new(), microchips: HashSet::new(), }; assert_eq!( 11, solve_puzzle(State { elevator: 0, floors: [floor1, floor2, floor3, floor4], }) ); } }