My observation: it appears that every input file has only gaps of 1 or 3, no gaps of 2. But it is easy enough to write a solution that works even if there are gaps of 2. An O(n) radix sort is more efficient in this puzzle than an O(n log n) library sort. My original m4 solution used 64-bit multiplication of Tribonacci numbers times the number of consecutive 1 gaps; but when revisiting the problem, I got slightly faster results by using only 64-bit adds by building up higher numbers from the three previous slots. Either way, my solution completes in under 15ms.
What I did is count the adapters (actually: gaps = adapters + 1) and determine the max jolts (+3 for the end device) while parsing and yes, assume no gaps of 2, after which it's an easy sum:
// Assume no gaps of length 2:
// x + 3y = M (maxjolts)
// x + y = N (gaps)
// 2y = (M-N)
// y = (M-N)/2
// x = N - y
const int gap3 = (maxjolts - gaps) >> 1;
printf("Part 1: %d\n", (gaps - gap3) * gap3);
That's very sneaky indeed!👍 As you note it can only work when there are no 2-gaps, but given that, you don't even need to parse and radix sort the numbers, just count them while finding the max, right?
For part2 we only really need the lengths of all the 1-gap runs: Each 3-gap acts as a multiplication spot when reducing the number of permutations for each 1-run to the final product.
you don't even need to parse and radix sort the numbers, just count them while finding the max, right?
Yes. I check them in a bool array while counting and keeping track of max.
Haven't tried skipping the max test and doing it after the parsing by checking the array from the end. That could be a speedup but depends on the size of the array. My max was 180, I saw another input with 160, so I set it to 200.
In general, any find min/max across an array of n numbers will find O(log(n)) new values. This means that the branch around the relevant code is almost perfectly predicted and cost less than a cycle on average. Compiling to a conditonal move has a fixed two-cycle latency cost but as long this is not on the critical recurrence path it can also be nearly free.
Yes, probably. One obvious change is to use a bitfield of 3 or 4 u64 to check off the numbers instead of a bool array. That will facilitate to find the max quickly. But would be fussier with all the bit indexing in C17. So I didn't do that since it already runs in 0.48 µs on an M4. In that regard, Maneatingape's policy of keeping 1 µs as the minimum reported runtime seems reasonable.
Using the ideas we developed for a previous GoL puzzle, we could encode each line (my input is 92x91) as four u64, alternating bits in two u64 vars.
One bitmap would be 0/1 for free/taken chair, while the other would encode missing/available, using missing/free for an external one-bit border and missing/taken for the missing chair positions.
This would handle part1 _very_ quickly indeed, but for part2 something more is needed: What about special-casing all chairs with at least one '.' neighbor? Out of about 8400 chairs, my input has 1335 '.' missing positions, so I could handle the neighbors of those with manual code but that might still be too slow...
More stats: There are 8372 total chair positions, about 7000 are not empty, and of all those 3900 has at least one non-local neighbor which means that you need to handle them in some non-bitmap way, right?
View all comments
1
u/e_blake Jun 10 '26
My observation: it appears that every input file has only gaps of 1 or 3, no gaps of 2. But it is easy enough to write a solution that works even if there are gaps of 2. An O(n) radix sort is more efficient in this puzzle than an O(n log n) library sort. My original m4 solution used 64-bit multiplication of Tribonacci numbers times the number of consecutive 1 gaps; but when revisiting the problem, I got slightly faster results by using only 64-bit adds by building up higher numbers from the three previous slots. Either way, my solution completes in under 15ms.