Today is day 10 already! And it’s a pretty interesting one.

We’re dealing with sequences of numbers, and differences between those numbers. Each number needs to have a difference of 1, 2, or 3 with the previous one.

Parsing this list of numbers is trivial. For this problem, it helps to add 0 to that list (as it’s always the initial number to consider). And since we must consider them from 0 to their max value, it also helps to sort it:

data = [0] + [int(l) for l in raw_data.splitlines()]
data.sort()

Now let’s get serious.

Part 1: counting differences

In this first part, we need to check how many numbers are “previous number + 1”, and how many are “previous number + 3”. We can simply keep 2 counters and iterate over that list, comparing each number against the previous one.

However, spoiler alert! In part 2, we will also need a list of differences. So instead we’ll create a list by collecting each difference with the previous number. Then we can use a Python collections.Counter to count how many +1 and +3 we have:

from collections import Counter


def calculate_diffs(data: List[int]) -> List[int]:
    return [data[i] - data[i - 1] for i in range(1, len(data))]


diffs = calculate_diffs(data)
counts = Counter(diffs)
print(counts[1] * (counts[3] + 1))

Done. 0.03 ms.

Part 2: arranging adapters

This is way more interesting. We have a target value: max(data) + 3. Each “adapter”’s value must be the previous one plus 1, 2, or 3. And we can skip any adapter if we can still meet this constraint. How many ways are there to order our adapters to reach that value?

The puzzle correctly explains that there are more than a trillion ways to arrange those adapters. And we need to count them…

Brute force is always an option. Sounds easy enough: a counter, some back-tracking to explore all possible arrangements, and we should be good! Except that with more than 10^13 possibilities, that would take a very long time. So instead, we need to (try to) be smart.

Let’s consider a couple of examples. If our adapters are 1 2 3 4 7, we can use the following combinations: 1 2 3 4 7, 1 2 4 7, 1 3 4 7, 2 3 4 7, 1 4 7, 2 4 7, and 3 4 7. So with only 5 numbers we already have 7 possibilities.

If our adapters are 1 2 3 4 7 10 13 14 15 16, then we have all the previous ones but with any of the following endings: ...10 13 14 15 16, ...10 13 14 16, ...10 13 15 16, and ...10 13 16.

In total, we have 7×4=28 possibilities. Ouch.

Now, how can we calculate the number of arrangements without trying them all? The key is that the difference between two valid values must be 1, 2, or 3. So if we have exactly 3 consecutive numbers (0 **3 4 5** 8), we know that this will lead to 2 possible arrangements: 0 3 4 5 8 and 0 3 5 8.

Let’s rewrite this by considering the difference between each number and the previous one in our input list. 0 3 4 5 8 becomes 3 1 1 3 (and, from there, we can rebuild the original list easily). In those differences, we can notice a sequence of two 1s. This could be left alone or replaced with a single 2, which will lead to either 0 3 4 5 8 or 0 3 5 8.

Likewise, if we have a sequence of three 1s (111), we can replace it with any sequence of 1s, 2s, and 3s that sums to 3. So: 111, 12, 21, or 3. 4 possibilities.

And so on:

• 1111 –> 1111, 112, 121, 211, 22, 13, 31: 7 possibilities
• 11111 –> 11111, 1112, 1121, 1211, 2111, 122, 212, 221, 113, 131, 311, 23, 32: 13 possibilities
• etc.

Things get harder if we also need to consider differences of 2 (0 2 3 4 6), but my input doesn’t contain any. It also doesn’t contain longer sequences of 1s.

Once we know that, calculating the number of possible arrangements becomes much easier: each sequence of length 2 multiplies it by 2, of length 3 by 4, of length 4 by 7, and of length 7 by 13. Meaning that if we have 3 sequences of four 1s there will be 7^3=343 arrangements.

The resulting code looks like this:

from collections import defaultdict

def count_seqs_1(diffs: List[int]) -> Dict[int, int]:
    c = 0
    res = defaultdict(int)
    for n in diffs:
        if n == 1:
            c += 1
        else:
            if c > 1:
                res[c] += 1
            c = 0
    if c > 1:
        res[c] += 1
    return dict(res)


diffs = calculate_diffs(data)
seqs = count_seqs_1(diffs)

mults = {2: 2, 3: 4, 4: 7, 5: 13}
tot = 1
for l, n in seqs.items():
    tot *= mults[l] ** n

print(tot)

We can easily use it to validate the short examples from the puzzle.

And that’s it. Takes 0.02 ms to run. My answer: more than 2 trillion arrangements… Brute-forcing really wasn’t a good idea! 😅