Initial commit

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],
+            })
+        );
+    }
+}