day 10

so... this was a new record for the number of incorrect submissions, and one potential solution that has been described as "O(heat-death-of-the-universe)" because my first approach for part b was incredibly naive

the setup for both parts is the same: it reads in the input, breaks on line breaks to turn it into a list, turns each of these strings into integers, adds in the extra adapters (the socket at 0, and the device at max + 3), and then sorts these.

# input
with open('10.txt', 'r') as file:
    input = file.read()
# turn the input into a list, one element is one number as a string
input_list = list(input.split('\n'))
adapters = [int(n) for n in input_list]
adapters.append(0)
adapters.append(max(adapters) + 3)
adapters.sort()

part a is just counting the number of jumps of 1 or of 3 when using all adapters:

# count number of 1-jolt and 3-jolt differences
j1 = 0
j3 = 0
for i in range(0, len(adapters)-1):
    if adapters[i+1] - adapters[i] == 1:
        j1 += 1
    elif adapters[i+1] - adapters[i] == 3:
        j3 += 1
print(j1 * j3)

part b is seeing how many different combinations of adapters you can use, so any sublist of the original list such that the difference between any consecutive integers is at most 3 - do not try to approach this by looking at how many routes you have from each adapter..

anyway, after throwing away the exponential-time solution that *technically* would've worked with enough time, i tried to do a similar thing but broken down into smaller pieces - i categorised the adapters into vital and non-vital adapters, where vital adapters MUST be included (socket [0], device [largest joltage], and any adapter in-between that is either preceded or followed by a gap of 3 jolts) and non-vital adapters can be removed (there is at least one legal sequence without that adapter, but you might not be able to remove all non-vital adapters at once).

# look at the list of vital adapters
# (socket, device, or either side of a break of 3)
vital_adapters = []
vital_adapters.append(0)
for i in range(0, len(adapters)-1):
    if adapters[i+1] - adapters[i] == 3:
        # either side of a break of 3, and hasn't been added already
        if not i in vital_adapters:
            vital_adapters.append(i)
        if not i+1 in vital_adapters:
            vital_adapters.append(i+1)

after this, i defined a function that gives the number of possible arrangements between two vital adapters, based on how many non-vital adapters are in-between: there was nothing with a gap of 2 in the input, so i could assume that every jump between two adapters, where at least one is non-vital, is a jump of 1.

for the first few, this can be done by hand: there is 1 way if there are no non-vitals in-between (direct connection a to b); 2 if there is one (a o b, a . b); and 4 if there are two (a . . b, a o . b, a . o b, a o o b). i also included 0 ways if the input is negative (technically true, and this prevents infinite loops in case it goes below 0). beyond this, you can calculate the number of paths recursively by taking the sum of the number of paths with 1, 2, or 3 fewer non-vitals (corresponding to the gap between the first connection and the second).

to get the number of non-vital (nv) arrangements from the number of adapters between (nab) two vital adapters, this algorithm does it fairly naively (and exponentially), but the input is considerably smaller so it won't take forever:

# between two vitals a and b
def nv(nab: int):
    if nab < 0:
        return 1
    elif nab == 0:
        return 1
    elif nab == 1:
        return 2
    elif nab == 2:
        return 4
    else: # cannot jump directly, but can go to 1, 2, or 3 away
        return nv(nab - 1) + nv(nab - 2) + nv(nab - 3)

now you can calculate the total number of arrangements! since each of these groups of non-vital adapters is separated by the vital adapters, you can consider each of them separately, and then get the product of the arrangements of each group of non-vitals.

you start off with one arrangement (using every adapter), and then for each vital adapter with another vital adapter after it, you get the number of non-vital adapters in-between, and then multiply the total number of arrangements by the number of arrangements of this one group of non-vitals. once the for loop is done, you have the answer for b

num_arrangements = 1
for j in range(0,len(vital_adapters)-1):
    # for every vital adapter with a vital adapter after it
    nab = vital_adapters[j+1] - vital_adapters[j] - 1
    num_arrangements = num_arrangements * nv(nab)
print(num_arrangements)