Module aoc::year2022::day20

Grove Positioning System

We store the numbers in a triple nested vec of vec of vec. The initial size of each vector is ∛5000 ~= 17, so that numbers are spread as evenly as possible.

Numbes are stored in the leaf vecs. This greatly reduces the time to insert, remove and find numbers, compared to storing all numbers in a single flat vec. Some further optimizations:

• The first and second level indices of a number change only when it moves, so these can be stored in a lookup array for fast access.
• The size of each first level vec is the the sum of the second level vecs contained inside. This is stored in the skip array to prevent recomputing on each move.

This implementation is both faster and simpler than the previous version (preserved in the commit history) that used an order statistic tree, although perhaps adding balancing rotations to the tree would make it faster.

Functions

• decrypt 🔒
• parse
• part1
• part2