aoc/year2016/

day11.rs

//! # Radioisotope Thermoelectric Generators
//!
//! Solves using a [BFS](https://en.wikipedia.org/wiki/Breadth-first_search) from the
//! starting position where each next state is the possible elevator moves either one floor up or
//! down. This was faster than using [A*](https://en.wikipedia.org/wiki/A*_search_algorithm)
//! with a heuristic.
//!
//! A huge critical optimization is the observation that generator and chip pairs are *fungible*.
//! A configuration that starts with two pairs on floor one takes the same number of steps to
//! solve whether pair A or pair B is moved first (that is, the setup `[-;-;AG,AM;BG,BM]` while on
//! floor 2 is indistinguishable from `[-;-;BG,BM;AG,AM]` on floor 2 in terms of the final result).
//! However, the relative positions of pairs still matter (the setup `[AM;AG;BG;BM]` on floor two
//! can move BG up or down, but the setup `[AM;BG;AG;BM]` on floor two can only move AG up). To
//! maximize state sharing, represent each pair's generator and microchip position as hex
//! digits, but merge all permutations by sorting those hex digit pairs during the hash
//! function. Including the elevator position, the hash value requires up to 30 useful bits
//! (2 + 7*4) if densely packed, although this uses a 64-bit struct with one-hot encodings.
//!
//! Next, observe that adding a chip and generator pair on floor 1 adds 12 moves to the final
//! solution. Likewise, removing a pair from floor 1 (but only if there is still something
//! else left on the floor) can be solved in 12 fewer moves. Tracking a smaller number of
//! chip and generator pairs, then adjusting by 12 times the number of ignored pairs,
//! is inherently faster.
//!
//! The rules for a valid floor are either:
//!
//! * Any number of microchips only with no generators.
//! * Any microchip on a floor with at least one generator must have its own generator on that
//!   floor.
//!
//! This allows us to efficiently memoize previously seen states and reject any that we've seen
//! before extremely quickly. Other optimizations:
//!
//! * If we can move 2 items up, then skip only moving 1 item up.
//! * If we can move 1 item down, then skip moving 2 items down.
//! * Moving a microchip and generator together is only safe if they are the same type (if they are
//!   not of the same type, then the old floor will necessarily have the generator that pairs with
//!   the chip being moved, leaving that chip to be fried on its new floor).
//! * If floor 1 is empty then don't move items back down to it, similarly if both floor 1 and floor
//!   2 are empty then don't move items to them.
use std::collections::VecDeque;

use crate::util::bitset::*;
use crate::util::hash::*;

// A one-hot encoding is more efficient than 0-3. For each byte, the generator is the
// high nibble, and the microchip the low nibble. Only 5 bytes matter, because the part two
// pairs contribute a constant input. The used bytes are stored in little-endian order, and
// unused lanes will be 0.
const MASK: u64 = 0x0000000101010101;
const FLOOR1: u64 = (MASK << 4) | MASK;
const FLOOR2: u64 = FLOOR1 << 1;
const FLOOR3: u64 = FLOOR2 << 1;
const FLOOR4: u64 = FLOOR3 << 1;
const PAIR1: u8 = (1 << 4) | 1;

#[derive(Clone, Copy, Default, Eq, Hash, PartialEq)]
pub struct State {
    elevator: u8, // 0-3
    pairs: u64,   // One-hot encoded floors for up to 5 item pairs.
}

impl State {
    // Reject any inconsistent setup.
    fn valid(&self, floor: u8) -> bool {
        let chips = (self.pairs) & (MASK << floor);
        let gens = (self.pairs >> 4) & (MASK << floor);
        gens == 0 || (chips & !gens) == 0
    }

    // Critical optimization treating generators and microchips as fungible.
    // Rearrange the pairs into canonical order. Endianness matters for getting valid slice indices.
    fn canon(mut self) -> Self {
        let mut array = self.pairs.to_le_bytes();
        array[..5].sort_unstable();
        self.pairs = u64::from_le_bytes(array);
        self
    }

    // Attempt to adjust state by moving one or two items up or down.
    fn move_floor(self, up: bool, item_mask: u64) -> Option<Self> {
        // Build the new state.
        let mut state = self;

        if up {
            state.pairs += item_mask;
            state.elevator += 1;
        } else {
            state.pairs -= item_mask >> 1;
            state.elevator -= 1;
        }

        (state.valid(self.elevator) && state.valid(state.elevator)).then(|| state.canon())
    }
}

pub fn parse(input: &str) -> u32 {
    let mut pairs = FastMap::new();

    // Find all items, and set an entry in state.pairs for each element name.
    let mut floor = 1;
    let words: Vec<_> = input.split(&[' ', ',', '.', '-']).skip(3).collect();

    for &[first, second] in words.array_windows() {
        match second {
            "floor" => floor <<= 1,
            "compatible" => *pairs.entry(first).or_insert(0) |= floor,
            "generator" => *pairs.entry(first).or_insert(0) |= floor << 4,
            _ => (),
        }
    }

    // Optimize search by pre-handling item pairs starting on non-empty floor 1.
    let mut floors = [0_u8; 8];
    let mut non_empty = false;
    let mut steps = 0;
    let mut i = 0;

    for pair in pairs.into_values() {
        if non_empty && pair == PAIR1 {
            steps += 12;
        } else {
            non_empty |= pair & PAIR1 != 0;
            floors[i] = pair;
            i += 1;
        }
    }

    // Little-endian matters, based on the indices that canon() will use.
    let state = State { elevator: 0, pairs: u64::from_le_bytes(floors) };
    bfs(state.canon(), steps)
}

pub fn part1(input: &u32) -> u32 {
    *input
}

pub fn part2(input: &u32) -> u32 {
    // Both pairs add 12 steps each.
    *input + 24
}

fn bfs(start: State, steps: u32) -> u32 {
    let mut todo = VecDeque::new();
    let mut seen = FastSet::with_capacity(500);

    todo.push_back((start, steps));
    seen.insert(start);

    while let Some((state, steps)) = todo.pop_front() {
        // Done if all items are on the top floor (the elevator will necessarily be there too).
        if state.pairs & FLOOR4 == state.pairs {
            return steps;
        }

        // Iterate over items that can be moved.
        let items = state.pairs & (FLOOR1 << state.elevator);
        let mut push = |up: bool, mask: u64| -> bool {
            if let Some(next) = state.move_floor(up, mask)
                && seen.insert(next)
            {
                todo.push_back((next, steps + 1));
                true
            } else {
                false
            }
        };

        // When moving down, try one item first. Try two only if one didn't work.
        // Don't move down from bottom floor, or down into empty region.
        if !(state.elevator == 0
            || (state.elevator == 1 && (state.pairs & FLOOR1) == 0)
            || (state.elevator == 2 && (state.pairs & (FLOOR1 | FLOOR2) == 0)))
        {
            let mut added = false;

            for i in items.biterator() {
                added |= push(false, 1 << i);
            }
            if !added {
                for i in items.biterator() {
                    for j in items.biterator().take_while(|&j| j < i) {
                        push(false, (1 << i) | (1 << j));
                    }
                }
            }
        }

        // When moving up, try two items first. Try one only if two didn't work.
        // Don't move up from top floor.
        if state.elevator < 3 {
            let mut added = false;

            for i in items.biterator() {
                for j in items.biterator().take_while(|&j| j < i) {
                    added |= push(true, (1 << i) | (1 << j));
                }
            }
            if !added {
                for i in items.biterator() {
                    push(true, 1 << i);
                }
            }
        }
    }

    unreachable!()
}