aoc/year2020/day14.rs
1//! # Docking Data
2//!
3//! First we parse each mask into 2 `u64` values, `ones` where a bit is set when there is a
4//! corresponding "1" in the mask and `xs` (plural of "x") where a bit is set when there is a
5//! corresponding "X" in the mask. A bit will never be set in the same location in both `ones` and
6//! `xs`. For example:
7//!
8//! ```none
9//! Mask: 000000000000000000000000000000X1001X
10//! ones: 000000000000000000000000000000010010
11//! xs: 000000000000000000000000000000100001
12//! ```
13//!
14//! ## Part One
15//! The memory values are quite sparse, about 500 discrete values in an address range of about 65,000.
16//! This makes a [`FastMap`] a better choice than a large mostly empty array. Storing the correct
17//! value is a straightforward application of the problem rules, expressed as bitwise logic.
18//!
19//! ## Part Two
20//! This part is subtly tricky to solve quickly. The maximum number of Xs in any mask is 9 which
21//! gives 2⁹ = 512 different memory addresses. A brute force solution will work, but there's a much
22//! more elegant approach.
23//!
24//! We treat each address and mask combination as a set. Then by using the
25//! [inclusion-exclusion principle](https://en.wikipedia.org/wiki/Inclusion-exclusion_principle)
26//! we can determine any overlaps with other sets and deduct the correct number of values.
27//!
28//! For example:
29//! ```none
30//! mask = 0000000000000000000000000000000001XX // A
31//! mem[8] = 3
32//! mask = 00000000000000000000000000000000011X // B
33//! mem[8] = 5
34//! mask = 000000000000000000000000000000000111 // C
35//! mem[8] = 7
36//! ```
37//! Results in the following address sets:
38//! ```none
39//! ┌──────────────┐A Set A: 12 13 14 15
40//! │ 12 13 │ Set B: 14 15
41//! │ ┌─────────┐B │ Set C: 15
42//! │ │ 14 │ │
43//! │ │ ┌────┐C │ │
44//! │ │ │ 15 │ │ │
45//! │ │ └────┘ │ │
46//! │ └─────────┘ │
47//! └──────────────┘
48//! ```
49//!
50//! Using the inclusion-exclusion principle the remaining size of A is:
51//! 4 (initial size) - 2 (overlap with B) - 1 (overlap with C) + 1 (overlap between B and C) = 2
52//! If there were any quadruple overlaps we would add those, subtract quintuple, and so on until
53//! there are no more overlaps remaining.
54//!
55//! To calculate the final answer we treat the value as the weight of the set, in this case:
56//! 2 × 3 + 1 × 5 + 1 × 7 = 18
57//!
58//! The complexity of this approach depends on how many addresses overlap. In my input most
59//! addresses overlapped with zero others, a few with one and rarely with more than one.
60//! Benchmarking against the brute force solution showed that this approach is ~90x faster.
61//!
62//! [`FastMap`]: crate::util::hash
63use crate::util::hash::*;
64use crate::util::parse::*;
65
66#[derive(Copy, Clone)]
67pub enum Instruction {
68 Mask { ones: u64, xs: u64 },
69 Mem { address: u64, value: u64 },
70}
71
72impl Instruction {
73 fn mask(pattern: &str) -> Instruction {
74 let (ones, xs) = pattern.bytes().fold((0, 0), |(ones, xs), b| {
75 ((ones << 1) | (b == b'1') as u64, (xs << 1) | (b == b'X') as u64)
76 });
77 Self::Mask { ones, xs }
78 }
79}
80
81struct Set {
82 ones: u64,
83 floating: u64,
84 weight: u64,
85}
86
87impl Set {
88 /// The one bits are from the original address, plus any from the mask, less any that
89 /// overlap with Xs.
90 fn new(address: u64, value: u64, ones: u64, floating: u64) -> Set {
91 Set { ones: (address | ones) & !floating, floating, weight: value }
92 }
93
94 /// Sets are disjoint if any 2 one bits are different and there is no X in either set.
95 ///
96 /// The intersection of two masks looks like:
97 /// ```none
98 /// First: 0011XXX
99 /// Second: 0X1X01X
100 /// Result: 001101X
101 /// ```
102 fn intersect(&self, other: &Set) -> Option<Set> {
103 let disjoint = (self.ones ^ other.ones) & !(self.floating | other.floating);
104
105 (disjoint == 0).then_some(Set {
106 ones: self.ones | other.ones,
107 floating: self.floating & other.floating,
108 weight: 0,
109 })
110 }
111
112 fn size(&self) -> i64 {
113 1 << self.floating.count_ones()
114 }
115}
116
117pub fn parse(input: &str) -> Vec<Instruction> {
118 input
119 .lines()
120 .map(|line| {
121 if line.starts_with("mask") {
122 Instruction::mask(&line[7..])
123 } else {
124 let (address, value) = line[4..].split_once("] = ").unwrap();
125 Instruction::Mem { address: address.unsigned(), value: value.unsigned() }
126 }
127 })
128 .collect()
129}
130
131pub fn part1(input: &[Instruction]) -> u64 {
132 let mut set = 0;
133 let mut keep = 0;
134 let mut memory = FastMap::new();
135
136 for &instruction in input {
137 match instruction {
138 Instruction::Mask { ones, xs } => {
139 set = ones;
140 keep = ones | xs;
141 }
142 Instruction::Mem { address, value } => {
143 memory.insert(address, (value | set) & keep);
144 }
145 }
146 }
147
148 memory.values().sum()
149}
150
151pub fn part2(input: &[Instruction]) -> u64 {
152 let mut ones = 0;
153 let mut floating = 0;
154 let mut sets = Vec::new();
155
156 for &instruction in input {
157 match instruction {
158 Instruction::Mask { ones: next_ones, xs } => {
159 ones = next_ones;
160 floating = xs;
161 }
162 Instruction::Mem { address, value } => {
163 sets.push(Set::new(address, value, ones, floating));
164 }
165 }
166 }
167
168 let mut total = 0;
169 let mut candidates = Vec::new();
170
171 for (i, set) in sets.iter().enumerate() {
172 candidates.extend(sets[(i + 1)..].iter().filter_map(|other| set.intersect(other)));
173
174 let size = set.size() + subsets(set, -1, &candidates);
175
176 total += size as u64 * set.weight;
177 candidates.clear();
178 }
179
180 total
181}
182
183fn subsets(cube: &Set, sign: i64, candidates: &[Set]) -> i64 {
184 let mut total = 0;
185
186 for (i, other) in candidates.iter().enumerate() {
187 if let Some(next) = cube.intersect(other) {
188 total += sign * next.size() + subsets(&next, -sign, &candidates[(i + 1)..]);
189 }
190 }
191
192 total
193}