Untitled

from collections import defaultdict, deque


def read_input(filename):
    with open(filename, 'r') as f:
        input = f.readlines()
        rules = []
        subsequences = []
        for i in range(len(input)):
            if "|" in input[i]:
                rules.append(tuple(map(int, input[i].strip().split("|"))))
            elif "," in input[i]:
                subsequences.append(list(map(int, input[i].strip().split(","))))
    return rules, subsequences


def create_adjacent_map(rules):
    global adj_list, indegree
    adj_list = defaultdict(list)
    indegree = defaultdict(int)
    # create adjacent map
    for left, right in rules:
        adj_list[left].append(right)
        indegree[right] += 1
        indegree[left] += 0
    return adj_list, indegree


def sort(adj_list, indegree):
    sorted_list = []
    queue = deque([node for node in indegree if indegree[node] == min(indegree.values())])
    while queue:
        node = queue.popleft()
        sorted_list.append(node)
        for neighbor in adj_list[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    return sorted_list


def valid_sequence(sorted_list, subsequences):
    valid_sequences = []
    for subsequence in subsequences:
        pivot_s = 0
        pivot_t = 0
        while pivot_t < len(sorted_list):
            if subsequence[pivot_s] == sorted_list[pivot_t]:
                pivot_s += 1
                if pivot_s == len(subsequence):
                    valid_sequences.append(subsequence)
                    break

            pivot_t += 1
    result_sum = sum(seq[len(seq) // 2] for seq in valid_sequences)
    return result_sum


if __name__ == '__main__':
    #
    # rules = [
    #     (47, 53),
    #     (97, 13),
    #     (97, 61),
    #     (97, 47),
    #     (75, 29),
    #     (61, 13),
    #     (75, 53),
    #     (29, 13),
    #     (97, 29),
    #     (53, 29),
    #     (61, 53),
    #     (97, 53),
    #     (61, 29),
    #     (47, 13),
    #     (75, 47),
    #     (97, 75),
    #     (47, 61),
    #     (75, 61),
    #     (47, 29),
    #     (75, 13),
    #     (53, 13),]

    # subsequences = [[75, 47, 61, 53, 29], [97, 61, 53, 29, 13], [75, 29, 13], [75, 97, 47, 61, 53], [61, 13, 29], [97, 13, 75, 29, 47]]

    rules, subsequences = read_input("5_input.txt")
    adj_list, indegree = create_adjacent_map(rules)
    sorted_list = sort(adj_list, indegree)
    result_sum = valid_sequence(sorted_list, subsequences)
    print(result_sum)