day14.rs

//! # Docking Data
//!
//! First we parse each mask into 2 `u64` values, `ones` where a bit is set when there is a
//! corresponding "1" in the mask and `xs` (plural of "x") where a bit is set when there is a
//! corresponding "X" in the mask. A bit will never be set in the same location in both `ones` and
//! `xs`. For example:
//!
//! ```none
//! Mask: 000000000000000000000000000000X1001X
//! ones: 000000000000000000000000000000010010
//! xs:   000000000000000000000000000000100001
//! ```
//!
//! ## Part One
//! The memory values are quite sparse, about 500 discrete values in an address range of about
//! 65,000. This makes a [`FastMap`] a better choice than a large mostly empty array. Storing the
//! correct value is a straightforward application of the problem rules, expressed as bitwise logic.
//!
//! ## Part Two
//! This part is subtly tricky to solve quickly. The maximum number of Xs in any mask is 9 which
//! gives 2⁹ = 512 different memory addresses. A brute force solution will work, but there's a much
//! more elegant approach.
//!
//! We treat each address and mask combination as a set. Then by using the
//! [inclusion-exclusion principle](https://en.wikipedia.org/wiki/Inclusion-exclusion_principle)
//! we can determine any overlaps with other sets and deduct the correct number of values.
//!
//! For example:
//! ```none
//! mask = 0000000000000000000000000000000001XX  // A
//! mem[8] = 3
//! mask = 00000000000000000000000000000000011X  // B
//! mem[8] = 5
//! mask = 000000000000000000000000000000000111  // C
//! mem[8] = 7
//! ```
//! Results in the following address sets:
//! ```none
//! ┌──────────────┐A            Set A: 12 13 14 15
//! │ 12 13        │             Set B: 14 15
//! │ ┌─────────┐B │             Set C: 15
//! │ │ 14      │  │
//! │ │ ┌────┐C │  │
//! │ │ │ 15 │  │  │
//! │ │ └────┘  │  │
//! │ └─────────┘  │
//! └──────────────┘
//! ```
//!
//! Using the inclusion-exclusion principle the remaining size of A is:
//! 4 (initial size) - 2 (overlap with B) - 1 (overlap with C) + 1 (overlap between B and C) = 2
//! If there were any quadruple overlaps we would add those, subtract quintuple, and so on until
//! there are no more overlaps remaining.
//!
//! To calculate the final answer we treat the value as the weight of the set, in this case:
//! 2 × 3 + 1 × 5 + 1 × 7 = 18
//!
//! The complexity of this approach depends on how many addresses overlap. In my input most
//! addresses overlapped with zero others, a few with one and rarely with more than one.
//! Benchmarking against the brute force solution showed that this approach is ~90x faster.
//!
//! [`FastMap`]: crate::util::hash
use crate::util::hash::*;
use crate::util::parse::*;

#[derive(Clone, Copy)]
pub enum Instruction {
    Mask { ones: u64, xs: u64 },
    Mem { address: u64, value: u64 },
}

impl Instruction {
    fn mask(pattern: &str) -> Self {
        let (ones, xs) = pattern.bytes().fold((0, 0), |(ones, xs), b| {
            ((ones << 1) | (b == b'1') as u64, (xs << 1) | (b == b'X') as u64)
        });
        Self::Mask { ones, xs }
    }
}

struct Set {
    ones: u64,
    floating: u64,
    weight: u64,
}

impl Set {
    /// The one bits are from the original address, plus any from the mask, less any that
    /// overlap with Xs.
    fn new(address: u64, value: u64, ones: u64, floating: u64) -> Self {
        Self { ones: (address | ones) & !floating, floating, weight: value }
    }

    /// Sets are disjoint if any 2 one bits are different and there is no X in either set.
    ///
    /// The intersection of two masks looks like:
    /// ```none
    /// First:  0011XXX
    /// Second: 0X1X01X
    /// Result: 001101X
    /// ```
    fn intersect(&self, other: &Self) -> Option<Self> {
        let disjoint = (self.ones ^ other.ones) & !(self.floating | other.floating);

        (disjoint == 0).then_some(Self {
            ones: self.ones | other.ones,
            floating: self.floating & other.floating,
            weight: 0,
        })
    }

    fn size(&self) -> i64 {
        1 << self.floating.count_ones()
    }
}

pub fn parse(input: &str) -> Vec<Instruction> {
    input
        .lines()
        .map(|line| {
            if line.starts_with("mask") {
                Instruction::mask(&line[7..])
            } else {
                let (address, value) = line[4..].split_once("] = ").unwrap();
                Instruction::Mem { address: address.unsigned(), value: value.unsigned() }
            }
        })
        .collect()
}

pub fn part1(input: &[Instruction]) -> u64 {
    let mut set = 0;
    let mut keep = 0;
    let mut memory = FastMap::new();

    for &instruction in input {
        match instruction {
            Instruction::Mask { ones, xs } => {
                set = ones;
                keep = ones | xs;
            }
            Instruction::Mem { address, value } => {
                memory.insert(address, (value | set) & keep);
            }
        }
    }

    memory.values().sum()
}

pub fn part2(input: &[Instruction]) -> u64 {
    let mut ones = 0;
    let mut floating = 0;
    let mut sets = Vec::new();

    for &instruction in input {
        match instruction {
            Instruction::Mask { ones: next_ones, xs } => {
                ones = next_ones;
                floating = xs;
            }
            Instruction::Mem { address, value } => {
                sets.push(Set::new(address, value, ones, floating));
            }
        }
    }

    let mut total = 0;
    let mut candidates = Vec::new();

    for (i, set) in sets.iter().enumerate() {
        candidates.extend(sets[(i + 1)..].iter().filter_map(|other| set.intersect(other)));

        let size = set.size() + subsets(set, -1, &candidates);

        total += size as u64 * set.weight;
        candidates.clear();
    }

    total
}

fn subsets(cube: &Set, sign: i64, candidates: &[Set]) -> i64 {
    let mut total = 0;

    for (i, other) in candidates.iter().enumerate() {
        if let Some(next) = cube.intersect(other) {
            total += sign * next.size() + subsets(&next, -sign, &candidates[(i + 1)..]);
        }
    }

    total
}