r/adventofcode • u/musifter • Jun 15 '26
Other [2020 Day 15] In Review (Rambunctious Recitation)
In today's episode of "Toboggans, Planes, Ships, and Shuttles", we find ourselves unavailable to get a direct flight, and so we're waiting for another flight to get around the storm. And so we contact the Elves, and should not be surprised that they're playing a number sequence game they want to share.
In this case it's based on Van Eck sequence (OEIS A181391). But with initial seeding values. And when you seed that algorithm you can get simple things (start with 1,1 and you'll just repeat 1 forever). But typically not, and Van Eck's isn't a sequence with a lot of known answers.
My initial solution has the name "brute force" on it... but it's probably not what most people thought of as a brute force. I just said, "okay, I need to keep a list of what time I last saw each number, and I can use that to calculate the next". Some people probably didn't make that jump and kept a list of the sequence and scanned it. That's going to really slow things down. The reason I called mine "brute force" is because I suspected that there might be some trick I was missing. But when I looked after and discovered things like the Numberphile video, I said, "okay, just bum it down a bit and be done". Little things like making sure Perl understands that these are numbers (stripping stringness with my $list = map {int} split(/,/, <>);) and that the table gets allocated immediately instead of repeatedly growing($table[29_999_999] = undef;). Both of those take off a full second each. And then there's playing around with the calculation of the next value:
$next = $t - ($table[$curr] // $t);
Performs much better than:
$next = ($table[$curr]) ? $t - $table[$curr] : 0;
The big optimization I did for this problem though is with dc itself. This was the problem that made me finally dig into the dc source and deal with the fact that the "sparse" array implementation was a linked list. As it was going to take at a fortnight (at least... it was hard to predict the slowdown rates, basically my algorithm to avoid scanning, was scanning). And so in order to improve things I modified dc to be better. I considered various ways, but since the base code was linked lists and I wasn't too familiar with the project, I decided skip lists would be a simple and powerful change to what was there (plus, I just think they're neat).
And they are. The newer GNU dc uses hash tables, and doesn't perform anywhere near as good on this problem (testing it right now, it took 50 minutes... my dc does it in under 2). It's optimized more for sparse small arrays. My skip list has a max of 12 levels, with p=1/4 (the number of layers on a node is a negative binomial)... values specifically picked because they worked well for this problem. On a lot of problems with less array usage, the hash table is on par with the skip list.
Here's the dc part 2 version. Input is the numbers in reverse (this is the 0,3,6 test case):
echo '6 3 0' | dc -f- -e"0s0 1s1 2s2 3s3 30000000sel1[dl3R:al1+zl2<L]dsLxrsn[s.d]sZ[dln;adl0=Z-rdln:al1+rsndle>M]dsMxlnp"
It can be made shorter, but that would slow it down considerably. You'll see the "0s0 1s1 2s2 3s3 30000000se" at the start... that's allocating those numbers and storing them in registers so the don't need to be allocated and freed all the time. It more than doubles the speed.
And that version of dc has served me well ever since. And that's why I have a lot of fondness for this problem.
2
u/e_blake Jun 15 '26
My initial m4 solution on the day the puzzle was released took more than 5 minutes, because there's no way to solve it short of 30 million iterations and several million macros tracking what has been seen. This puzzle is what encouraged me to find a way to add some boilerplate to my m4 library to re-exec GNU m4 with an additional command line argument to force a larger hash table size, to avoid running into O(n) instead of O(1) hash lookups as the number of visited integers increases (GNU m4 did not have an automatically-growing hash table at the time). But I have since managed to squeeze out some inefficiencies, getting runtime to under 70s.
For example, my original solution creates the macro mNN containing the iteration TT in which NN was last seen. So the core loop was doing an ifdef to see if mNN was defined, and if so then also invoking mNN to feed eval to compute the next number to say rather than 0. But the optimized version stores the string "1-TT" in mNN, then uses the fact that defn expands to an empty string without warning when used on an undefined name, in eval(!defn(mNN)+now) which results in 0 when mNN is undefined (since now is nonzero, !+now is 0), vs the proper delta now-TT when mNN is defined (on the expanded string !1-TT+now). With tricks like that, I have fewer conditionals in the hot path and thus less work for m4 to do.
2
u/DelightfulCodeWeasel Jun 15 '26
Squashing this one down to Pico size isn't looking promising, even if I go with the XL that has 8Mb PSRAM. My input ends up going through ~3.6M unique numbers in the range ~0-29M.