What I've Learned From Advent of Code 2020
My goal is to program defensively the solutions of the Advent of Code puzzles in idiomatic declarative Rust using only the standard library. You can find the repository here.
0x01
use std::collections::BTreeSet;
BTreeSet (and BTreeMap) are (sometimes) performance wise far superior on lookups as their default counterparts (Vec/HashMap).
If you are unsettled about the data structure you need, this website could help you to determine the needed characteristics
and the official documentation of collections will guide you towards the appropriate data structure.
0x02
(first..=last).contains(value)
This is a nice expressive way of checking if a value is in a certain range. There will be even the same machine code generated as with direct comparing code, because of compiler optimizations.
0x03
struct RingAdderSequence {
next: u64,
step_width: u64,
modulus: u64,
}
impl Iterator for RingAdderSequence {
type Item = u64;
fn next(&mut self) -> Option<u64> {
let current = self.next;
self.next += self.step_width;
self.next %= self.modulus;
Some(current)
}
}
More often than you might think, it is possible to spot mathematical structures in a given logic, you have to implement.
In this specific case I spotted a sequence operating in a ring and implemented it generically as a custom Iterator, since iterators are a perfect match for sequences.
A Reddit user mentioned, that there would be a shorter solution, but I prefer the custom Iterator as it uses modular arithmetic and is therefore faster.
(0..modulus).cycle().step_by(step_width).nth(n)
0x04
Nothing special, besides a parsing algorithm to generate a set in a list from the following input.
key0:value0_0 key1:value1_0 key2:value2_0
key0:value0_1 key1:value1_1 key2:value2_1
0x05
Today I learned there is an unknown function called scan
which is a kind of stateful (like fold) map.
Furthermore, it helped enormously to understand the maths of the problems.
struct SeatPosition {
pub row: u32,
pub column: u32,
}
impl SeatPosition {
fn get_id(&self) -> u32 {
(self.row * 8) + self.column
}
}
impl Sub<u32> for &SeatPosition {
type Output = SeatPosition;
fn sub(self, other: u32) -> Self::Output {
let new_id = self.get_id() - other;
let column = new_id % 8;
let row = (new_id - column) / 8;
SeatPosition { row, column }
}
}
In the last block the goal was to subtract a number from the ID of the seat. At first glance I tried some rather complicated if-expressions,
but then I analyzed the mechanics of generating the ID’s, and then the subtraction process was fairly trivial.
0x08
This is a remarkably interesting challenge as you implement a very basic emulator and as a result you gain a more natural understanding of low-level stuff like segfaults.
(1_u64 as i128 + 1_i64 as i128) as u64
This rather unintuitive statement is required when you want to add/subtract a signed integer to/from an unsigned (bitwise same sized) number without loosing information.
0x0A
fn count_mutations(adapters: &[u64], last_value: u64, cache: &mut BTreeMap<u64, u64>) -> u64 {
if cache.contains_key(&last_value) {
return cache[&last_value];
}
if last_value + 3 < adapters[0] {
return 0;
}
if adapters.len() == 1 {
return 1;
}
let mutations = count_mutations(&adapters[1..], adapters[0], cache)
+ count_mutations(&adapters[1..], last_value, cache);
cache.insert(last_value, mutations);
mutations
}
If you have a recursive function which depends primarily on one input parameter and the function will recompute values over and over again, you should memoize the computed results with a BTreeMap (or use another form of dynamic programming).
Without the caching, this algorithm won’t terminate in a few minutes, with caching it took ≈ 30 µs on the same machine.
0x0B
Todays challenge was essentially to build a Conway’s Game of Life engine with substitutable counting neighbors functions.
fn get_first_border(center: usize) -> usize {
center - (center != 0) as usize
}
fn get_width(center: usize, size: usize) -> usize {
let mut default_width = 3;
default_width -= (center == 0) as usize;
default_width -= (center == size - 1) as usize;
default_width
}
fn count_occupied_neighbors(map: &Map, line_index: usize, column_index: usize) -> u32 {
map.iter()
.skip(get_first_border(line_index))
.take(get_width(line_index, map.len()))
.map(|line| {
line.iter()
.skip(get_first_border(column_index))
.take(get_width(column_index, line.len()))
.filter(|state| state.is_occupied())
.count() as u32
})
.sum::<u32>()
- (map[line_index][column_index].is_occupied() as u32)
}
The ordinary neighbors counting without any static indexing, as it uses only skip and take to get the 3x3, or smaller, field and subtracts the inner field afterwards.
The the field size functions are done via branchless programming.
0x0C
It took me a hard time to solve the second part, as the solution involved the Chinese remainder theorem since it wouldn’t be possible without the theorem to have a terminating algorithm. This lesson teaches us to focus on the mathematics and only secondarily on algorithmics.
0x0F
let mut last_values: HashMap<u32, u32> = starting_values
.iter()
.enumerate()
.map(|(index, value)| (*value, index as u32 + 1))
.collect();
collect lets you generate a *Map out of an Iterator of touples.
Incidentally, you can use collect to propagate an inner error to the outside, as described in this blog post (section collect()).
use std::collections::HashMap;
Contrary to 0x01 if you have a lot of data manipulations and not many lookups a HashMap is multiple magnitudes faster as a BTreeMap.
0x10
As I struggled absent-minded with the borrow checker, I forgot the iter_mut() method.
Most containers have reference and mutable versions of their getter methods.
0x11
(-1 * is_4_dimensional as i64..=is_4_dimensional as i64)
Wherever you have a value which should be 0 when a boolean is false and otherwise the current value, you could improve your program with branchless programming.
fn cycle(active_cubes: &BTreeSet<Position>, is_4_dimensional: bool) -> BTreeSet<Position> {
active_cubes
.iter()
.map(|current_active| current_active.get_block(is_4_dimensional))
.flatten()
.unique()
.filter(|possible_cube| {
let is_active = active_cubes.contains(possible_cube);
let neighbors = possible_cube.get_neighbors(active_cubes, is_4_dimensional);
matches!((is_active, neighbors), (true, 2..=3) | (false, 3))
})
.collect()
}
As todays quest was to implement a multidimensional Conway’s Game of Life, I tried doing it in an expressive way, which could support even more dimensions.
0x13
Todays quest was really interesting, as it involved building a RegEx-like state machine, in order to validate/pattern-match strings. The sole technical difference is the easier to parse, but harder to read, rule-syntax.
fn check(&self, message: &str, next_rule: u32, paths: &mut Vec<u32>) {
if paths.is_empty() {
return;
}
match self.rules.get(&next_rule).expect("Rule not found!") {
Rule::Data(data) => {
*paths = paths
.iter()
.filter(|index| message.chars().nth(**index as usize) == Some(*data))
.map(|path| *path + 1)
.collect()
}
Rule::Meta(sub_rules) => {
*paths = sub_rules
.iter()
.map(|rule_chain| {
let mut next_paths = paths.to_vec();
rule_chain
.iter()
.for_each(|rule| self.check_internal(message, *rule, &mut next_paths));
next_paths
})
.flatten()
.collect();
}
}
}
This function traverses the rule-tree and permutates into any rule combination to save matching ones in the rule-paths variable.
0x18
A great visualization of Axial coordinates by Amit Patel.
The challenge was to walk in a hexagonal grid and identify the hexagons uniquely. In order to be unique, I changed the basis of the vectors to have only two components. I learned later, that this basis is called Axial coordinates.
0x19
I was pleased that the task was to break RSA/Diffie–Hellman.
fn discrete_logarithm(base: u64, divider: u64, result: u64) -> Option<u64> {
let base = base % divider;
let result = result % divider;
let big_step_size = (divider as f64).sqrt().ceil() as u64;
let big_values: HashMap<u64, u64> = (1..=big_step_size)
.map(|big_step| (pow_mod(base, big_step * big_step_size, divider), big_step))
.collect();
(1..=big_step_size)
.map(|baby_step| (baby_step, (pow_mod(base, baby_step, divider) * result) % divider)
.filter_map(|(baby_step, baby_value)| big_values.get(&baby_value)
.map(|big_step| big_step * big_step_size - baby_step))
.min()
}
As the message is public, the only unknown part was the exponent. The mathematical operation to invert the modular exponentiation is the discrete logarithm. There is no known efficient method of this problem, but I used the Baby-step giant-step algorithm, which is at least significantly more efficient than brute-forcing. 1
fn pow_mod(base: u64, exponent: u64, divider: u64) -> u64 {
(0..exponent)
.fold(1_u64, |value, _| (value as u128 * base as u128 % divider as u128) as u64)
}
This was my first attempt to implement a simple modular exponentiation. Woefully, this was way to slow as it started with the first iteration every time.
fn pow_mod_cached(base: u64, exponent: u64, divider: u64, mut exponent_cache: &mut HashMap<u64, u64>) -> u64 {
if exponent == 0 {
return 1;
}
let highest_cached_exponent = exponent_cache.keys().filter(|cached_exponent| cached_exponent <= &&exponent).max();
let result = match highest_cached_exponent {
None => pow_mod(base, exponent, divider),
Some(highest_cached_exponent) =>
(exponent_cache[highest_cached_exponent]
* pow_mod_cached(base, exponent - highest_cached_exponent, divider, &mut exponent_cache))
% divider,
};
exponent_cache.insert(exponent, result);
result
}
As the exponent grows linearly I, did memoization to have the highest cached exponent, which is smaller than the requested exponent and utilize this as a starting value. This brought the computation time down from 8 minutes to around 400 ms. 1
fn pow_mod(mut base: u64, mut exponent: u64, divider: u64) -> u64 {
let mut result = 1_u128;
while exponent != 0 {
if exponent % 2 != 0 {
result *= base;
result %= divider;
}
exponent = exponent >> 1;
base *= base;
base %= divider;
}
result as u64
}
But I retained something in mind and after a bit of searching I rediscovered the Right-to-left binary method. With this algorithm the calculation took only ≈ 7 ms. 1