'''
To completely determine whether you have enough adapters, you'll need to figure out how many different ways they can be arranged. Every arrangement needs to connect the charging outlet to your device. The previous rules about when adapters can successfully connect still apply.

The first example above (the one that starts with 16, 10, 15) supports the following arrangements:

(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)
(The charging outlet and your device's built-in adapter are shown in parentheses.) Given the adapters from the first example, the total number of arrangements that connect the charging outlet to your device is 8.

The second example above (the one that starts with 28, 33, 18) has many arrangements. Here are a few:

(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)

(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, 49, (52)

(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, 48, 49, (52)

(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, 49, (52)

(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, 47, 48, 49, (52)

(0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45,
46, 48, 49, (52)

(0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45,
46, 49, (52)

(0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45,
47, 48, 49, (52)

(0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45,
47, 49, (52)

(0), 3, 4, 7, 10, 11, 14, 17, 20, 23, 25, 28, 31, 34, 35, 38, 39, 42, 45,
48, 49, (52)
In total, this set of adapters can connect the charging outlet to your device in 19208 distinct arrangements.

You glance back down at your bag and try to remember why you brought so many adapters; there must be more than a trillion valid ways to arrange them! Surely, there must be an efficient way to count the arrangements.

What is the total number of distinct ways you can arrange the adapters to connect the charging outlet to your device?
'''

def getDifference(joltageList, firstIndex, secondIndex):
    if not (secondIndex < len(joltageList)):
        return 9999999999
    return joltageList[secondIndex] - joltageList[firstIndex]

def getOptions(joltageList, currentIndex):
    searchIndex = currentIndex + 1
    result = []
    while getDifference(joltageList, currentIndex, searchIndex) <= 3:
        result.append(searchIndex)
        searchIndex += 1
    return result

def getNumOptions(joltageList, currentIndex):
    return len(getOptions(joltageList, currentIndex))

def findNumberOfPaths(joltageList, startIndex, endIndex):
    if startIndex == endIndex:
        return 1
    nextOptions = getOptions(joltageList, startIndex)
    totalOptions = 0
    for nextOption in nextOptions:
        totalOptions += findNumberOfPaths(joltageList, nextOption, endIndex)
    return totalOptions

joltages = []

with open("Data\input.txt", "r") as inputFile:
    for joltage in inputFile:
        joltages.append(int(joltage))

joltages.append(0)
joltages = sorted(joltages)
joltages.append(joltages[-1] + 3)

partitions = []

currentPartition = set()
for index in range(len(joltages) - 1):
    if getNumOptions(joltages, index) > 1:
        currentPartition.add(index)
        currentPartition.update(getOptions(joltages, index))
    else:
        if len(currentPartition) > 0 and getNumOptions(joltages, max(currentPartition)) == 1:
            partitions.append(currentPartition)
            currentPartition = set()

totalPaths = 1
for partition in [sorted(part) for part in partitions]:
    totalPaths *= findNumberOfPaths(joltages, partition[0], partition[-1])

print(totalPaths)