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 mut ones = 0;
75 let mut xs = 0;
76
77 for b in pattern.bytes() {
78 ones <<= 1;
79 xs <<= 1;
80 match b {
81 b'1' => ones |= 1,
82 b'X' => xs |= 1,
83 _ => (),
84 }
85 }
86
87 Self::Mask { ones, xs }
88 }
89}
90
91struct Set {
92 ones: u64,
93 floating: u64,
94 weight: u64,
95}
96
97impl Set {
98 /// The one bits are from the original address, plus any from the mask, less any that
99 /// overlap with Xs.
100 fn new(address: u64, value: u64, ones: u64, floating: u64) -> Set {
101 Set { ones: (address | ones) & !floating, floating, weight: value }
102 }
103
104 /// Sets are disjoint if any 2 one bits are different and there is no X in either set.
105 ///
106 /// The intersection of two masks looks like:
107 /// ```none
108 /// First: 0011XXX
109 /// Second: 0X1X01X
110 /// Result: 001101X
111 /// ```
112 fn intersect(&self, other: &Set) -> Option<Set> {
113 let disjoint = (self.ones ^ other.ones) & !(self.floating | other.floating);
114
115 (disjoint == 0).then_some(Set {
116 ones: self.ones | other.ones,
117 floating: self.floating & other.floating,
118 weight: 0,
119 })
120 }
121
122 fn size(&self) -> i64 {
123 1 << self.floating.count_ones()
124 }
125}
126
127pub fn parse(input: &str) -> Vec<Instruction> {
128 input
129 .lines()
130 .map(|line| {
131 if line.len() == 43 {
132 Instruction::mask(&line[7..])
133 } else {
134 let (address, value) = line[4..].split_once("] = ").unwrap();
135 Instruction::Mem { address: address.unsigned(), value: value.unsigned() }
136 }
137 })
138 .collect()
139}
140
141pub fn part1(input: &[Instruction]) -> u64 {
142 let mut set = 0;
143 let mut keep = 0;
144 let mut memory = FastMap::new();
145
146 for &instruction in input {
147 match instruction {
148 Instruction::Mask { ones, xs } => {
149 set = ones;
150 keep = ones | xs;
151 }
152 Instruction::Mem { address, value } => {
153 memory.insert(address, (value | set) & keep);
154 }
155 }
156 }
157
158 memory.values().sum()
159}
160
161pub fn part2(input: &[Instruction]) -> u64 {
162 let mut ones = 0;
163 let mut floating = 0;
164 let mut sets = Vec::new();
165
166 for &instruction in input {
167 match instruction {
168 Instruction::Mask { ones: next_ones, xs } => {
169 ones = next_ones;
170 floating = xs;
171 }
172 Instruction::Mem { address, value } => {
173 sets.push(Set::new(address, value, ones, floating));
174 }
175 }
176 }
177
178 let mut total = 0;
179 let mut candidates = Vec::new();
180
181 for (i, set) in sets.iter().enumerate() {
182 candidates.extend(sets[(i + 1)..].iter().filter_map(|other| set.intersect(other)));
183
184 let size = set.size() + subsets(set, -1, &candidates);
185
186 total += size as u64 * set.weight;
187 candidates.clear();
188 }
189
190 total
191}
192
193fn subsets(cube: &Set, sign: i64, candidates: &[Set]) -> i64 {
194 let mut total = 0;
195
196 for (i, other) in candidates.iter().enumerate() {
197 if let Some(next) = cube.intersect(other) {
198 total += sign * next.size() + subsets(&next, -sign, &candidates[(i + 1)..]);
199 }
200 }
201
202 total
203}