# Advent of Code 2020: Day 10

Day 10 is about looking at a list of numbers. In the first part I’ll just need to make a histogram of the differences between the numbers when sorted. For part two, it’s the first challenge this year where I’ll need to come up with an efficient algorithm to handle it. I’m asked to come up with the number of valid combinations according to some constraints. I’ll use recursion to solve it, and it only works in reasonable time with caching on that recursion.

## Challenge

The puzzle can be found here. The puzzle input is a list of integers, though the problem states that there are implied values of zero and three larger than the largest value, so I’ll need to add those to the list. For part one, I’m asked to sort them and look at the delta between values, counting the number of times that is one and three. For part two, I’ve got the constraint that I can skip ahead as long as the values don’t jump by more than three. I’m tasked with finding the number of valid combinations.

The example given uses this list:

```
16
10
15
5
1
11
7
19
6
12
4
```

The number of valid combinations is eight:

```
(0), 1, 4, 5, 6, 7, 10, 11, 12, 15, 16, 19, (22)
(0), 1, 4, 5, 6, 7, 10, 12, 15, 16, 19, (22)
(0), 1, 4, 5, 7, 10, 11, 12, 15, 16, 19, (22)
(0), 1, 4, 5, 7, 10, 12, 15, 16, 19, (22)
(0), 1, 4, 6, 7, 10, 11, 12, 15, 16, 19, (22)
(0), 1, 4, 6, 7, 10, 12, 15, 16, 19, (22)
(0), 1, 4, 7, 10, 11, 12, 15, 16, 19, (22)
(0), 1, 4, 7, 10, 12, 15, 16, 19, (22)
```

## Solution

### Part 1

Part one was really straight forward. First I need a bit of work to prep the list. I’ll read it in, convert to ints, append zero and three plus the max, and sort. Now I’ll just use a list comprehension from one to the length of the list to get a list of the deltas, and a `Counter`

from collections to quickly count the number of each value. I can multiple the ones and threes count to get the answer:

```
with open(sys.argv[1], "r") as f:
adapters = list(map(int, f.readlines()))
adapters = sorted(adapters + [0, max(adapters) + 3])
diffs = [adapters[i] - adapters[i - 1] for i in range(1, len(adapters))]
hist = Counter(diffs)
print(f"Part 1: {hist[1] * hist[3]}")
```

### Part 2

This is the hardest challenge yet this year, because it forces you to think through the best algorithm to figure this out. The most obvious idea would be to generate all possible combinations of any length, and then throw away any that contain jumps of more than three. But there would be way too many to do that, and it would run forever.

Instead, I’ll use a recursive approach, creating a function that looks at an index in the list and figured out how many paths there are to the end from there. I’ll posit that from any given node, the number of paths to the end is the sums of the number of paths to the end for each of the nodes that could possibly come next.

I’ll use this example input: `(0), 1, 4, 5, 6, 7,(10)`

. If I start at the end of the list (`paths_to_end(6)`

), how many paths are there? Well…one. It’s a single node. Simple base case. Now I’ll step back one node (`paths_to_end(5)`

). The list is now `7, (10)`

. Still just one way to traverse the list. The same for `paths_to_end(4)`

.

Stepping back again is where it gets interesting. The list is now `5, 6, 7, (10)`

. From there, I could go `5, 6, 7, (10)`

or `5, 7, (10)`

. And thinking about this more generically, `paths_to_end(3) = paths_to_end(4) + paths_to_end(5)`

.

From this understanding, I can create a recursive function:

```
@lru_cache(maxsize=256)
def paths_to_end(i):
if i == len(adapters) - 1:
return 1
return sum(
[
paths_to_end(j)
for j in range(i + 1, min(i + 4, len(adapters)))
if adapters[j] - adapters[i] <= 3
]
)
```

If I’m at the last node, the number of paths is one. Otherwise, look ahead at the next three nodes (or to the end of the list, whichever is first), and for any that are valid jumps (value is no more than three more), find the number of paths from that node to the end.

For back to this example: `(0), 1, 4, 5, 6, 7,(10)`

i | nums[i] | paths_to_end(i) | Result |
---|---|---|---|

0 | 0 | paths_to_end(1) | 4 |

1 | 1 | path_to_end(2) | 4 |

2 | 4 | paths_to_end(3) + paths_to_end(4) + paths_to_end(5) | 4 |

3 | 5 | paths_to_end(4) + paths_to_end(5) | 2 |

4 | 6 | paths_to_end(5) | 1 |

5 | 7 | paths_to_end(6) | 1 |

6 | 10 | 1 | 1 |

I can work forward to fill in the third column, and once that’s done, work up from the bottom to generate the forth column to get the final answer.

### Final Code

With caching, this returns instantly:

```
$ time python3 day10.py 10-puzzle.txt
Part 1: 2080
Part 2: 6908379398144
real 0m0.056s
user 0m0.044s
sys 0m0.012s
```

```
#!/usr/bin/env python3
import sys
from collections import Counter
from functools import lru_cache
with open(sys.argv[1], "r") as f:
adapters = list(map(int, f.readlines()))
adapters = sorted(adapters + [0, max(adapters) + 3])
diffs = [adapters[i] - adapters[i - 1] for i in range(1, len(adapters))]
hist = Counter(diffs)
print(f"Part 1: {hist[1] * hist[3]}")
@lru_cache(maxsize=256)
def paths_to_end(i):
if i == len(adapters) - 1:
return 1
return sum(
[
paths_to_end(j)
for j in range(i + 1, min(i + 4, len(adapters)))
if adapters[j] - adapters[i] <= 3
]
)
print(f"Part 2: {paths_to_end(0)}")
```

### On Caching

Caching is critical for this piece. I used `lru_cache`

from functools, but I could have just as easily defined a dict outside the function, and at the end of the function, add the key / value `i`

/ `result`

to the dict. At the start of the function I could check to see if i was in the dict, and if so, returned the same value.

If I comment out the `@lru_cache`

decorator in the code above, my puzzle input runs for longer than I was willing to wait (I killed it after 30 minutes). So to illustrate this, I’ll add a counter outside the function, starting at 0, and then declare it as `global`

and increment it each time `path_to_end`

is called.

I’ll use two small examples from the challenge:

```
$ wc -l 10-test*.txt
11 10-test1.txt
31 10-test2.txt
42 total
```

With caching, the function is actually executed (as opposed to returning from cache) the length of input pus two times:

```
$ python3 day10.py 10-test1.txt
Part 1: 35
Part 2: 8
Called path_to_end 13 times
$ python3 day10.py 10-test2.txt
Part 1: 220
Part 2: 19208
Called path_to_end 33 times
```

If I comment out the caching, it goes up exponentially:

```
$ python3 day10.py 10-test1.txt
Part 1: 35
Part 2: 8
Called path_to_end 58 times
$ python3 day10.py 10-test2.txt
Part 1: 220
Part 2: 19208
Called path_to_end 76217 times
```