Advent of Code 2020 - Day 10
Tags: adventofcode, python, puzzles
Published: 2020-12-25 14:08:25

https://adventofcode.com/2020/day/10 ('Adapter Array')

This felt like the first more difficult problem in this year's set.

Part 1 is relatively straightforward: as each adaptor must have a lower-rated adaptor on one side and a higher-rated one on the other, the only way to use all the adaptors is to sort them in ascending order. Having done this we can workout the differences between adjacent adaptors and from this count the number of 1s or 3s:
```python
def part1():
    adaptors = sorted(read_input())
    target = adaptors[-1] + 3
    adaptors = [0] + adaptors + [target]

    diffs = [adaptors[i + 1] - adaptors[i] for i in range(0, len(adaptors) - 1)]
    diff_1_count = sum(1 for d in diffs if d == 1)
    diff_3_count = sum(1 for d in diffs if d == 3)
    return diff_1_count * diff_3_count
```

Solving part 2 was a bit of a journey. My first instinct was to try a recursive solution:

1. Start with all the adaptors
2. Find the first adaptor in the list that can be removed (i.e. removing it wouldn't leave a gap bigger than 3 between the two adaptors that would become adjacent)
3. Create a copy of the list with the adaptor removed and recursively try to solve the same problem, removing only adaptors to the right of the one removed.
4. Go back to 2, looking for the next adaptor that can be removed.

This looks like:
```python
def count_ways(adaptors, start=1):
    if start >= len(adaptors) - 1:
        return 1
    count = 1
    for i in range(start, len(adaptors) - 1):
        # See if we can remove adaptor i
        diff = adaptors[i + 1] - adaptors[i - 1]
        if diff <= 3:
            # We can remove adaptor i, so see which ones to the right of it we can also remove
            new_adaptors = adaptors[:i] + adaptors[i + 1:]
            count += count_ways(new_adaptors, i)
    return count
```
where `adaptors[0]` is the socket and `adaptors[-1]` is the device.

My puzzle input had 108 adaptors in it so the number of possible combinations to be checked could be as high as 2^108, or about 10^33. Counting these one at a time wasn't going to get anywhere fast! Of course, the problem can be simplified but it took me some time to work out how. 

# Simplifying the Problem

Looking at the larger example given in the puzzle (with 19,208 possibilities) we have the following adaptors (including the socket and the device at either end):
```
0 1 2 3 4 7 8 9 10 11 14 17 18 19 20 23 24 25 28 31 32 33 34 35 38 39 42 45 46 47 48 49 52
```
We can tell that some of these adaptors can't be removed as they would leave a gap of more than three - and the socket and device obviously can't be removed. Marking these non-removable adaptors with brackets we get:
```
(0) 1 2 3 (4) (7) 8 9 10 (11) (14) (17) 18 19 (20) (23) 24 (25) (28) (31) 32 33 34 (35) (38) (39) (42) (45) 46 47 48 (49) (52)
```
The trick now is not to regard this as a single problem. Instead we split the list of adaptors up into sets that are bookended by adaptors that can't be removed:
```
(0) 1 2 3 (4)
(7) 8 9 10 (11)
(14)
(17) 18 19 (20)
(23) 24 (25)
(28)
(31) 32 33 34 (35)
(38) (39)
(42)
(45) 46 47 48 (49)
(52)
```
Provided that the resulting groups are small enough, counting the number of possibilities for each group independently and then multiplying the result for each group together should be a much faster way of producing the same result. Looking at the example above, we have five kinds of group:

* `(n)` - a group containing a single non-removable adaptor. There's only one possibility here as nothing can be removed.
* `(n), (n + 1)` - a group containing two non-removable adaptors. Again, only one possibility.
* `(n), n + 1, (n + 2)` - a group of consecutive integers with a removable adaptor in the middle. There are two possibilities as the middle adaptor can either be present or not.
* `(n), n + 1, n + 2, (n + 3)` - consecutive integers with two removable adaptors in the middle. Either, both or neither can be removed so there are four possibilities.
* `(n), n + 1, n + 2, n + 3, (n + 4)` - consecutive integers with three removable adaptors in the middle. In this case we can remove any combination of the middle adaptors as long as we don't remove all three at once (as the jump from `n` to `n + 4` would be too big). This gives 7 possibilities.

Working through the groups then, the number of possibilities are 7, 7, 1, 4, 2, 1, 7, 1, 1, 7 and 1 - and multiplying these together gives 19,208 as expected.

Splitting the adaptors into groups is just a matter of collecting subsequent adaptors until the gap is 3 or more:
```python
def split_adaptors(adaptors):
    group = []
    last_adaptor = adaptors[0]
    for adaptor in adaptors:
        if adaptor - last_adaptor >= 3:
            yield group
            group = []
        group.append(adaptor)
        last_adaptor = adaptor
    yield group
```
so part 2 becomes:
```python
from functools import reduce
from operator import mul

def part2_recursive():
    adaptors = get_adaptors()

    return reduce(mul, (count_ways(group) for group in split_adaptors(adaptors)))
```
(where the code to read the adaptors, sort them and add on the outlet and device at the beginning and end of the list has been pulled out into `get_adaptors()`).

Luckily the largest group in my puzzle input had five adaptors so this worked perfectly! For my input the result was 226,775,649,501,184, calculated in about 0.3ms.

However the story doesn't end here - there are other ways of solving the problem that I also ended up exploring, culminating in a very neat non-recursive method that seems almost like magic...

# Tribonacci Numbers

I noticed that the adaptors in my input were all either 1 or 3 apart - there were no differences of 2. This means that when split into groups book-ended by adaptors that can't be removed, each group is always of the form of `n` consecutive integers:
```
(x)   x + 1   x + 2   ...   x + n - 3   x + n - 2   (x + n - 1)
```
where `x` and `x + n - 1` are the non-removable adaptors.

I wondered whether rather than recursively calculating the number of possibilities using the `count_ways()` function from above there might be some kind of closed-form expression for the number of possibilities for a group of size `n`. Continuing on from above and working out the number of possibilities for groups of 6 or 7 adaptors by hand we get:

| Group size (`n`) | Possibilities |
|------------------|---------------|
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 4 |
| 5 | 7 |
| 6 | 13 |
| 7 | 24 |

I didn't spot the pattern straight away and instead entered the sequence into the [OEIS](https://oeis.org/). This turned up sequence [A000073](https://oeis.org/A000073), or the so-called [_tribonacci numbers_](https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers#Tribonacci_numbers). _If_ this pattern holds true for all cases, we should be able to calculate the nth tribonacci number fairly quickly using recursion. There's a formula for the nth tribonacci number but, just as for Fibonacci numbers, it relies on exponentiation of irrational numbers so will be limited by the accuracy of floating-point arithmetic.

For a group of `n` consecutive adaptors, the middle `n - 2` are removable. If we were allowed to remove any combination of adaptors there would be `2^(n - 2)` possibilities. However we are constrained by not being allowed to remove three or more consecutive adaptors. Finding the number of possibilities is therefore equivalent to finding the number of binary numbers of length `n - 2` that do not contain three consecutive zeros.

Let's say that `B(n)` is the number of binary numbers of length `n` that don't contain three consecutive zeros, so:
* `B(1) = 2` (i.e. 0 or 1)
* `B(2) = 4` (00, 01, 10 or 11)
* `B(3) = 7` (001, 010, 011, 100, 101, 110, 111, but not 000)
* `B(4) = 13` (16 combinations minus 1000, 0001 and 0000), etc.

Thinking about it, `B(n)` will contain binary numbers belonging to one of these categories:
* `1xxxxxx` (i.e. a 1 followed by an `n - 1` digit number that doesn't contain three consecutive zeros)
* `01xxxxx` (i.e. 01 followed by an `n - 2` digit number that doesn't contain three consecutive zeros)
* `001xxxx` (i.e. 001 followed by an `n - 3` digit number that doesn't include three consecutive zeros)

No numbers in `B(n)` can start with any other combination of digits (e.g. `0001`) as this would give them three consecutive zeros at the start. We can immediately see that the number of numbers in the first category is `B(n - 1)`, in the second is `B(n - 2)` and in the third is `B(n - 3)`, so we must have `B(n) = B(n - 1) + B(n - 2) + B(n - 3)` - which is the definition of the tribonacci sequence!

Having proved that number of possibilities for a group of adaptors of size `n` _do_ follow the tribonacci sequence, we can rewrite part 2 as:
```python
from functools import lru_cache, reduce
from operator import mul

def part2():
    @lru_cache
    def tribonacci(n):
        if n == 1:
            return 2
        if n == 2:
            return 4
        if n == 3:
            return 7
        return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3)

    def count(group_size):
        if group_size < 3:
            return 1
        return tribonacci(group_size - 2)

    adaptors = get_adaptors()
    return reduce(mul, (count(len(group)) for group in split_adaptors(adaptors)))
```
This is much simpler than before, though it's still recursive. The tribonacci numbers can be cached using the [`@lru_cache`](https://docs.python.org/3/library/functools.html#functools.lru_cache) decorator from the `functools` module to ensure we only calculate each one once (though in reality `tribonacci(n)` is only called with `n` equal to 1, 2 or 3 for the puzzle input, so there's not much repetition). This evaluates to the same result as the previous method, but in 0.2ms - so a slight improvement on the 0.3ms from before!

# Graphs - First Attempt

But we're still not done! So far we've regarded the adaptors as a set from which we can remove different combinations subject to certain rules. What if we think of the adaptors as a graph?

Let's regard each adaptor as a node in a graph with links to all the adaptors that could follow it (so adaptor 4 could have links to adaptors 5, 6 and 7 - if they exist - but not adaptor 8). Now solving the problem is equivalent to counting the number of routes through the graph from the socket to the device.

Constructing the graph is relatively straightforward, though it helps to have the adaptors as a `set` first:
```python
# Build a graph so that each adaptor lists the adaptors that
# could follow it.
adaptors = set(adaptors)
follows = {}
for adaptor in adaptors:
    following_adaptors = []
    # There are only three possible adaptors that this one 
    # could connect to
    for i in range(3):
        following_adaptor = adaptor + i + 1
        # Only link to adaptors that actually exist
        if following_adaptor in adaptors:
            following_adaptors.append(following_adaptor)
    follows[adaptor] = following_adaptors
```

Counting the number of routes through the graph is another recursive problem: the number of routes from a given node is equal to the sum of the number of routes from each of the nodes that follow it, with the final node counting as having 1 route:
```python
@lru_cache
def count_paths(start):
    if len(follows[start]) == 0:
        return 1
    return sum(count_paths(next_adaptor) for next_adaptor in follows[start])
```
Decorating the function with `@lru_cache` is definitely a good idea here as the counting process is likely to hit the same nodes repeatedly when tracing all the routes through the graph.

Now the answer is just a matter of calculating `count_paths(0)`. This takes about 0.7ms, so is slower than either of the above techniques. However it does feel conceptually cleaner, especially when compared to the complicated recursion in the `count_ways()` function used in the first approach.

# Graphs - Second Attempt

However this is one more step we can take - and this results in a solution which (to me at least) seems like wizardry.

Instead of counting the number of possible paths from a given node in the graph to the final node (the device), we can look at it the other way round and calculate the number of ways it's possible to get to a particular node. The overall answer would then be the number of ways of reaching the device at the end of the adaptor list.

The important thing to note is that each adaptor is unique (we don't have two adaptor 8s, say) and that adaptor `a` can only be connected to from adaptors `a - 1`, `a - 2` and `a - 3` (if they exist). As a result we don't need recursion at all: we can just start from 0 and work our way up through the adaptors in numerical order, knowing that by the time we've got to adaptor `a` we'll already have worked out the number of ways of getting to all the adaptors that could precede it!

So what does this magical solution look like? This is all it is:
```python
def part2():
    adaptors = get_adaptors()

    # We start the process by saying that there's one way to 
    # get to the start node.
    counts = {0: 1}

    for a in adaptors[1:]:
        # Number of ways to get to adaptor a is equal to the
        # sum of the number of ways of getting to a - 1, a - 2
        # and a - 3.
        counts[a] = counts.get(a - 1, 0) + \
            counts.get(a - 2, 0) + counts.get(a - 3, 0)

    return counts[adaptors[-1]]
```

No recursion, no `lru_cache`, completes in just over 0.2ms - why didn't I think of this to start with?