aoc/year2021/

day12.rs

//! # Passage Pathing
//!
//! Our basic approach is a [DFS](https://en.wikipedia.org/wiki/Depth-first_search) through the cave
//! system, exploring all possible permutations of the paths and finishing whenever we reach
//! the `end` cave.
//!
//! To speed things up, 2 strategies are used, one high-level and one low-level:
//! * [Memoization](https://en.wikipedia.org/wiki/Memoization) (or caching) of the possible paths
//!   from each position, taking into account previously visited caves is the high-level strategy
//!   to reuse work and save time.
//! * [Bit Manipulation](https://en.wikipedia.org/wiki/Bit_manipulation) to store both the graph of
//!   cave connections as an [adjacency matrix](https://en.wikipedia.org/wiki/Adjacency_matrix)
//!   and the list of visited caves compressed into a single `u32` is the low-level strategy to
//!   quickly and efficiently store the small cardinality set of caves.
use crate::util::bitset::*;
use crate::util::hash::*;
use crate::util::iter::*;

const START: usize = 0;
const END: usize = 1;

pub struct Input {
    small: u32,
    edges: Vec<u32>,
}

/// Parse the input into an adjacency matrix of edges compressed into `u32` bitfields.
///
/// First, each cave is assigned a unique index, with `0` reserved for the `start` cave and `1`
/// reserved for the `end` cave. For example, the sample input caves are:
///
/// | start | end | A | b | c | d |
/// | :---: | :-: | - | - | - | - |
/// |   0   |  1  | 2 | 3 | 4 | 5 |
///
/// Next a `vec` of `u32` with an entry for each cave at the corresponding index is created with
/// a bit set for each other cave reachable at `2ⁿ` where n is the cave index. The start cave
/// can only be visited once at the beginning, so it is removed from all edges.
/// For example, the sample start cave `vec` looks like:
///
/// | cave  | index | edges  |
/// | ----- | ----- | ------ |
/// | start | 0     |   1100 |
/// | end   | 1     |   1100 |
/// | A     | 2     |  11010 |
/// | b     | 3     | 100110 |
/// | c     | 4     |    100 |
/// | d     | 5     |   1000 |
///
/// Finally, all small caves are added to a single `u32`, for example the
/// sample data looks like `111011`.
pub fn parse(input: &str) -> Input {
    let tokens: Vec<_> =
        input.split(|c: char| !c.is_ascii_alphabetic()).filter(|s| !s.is_empty()).collect();

    let mut indices = FastMap::build([("start", START), ("end", END)]);
    for token in &tokens {
        let next = indices.len();
        indices.entry(token).or_insert(next);
    }

    let mut edges = vec![0; indices.len()];
    for [a, b] in tokens.iter().chunk::<2>() {
        edges[indices[a]] |= 1 << indices[b];
        edges[indices[b]] |= 1 << indices[a];
    }
    let not_start = !(1 << START);
    edges.iter_mut().for_each(|edge| *edge &= not_start);

    let small = indices
        .iter()
        .filter(|(key, _)| key.as_bytes()[0].is_ascii_lowercase())
        .fold(0, |small, (_, index)| small | (1 << index));

    Input { small, edges }
}

/// Explore the cave system visiting all small caves only once.
pub fn part1(input: &Input) -> u32 {
    explore(input, false)
}

/// Explore the cave system visiting a single small cave twice and the other small caves only once.
pub fn part2(input: &Input) -> u32 {
    explore(input, true)
}

/// Convenience method to create initial state.
fn explore(input: &Input, twice: bool) -> u32 {
    // Calculate the needed size of the cache as the product of:
    // * 2 states for boolean "twice".
    // * n states for the number of caves including start and end.
    // * 2⁽ⁿ⁻²⁾ states for the possible visited combinations, not including start and end cave.
    let size = 2 * input.edges.len() * (1 << (input.edges.len() - 2));
    let mut cache = vec![0; size];

    paths(input, START, 0, twice, &mut cache)
}

/// Core recursive DFS logic.
///
/// First we check if we have either reached the `end` cave or seen this state before,
/// returning early in either case with the respective result.
///
/// Next we use bit manipulation to quickly iterate through the caves connected to our current
/// location. The [`trailing_zeros`] method returns the next set bit. This intrinsic compiles to
/// a single machine code instruction on x86 and ARM and is blazing fast. We remove visited caves
/// using a `^` XOR instruction.
///
/// The nuance is reusing the same code for both part one and part two. First we check if we can visit
/// a cave using the rules for part one. If not, then we also check if the `twice` variable is
/// still `true`. This variable allows a single second visit to a small cave. The expression
/// `once && twice` sets this value to `false` whenever we need to use it to visit a small cave.
///
/// [`trailing_zeros`]: u32::trailing_zeros
fn paths(input: &Input, from: usize, visited: u32, twice: bool, cache: &mut [u32]) -> u32 {
    // Calculate index by converting "twice" to either 1 or 0, then multiplying "from" by 2
    // (the cardinality of "twice") and "visited" by "edges.len()".
    // Subtle nuance, by not multiplying "visited" by 2 and also dividing by 2 we ignore the
    // two least significant bits for start and end cave, as these will always be 0 and 1
    // respectively.
    let index = twice as usize + 2 * from + (input.edges.len() * (visited as usize / 2));
    if cache[index] > 0 {
        return cache[index];
    }

    let mut caves = input.edges[from];
    let mut total = 0;
    let end = 1 << END;

    if caves & end != 0 {
        caves ^= end;
        total += 1;
    }

    for to in caves.biterator() {
        let mask = 1 << to;
        let once = input.small & mask == 0 || visited & mask == 0;

        if once || twice {
            total += paths(input, to, visited | mask, once && twice, cache);
        }
    }

    cache[index] = total;
    total
}