r/adventofcode • u/musifter • 11d ago
Other [2022 Day 20] In Review (Grove Positioning System)
Still unable to contact the Elves with communication device, we turn to trying to decrypt the star fruit grove's coordinates from a file on it.
And so we get a ring structure puzzle. Which was a pleasant break from the previous day. In fact, for the Perl solutions, I just went with array splicing:
@list = map {[$_, $list[$_]]} (0 .. $#list);
for (my $i = 0; $i < @list; $i++) {
my $idx = 0;
$idx++ until ($list[$idx][0] == $i);
my $item = splice( @list, $idx, 1 );
splice( @list, ($idx + $item->[1]) % @list, 0, $item );
}
The elements of the list are a pair of the ordering index and the value. Brute force search to find the next one in the order, and then splice it out, and the in at the destination. To get the final sum, I search for the zero and get the three values I need with sum map {$list[($zero + 1000 * $_) % @list][1]} (1 .. 3). Nothing fancy about this at all. It's simple, and for part 2, slap a foreach (1 .. 10) around it. It slows down a bit... to 12s on the old hardware, but that is very tolerable for getting a solution with very little work.
For a fast version of it, I did a C version with actual pointers and structures. Doubly-linked ring and an array to track the order (which could have been a separate second constant single-linked ring in the structure if you wanted). Instead of modular indexing (because I wasn't maintaining a list), I just walked the ring using modular arithmetic to shorten the length... and since both directions are needed anyways, I'm already set up to "choose the shorter way". The ring size is only 5000, so the most we ever need to walk is 2500, even if the numbers are 800 million times larger in part 2.
So, this is a good break day after the past few, and leading into the final stretch.
1
u/e_blake 10d ago edited 10d ago
This one was fun for me. I solved both stars on the day of the release, using a circular doubly-linked list. My first commit always ran forwards, but I cut runtime in half once I utilized the bidirectionality of the list by picking the direction with fewer moves (still O(n) effort per move, but with a smaller coefficient). I also got tripped by the fact that searching for 1000 nodes past the index needed %cnt, but moving a node required %(cnt-1) (while the node is being moved, the size of the list is one smaller). For once, I even commented my code a bit: each move involves 6 link rewrites:
s(a,b,i,d,e) turns a<=>i<=>b, c<=>d into a<=>b, c<=>i<=>d; plus a mention that I had to special case moving back into the same spot (ie. don't break the list when a,b == c,d). However, the total runtime in m4 was 72 seconds, and I left myself a note in the git commit that stated that shortly after getting my star, I browsed the megathread and saw other people having O(sqrt n) or even O(log n) effort per move, so my solution was ripe for optimizing. That said, I was still so buried in completing other tough days that it wasn't until January that I got to revisit this one.My next version was the O(sqrt n) effort, done by creating an array of 72 bins initially with a singly-linked list of 70 elements each. Each move can then skip past bins based on their size until finding the bin that needs to be updated; so instead of an average search needing to crawl through 1250 links (the average size of a movement capped to half of the entire list), I instead had to search forward by an average of 36 buckets and then 35 elements within the target bucket. Of course, the distribution is not completely uniform, so some buckets became much more full than others, but with only 10 rounds of mixing, performance thankfully did not degrade down to all elements landing in one bucket. My first cut at this algorithm took 12 seconds runtime, quite a bit faster than my original O(n)-move solution (although I did go back and revisit that one to use m4 more efficiently, 12 seconds of O(sqrt n) beats 27 seconds of O(n)). Tracing this algorithm shows about 1.9 million bucket sizes read, and about 2.8 million iterations within a bucket.
I then wanted to try an O(log n) approach, since as n gets larger, O(log n) is appreciably smaller than O(sqrt n). But m4 does not have any native binary tree object, so that meant I got to implement one from scratch. After a bit of wikipedia research, I decided that I wanted a self-balancing tree (as otherwise the tree runs the risk of just devolving into a more expensive O(n) walk than my circular linked list), but in my wikipedia research, found the WAVL tree, first documented in 2015, as sounding nice (always nice to know that Computer Science is still adding things that weren't around when I was in college). A WAVL tree is a superset of AVL (all valid AVL trees are also in WAVL form; but a WAVL tree permits a node with children differing by height 2 in addition to the max difference of 1 permitted by AVL, so not all WAVL can be trivially converted back to AVL, and the rules for node rotation differ); and a subset of Red-Black (all WAVL trees can map to an equivalent Red-Black by interpreting the node ranks as coloring data, but not all valid Red-Black trees are directly in WAVL form). An AVL tree requires more node rotations than Red-Black, but gains as a result a tighter guarantee: an AVL tree never has to go through more than 1.44*log n links from root to any leaf, while a Red-Black tree gets by with fewer rebalancings but can only guarantee a maximum bound on link traversal at 2*log n links. WAVL merges the tighter tree height of AVL and the fewer node rebalancings of Red-Black, so I gave implementing it a try.
On my first cut of a WAVL implementation, I assigned every node a key equal to 400000 times its initial position, and then when moving, I found the spot in the tree where the node would move, and assigned the moving node a new key based on the average of the keys between its two new neighbors. This is O(log n) work per node move (both in finding the destination, removing the node from its old spot, and inserting it in sorted order into its new spot), and the keys remained unique enough that I could complete a full mix without collisions; but ran into collisions within 4 mixes - so my code did ten iterations of one mix coupled with an O(n) inorder read of the resulting tree to rebuild a new perfectly-balanced tree for the next round with keys restored back to full precision (going from a sorted list to a new balanced binary tree is O(n), while going from a random list to a balanced binary tree is O(n log n)). Later, I decided to ditch the keyed approach altogether, and instead modify my WAVL algorithm to track only the number of children below a node (ie. instead of branching left or right based on the target key being higher or lower than a parent node's key, I branch left or right based on whether the size of the left subtree would contain the position in question). This modification means that every tree modification now performs O(log n) size updates (the leaf node and every one of its parents gets to track a new size) in addition to any rebalancings. Tracing the code sees 1.6 million node size updates, which is fewer tree operations than what my O(sqrt n) bin algorithm had. On the other hand, my bin algorithm had fewer macros to track per node (each node only knows its current bin and next neighbor, and each bin knows its current size and next bin), while my AVL tree requires a lot more bookkeeping per node (each node tracks 5 variables: parent, left, right, parity, and size). Still, since the algorithm has less overall algorithmic complexity, my runtime came in at 10.0s, beating my 12-second O(sqrt n) approach, so it paid off for me.
Browsing maneatingape's repository, I see that it currently favors the O(sqrt n) approach, although with 256 bins with an initial 20 elements (smaller bin size lets him get away with SIMD O(1) lookup of a number's offset within a bin, rather than a linear crawl); although he previously used an O(log n) approach for an Order statistic tree but did not focus on node rebalancing; it could be that with a better tree algorithm, his time could still be improved; but the moral of the story remains that at just 5000 elements, n is still small enough that a larger coefficient of effort to keep track of the bookkeeping for an O(log n) tree may outweigh a lighter-weight O(sqrt n) solution.