AoC 2020 D10: Adapter Array

Python | Problem statement | Source code | Tags: MemoizationDynamic programming

← Previous Back to AoC Index Next →

Part 1

The problem essentially asks us to arrange some numbers into a non-decreasing sequence such that the difference between adjacent numbers is at most 3. We can sort the input numbers and prepend a 0 (the charging outlet) and append adapters[-1] + 3 (the device's built-in adapter). Then, we can just count the differences. NumPy makes this easy:

adapters = sorted(map(int, data))
adapters = [0] + adapters + [adapters[-1] + 3]
diffs = np.diff(adapters)
ones = np.sum(diffs == 1)
threes = np.sum(diffs == 3)
python

Part 2

I'm reluctant to call it Dynamic programming (what is dynamic programming anyway, if not just memoized recursion?), but that's the basic idea. Thinking recursively, the number of ways to reach a given adapter joltage is the sum of the number of ways to reach the previous 3 adapter joltages (if they exist):

ways(j)={0 if j∉adapters1 if j=min⁡(adapters)ways(j−1)+ways(j−2)+ways(j−3) otherwise\mathit{ways}(j) = \begin{cases} 0 &\text{ if } j \not\in \mathit{adapters} \\ 1 &\text{ if } j = \min(\mathit{adapters}) \\ \mathit{ways}(j - 1) + \mathit{ways}(j - 2) + \mathit{ways}(j - 3) &\text{ otherwise} \end{cases}

We can implement this directly with a recursive function, but it will recompute the same thing many times (for example, ways(5) is depended on by ways(6), ways(7), and ways(8)). The simple solution is to add a memoization layer such as a dictionary or @functools.cache. However I'm usually cautious about recursion due to stack depth limits, so I prefer to use a DP table instead:

ways = {adapters[0]: 1}
for adapter in adapters[1:]:
    ways[adapter] = (
        ways.get(adapter - 1, 0)
        + ways.get(adapter - 2, 0)
        + ways.get(adapter - 3, 0)
    )
python

Now the answer is ways[adapters[-1]].

← Previous Back to AoC Index Next →