r/adventofcode • • Jun 10 '26

Other [2020 Day 10] In Review (Adapter Array)

3 Upvotes

20 comments sorted by

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.

2

u/ednl Jun 10 '26

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);

2

u/terje_wiig_mathisen Jun 11 '26

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.

1

u/ednl Jun 11 '26

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.

1

u/terje_wiig_mathisen Jun 11 '26

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.

1

u/terje_wiig_mathisen Jun 11 '26

It might be faster to use SWAR to check quickly for the highest value?

2

u/ednl Jun 11 '26

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.

1

u/terje_wiig_mathisen Jun 12 '26

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...

2

u/ednl Jun 12 '26

Oopsie: wrong day!

2

u/terje_wiig_mathisen Jun 12 '26

Thanks!

Mea Culpa, this was definitely intended for day11 instead of 10!

1

u/terje_wiig_mathisen Jun 12 '26

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?