DEV Community

Discussion on: Advent of Code 2020 Solution Megathread - Day 14: Docking Data

Collapse
 
benwtrent profile image
Benjamin Trent

Instead of figuring out how to do this purely with bitmasking + bit math, I brute forced utilizing bitvec. Not pretty :)

struct MaskAndValues {
    mask: HashMap<u8, u8>,
    values: Vec<(usize, usize)>,
}

impl MaskAndValues {
    fn add_values(&self, totals: &mut HashMap<usize, usize>) {
        for (key, value) in &self.values {
            totals.insert(*key, self.masked_value(value));
        }
    }

    fn add_values_multiple_places(&self, totals: &mut HashMap<usize, usize>) {
        for (key, value) in &self.values {
            let keys = self.get_keys(key);
            for k in keys {
                totals.insert(k, *value);
            }
        }
    }

    fn get_keys(&self, key: &usize) -> Vec<usize> {
        let bits = key.view_bits::<Lsb0>();
        let mut bits = BitVec::from_bitslice(bits);
        for (pos, val) in &self.mask {
            if *val == 0 {
                continue;
            }
            bits.set(*pos as usize, true);
        }
        let new_key = bits.load::<usize>();
        let mut values = HashSet::new();
        for bit in 0..36usize {
            if !self.mask.contains_key(&(bit as u8)) {
                bits.set(bit, false);
            }
        }
        values.insert(bits.load::<usize>());
        MaskAndValues::masking_recur(
            &self.mask.keys().map(|v| *v).collect(),
            &mut bits,
            0,
            &mut values,
        );
        values.iter().map(|v| *v).collect()
    }

    fn masking_recur(
        mask: &HashSet<u8>,
        bits: &mut BitVec,
        curr_bit: u8,
        values: &mut HashSet<usize>,
    ) {
        if curr_bit > 35 {
            return;
        }
        let mut curr_bit = curr_bit;
        while mask.contains(&(curr_bit as u8)) {
            curr_bit += 1;
        }
        if curr_bit > 35 {
            return;
        }
        bits.set(curr_bit as usize, true);
        values.insert(bits.load::<usize>());
        MaskAndValues::masking_recur(mask, bits, curr_bit + 1, values);
        bits.set(curr_bit as usize, false);
        values.insert(bits.load::<usize>());
        MaskAndValues::masking_recur(mask, bits, curr_bit + 1, values);
    }

    fn masked_value(&self, value: &usize) -> usize {
        let bits = value.view_bits::<Lsb0>();
        let mut bits = BitVec::from_bitslice(bits);
        for (pos, val) in &self.mask {
            bits.set(*pos as usize, *val == 1);
        }
        bits.load::<usize>()
    }
}

#[aoc(day14, part1)]
fn masked_bit_sums(input: &Vec<MaskAndValues>) -> usize {
    let mut vals: HashMap<usize, usize> = HashMap::new();
    for v in input {
        v.add_values(&mut vals);
    }
    vals.values().sum()
}

#[aoc(day14, part2)]
fn data_mask_sums(input: &Vec<MaskAndValues>) -> usize {
    let mut vals: HashMap<usize, usize> = HashMap::new();
    for v in input {
        v.add_values_multiple_places(&mut vals);
    }
    vals.values().sum()
}

Enter fullscreen mode Exit fullscreen mode