Module day20

Grove Positioning System

We store the numbers in an array of vecs. The initial size of each vector is 20 so that numbers are spread as evenly as possible.

Using multiple leaf vecs 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 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.

Leaf vecs are padded to a size modulo 64 to speed up searching for numbers. A SIMD variant can search for 64 numbers simultaneously.

Structs

PaddedVec 🔒

Functions

decrypt 🔒

parse

part1

part2

position 🔒

The compiler optimizes the position search when the size of the chunk is known.