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