adapter array

approach

the adapters are sorted once. part 1 tallies the differences between neighbours (including the jump from the outlet to the first one) into a three-slot list, and multiplies the 1-jolt count by the 3-jolt count plus one for the device's built-in adapter.

part 2 counts valid arrangements without enumerating them. the chain splits into runs of adapters that are 1 apart; a 3-jolt gap can never be skipped, so each run can be counted on its own and the results multiplied. the number of ways through a run of length n follows a tribonacci-style recurrence, dp(n-1) + dp(n-2) + dp(n-3), memoized with lru_cache.

the trick

3-jolt gaps are fixed points: count the ways through each run of consecutive adapters and multiply.

@lru_cache
def dp(n):
    if n <= 2:
        return 1
    elif n == 3:
        return 2
    return dp(n - 1) + dp(n - 2) + dp(n - 3)