diff options
Diffstat (limited to 'd11/src/main.rs')
| -rw-r--r-- | d11/src/main.rs | 251 |
1 files changed, 251 insertions, 0 deletions
diff --git a/d11/src/main.rs b/d11/src/main.rs new file mode 100644 index 0000000..3dfad58 --- /dev/null +++ b/d11/src/main.rs @@ -0,0 +1,251 @@ +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], + }) + ); + } +} |