Advent of Code: Day #10 - Adapter Array

In to double digits, only 15 days left! Today we must dig through our great big bag of connectors to find the right combination to charge our laptop (Probably why we needed to bring so many bags on Day 7)!

For this task we are asked to use every single adapter we have in a big chain (definitely not a fire hazard) and calculate how many Jolt differences there are and return the product of the sum of 1 Jolt and 3 Jolt increases.

Reading in the data

We read the data into an array, append the starting joltage of 0 and the finishing joltage of our laptop (Maximum Joltage in the list +3) and then sort the array.

def read_data(path):
    dataset = []
    with open(path, "r") as file:
        for line in file.readlines():
            dataset.append(int(line.strip()))

    dataset.append(0)
    dataset.append(max(dataset) + 3)
    dataset = sorted(dataset)

    return dataset

The Solution

To solve this we iterate over all the adapters and calculate the jolt difference between the current adapter and the previous one. We then increment the value in the dictionary. Once we have iterated over all the chargers we return the product of the 1 Jolt and 3 Jolt totals.

def task_one(adapters):
    voltage_jumps = {1: 0, 2: 0, 3: 0}

    prev_voltage = adapters[0]
    for adapter in adapters[1:]:
        voltage_jumps[adapter - prev_voltage] += 1
        prev_voltage = adapter

    return voltage_jumps[1] * voltage_jumps[3]

The Solution

For task two we must find the total different combinations we can plug the adapters in (An adapter can plug into another if it has a jolt difference of 3). The number we expect is in the trillions so a brute force solution isn't going to work here (At least not in a sane amount of time). To get around this we can store a dictionary of paths we have found before, i.e once we have found the amount of combinations from the 8th adapter we can store that and the next time we see the 8th adapter we can just reuse that value instead of re-calculating it! This is known as dynamic programming.

def task_two(adapters):

    found_paths = {}

    def find_from(x):
        if x == len(adapters) - 1:
            return 1
        if x in found_paths:
            return found_paths[x]

        possibilities = 0

        for j in range(x+1, x+4 if x+4 < len(adapters) else len(adapters)):
            if adapters[j] - adapters[x] <= 3:
                possibilities += find_from(j)

        found_paths[x] = possibilities
        return possibilities

    return find_from(0)