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.

``````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.

``````(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.

``````struct RingAdderSequence {
next: u64,
step_width: u64,
modulus: u64,
}

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)
``````

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
``````

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.

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.

``````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;
}
return 1;
}

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.

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.

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.

``````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`.

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.

``````(-1 * is_4_dimensional as i64..=1 * 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);
match (is_active, neighbors) {
(true, 2..=3) => true,
(false, 3) => true,
_ => false,
}
})
.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.

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;
}
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.

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.

``````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

1. The factors are casted to `u128` and after the modulo casted back to `u64` like in the simple `pow_mod`-example. The original source code can be found here and here. ↩︎