Untitled
unknown
plain_text
5 months ago
2.6 kB
4
Indexable
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)
Editor is loading...
Leave a Comment