The Day 10, the puzzle revolves around connecting “joltage” adapters to reach a desired target output. For part 1, the problem asks for the distribution of joltage differences in the input list. The input is a list of numbers:

16
10
15
5
1
11
7
19
6
12
4

With two implicit numbers: 0 and max(input) + 3. The answer to part 1 is the product of the number of 1- and 3-jolt differences. This can be found very effectively using the Counter class from the collections module:

nums.insert(0, 0)
nums.append(nums[-1] + 3)
p1_start = datetime.now()
diffs = []
for i in range(len(nums) - 1):
    diffs.append(nums[i + 1] - nums[i])
c = Counter(diffs)
p1 = c[1] * c[3]

For part 2, only joltage differences of 3 or less are usable, and the puzzle asks for the number of distinct combinations that can be made. This number rapidly becomes too large to count by simple iteration, but it does lend itself to solution with a dynamic programming algorithm. Dynamic programming problems are good for instances where the solution for one part is dependent on the solution for another part, and where a normal iterative or recursive method would repeat calculations. Dynamic programming algorithms always have a “grid” or “table” that tracks previous answers for use in larger parts of the problem. The grid is then iteratively filled, using the previous answers where possible:

states = []
grid = {n: 0 for n in nums}
grid[0] = 1
if args.visualize:
    states.append(GridState(deepcopy(grid)))
for num in nums[1:-1]:
    grid[num] += grid[num - 1] if num - 1 in grid else 0
    grid[num] += grid[num - 2] if num - 2 in grid else 0
    grid[num] += grid[num - 3] if num - 3 in grid else 0
    if args.visualize:
        states.append(GridState(deepcopy(grid)))
p2 = grid[nums[-2]]

This problem lends itself to being nicely visualized: