path: root/d11/src/main.rs

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