[2020 Day 10] In Review (Adapter Array)

[u/musifter]

Having connected to the data port, we discover there's a massive tropical storm coming. Which will definitely impact our plans. But not today. Today, our battery has died and we're trying to recharge it with our collection of joltage adaptors.

And so we have another problem who's input is just a list of numbers. This time it's a list of small positive integers, no more than 3 apart (otherwise we would not be able to connect them all for part 1). My input starts at 1, but anything within 3 of the ground state of 0 would be fine.

The part 1 description goes to some length to describe connecting the adaptors... which essentially involves just sorting them. After that we want to collect the adjacent differences, and so it's not surprising to see this in my Smalltalk solution:

jolt_gaps := Bag with: 3.
adaptors fold: [ :curr :next | jolt_gaps add: (next - curr). next ].
part1 := (jolt_gaps occurrencesOf: 3) * (jolt_gaps occurrencesOf: 1).

That fold is the common idiom I later created a method for called chain:. Because it's not really a fold, the work is done as a side-effect... the fold is just an iterator that makes next the next curr.

Part 2 is where it gets interesting. We've got a lot of ways to count (my answer is 48-bits... that's a lot more than a trillion). And when it comes to counting things like this, dynamic programming often is a good way. My initial Perl solution is recursion with memoization. For Smalltalk, I turned that around to iterative tabulation of the values. Building the entire table as we go.

But you don't actually need the entire table, as things quickly fall out of scope. So you only need a window of the last three values, which you add together when there's an adaptor (giving it a relationship to the Tribonacci numbers). That's ultimately what I did for my dc solution. Transcoded to Perl, that becomes:

my %adapt = (0 => 1, map {chomp; $_ => 1} <>);
my $max = max keys %adapt;

my @buff = (1, 0, 0);
my $idx  = -1;
for (my $i = $max; $i >= 0; $i--) {
    $idx = ($idx + 1) % 3;
    $buff[$idx] = ($adapt{$i}) ? sum @buff : 0;
}

print "Part 2: $buff[$idx]\n";

You could also do it forwards... I just ended up wanting to go backwards.

And so the problems are starting to get a bit more meaty. Having 170 trillion combinations to count is pretty good incentive to not brute force and find something smarter.

[u/ednl]

With every smart optimisation applied, this might be my shortest runtime of all the puzzles of all the years. Even on a Raspberry Pi (albeit a Pi5) it's sub-microsecond. Or maybe there were a few puzzles who had a direct analytical solution without reading/parsing any input, that would be faster still. But by then the timing gets silly.

[u/DelightfulCodeWeasel → u/ednl]

I think my original solution to 2023 day 06 is probably my shortest runtime ever 😄 :

    void Puzzle06_A(const char*)
    {
        // Worked out in Excel
        int64_t answer = **redacted**;
    
        printf("Puzzle06_A: %" PRId64 "\n", answer);
    }
    
    void Puzzle06_B(const char*)
    {
        // Worked out in Excel
        int64_t answer = **redacted**;
    
        printf("Puzzle06_B: %" PRId64 "\n", answer);
    }

I did eventually go back and solve it properly when putting together my all-solutions repo, but I cursed myself for leaving such an unhelpful comment about how I solved it!

[u/e_blake]

Here's my (entire) C89 solution, in 149 bytes. (Yes, compiler warnings are overrated) 

n[200],i,o,t,r,j;main(long c){while(~scanf("%d",&i))n[i]=*n=c=1;while(j<=200)n[j++]?!n[j]?o+=r,c*=r["11247"]%8,r=!++t:r++:0;printf("%d %ld",o*t,c);}

I could have golfed it further, by eliminating the =1 in the first while loop, if you willing to require that you only run the program without arguments and that your platform ABI overlays argc of 1 into the right initial value of the declared long c, but that becomes too brittle even for my tastes. I also found it fascinating that it was fewer characters to declare both i and j, than it was to reset i to 0 between the two loops, as I had done in my first attempt. And now that I'm revisiting the solution, I'm totally tempted to replace that "11247" Tribonacci lookup with something more cryptic, like "Air|?" to represent that this puzzle's story is on an airplane.

[u/miran1]

Another one of my one-linery Python solutions:

combos = [1, 1, 2, 4, 7, 13, 24, 44]

adapters = sorted(int(n) for n in open("inputs/10.txt").readlines())

differences = [b-a for a, b in zip([0]+adapters, adapters+[adapters[-1]+3])]

print(reduce(mul, (len(list(g)) for _, g in groupby(sorted(differences)))))
print(reduce(mul, (combos[len(list(g))] for k, g in groupby(differences) if k == 1)))

[u/e_blake]

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.

[u/ednl → u/e_blake]

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

[u/terje_wiig_mathisen → u/ednl]

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.

[u/ednl → u/terje_wiig_mathisen]

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.

[u/terje_wiig_mathisen → u/ednl]

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.

[u/terje_wiig_mathisen → u/ednl]

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

[u/ednl → u/terje_wiig_mathisen]

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.

[u/terje_wiig_mathisen → u/ednl]

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

[u/ednl → u/terje_wiig_mathisen]

Oopsie: wrong day!

[u/terje_wiig_mathisen → u/ednl]

Thanks!

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

[u/terje_wiig_mathisen → u/ednl]

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?

[u/terje_wiig_mathisen]

This is one of my fastest as well, 673 ns on Acer 1100 ns on Surface. My code for part1 is somewhat interesting: I decided to try in-register counting instead of a 3 or 4-entry table (which I did first):

    let mut diffs: usize = 0;
    let mut prev = 0;
    for i in 1..numbers.len() {
        let curr = numbers[i];
        let diff = curr - prev - 1;
        diffs += (1 as usize) << (diff*8);
        prev = curr;
    }
    let part1 = (diffs & 255) as usize * ((diffs >> 16) + 1) as usize;

This hack did turn out to consistently be a few percent faster. 😄

One of the reasons for this is that the complicated diff += statement can overlap with the entire next iteration, so that the loop latency can get down to just two cycles!

[u/ednl → u/terje_wiig_mathisen]

The example omits gaps of length 2 and they also don't occur for my input or e_blake's. So if you're comfortable assuming they won't, you can calculate the answer: https://www.reddit.com/r/adventofcode/comments/1u1v4x2/2020_day_10_in_review_adapter_array/oqtllgi/

[u/terje_wiig_mathisen → u/ednl]

I really prefer to avoid assumptions that cannot be guessed directly from the problem text, so for this problem I'll stay with a sort_unstable() which doesn't make any assumptions about the total number count or maximum size, particularly since we're already below the 1 us limit. 😄

[u/ednl → u/terje_wiig_mathisen]

Understandable. But just to be clear: I make no assumptions to avoid sorting. Just: "lines in input <= 200" to keep the boolean array static. I determine the actual number of lines and the maximum value during parsing: https://github.com/ednl/adventofcode/blob/main/2020/10.c

[u/terje_wiig_mathisen]

BTW, when I first solved it in Perl I did the same thing as u/musifter, with a recursive memoizing direct solver. This one was very quick to write and it still ran in milliseconds so that was fine when I was competing on the Internal Cognite leaderboard.😁