From a7a6b86002b595bc167af72606b14c67ed1bdf8f Mon Sep 17 00:00:00 2001 From: Tomasz Kramkowski Date: Wed, 24 Nov 2021 22:25:42 +0000 Subject: init commit --- 9/solution.py | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) create mode 100644 9/solution.py (limited to '9/solution.py') diff --git a/9/solution.py b/9/solution.py new file mode 100644 index 0000000..48b0c7c --- /dev/null +++ b/9/solution.py @@ -0,0 +1,40 @@ +from itertools import permutations, islice +import collections + +def sliding_window(iterable, n): + # sliding_window('ABCDEFG', 4) -> ABCD BCDE CDEF DEFG + it = iter(iterable) + window = collections.deque(islice(it, n), maxlen=n) + if len(window) == n: + yield tuple(window) + for x in it: + window.append(x) + yield tuple(window) + +def part1(nodes: set, distances: dict) -> int: + """ + >>> part1(set('ABC'), {('A', 'B'): 464, ('A', 'C'): 518, ('B', 'C'): 141}) + 605 + """ + return min(sum(distances[tuple(sorted(edge))] for edge in sliding_window(path, 2)) for path in permutations(nodes)) + +def part2(nodes: set, distances: dict) -> int: + """ + >>> part2(set('ABC'), {('A', 'B'): 464, ('A', 'C'): 518, ('B', 'C'): 141}) + 982 + """ + return max(sum(distances[tuple(sorted(edge))] for edge in sliding_window(path, 2)) for path in permutations(nodes)) + +if __name__ == '__main__': + nodes = set() + distances = dict() + with open('input') as f: + for l in f: + l = l.strip() + edge, distance = l.split(' = ') + edge = tuple(sorted(edge.split(' to '))) + nodes.add(edge[0]) + nodes.add(edge[1]) + distances[edge] = int(distance) + print(part1(nodes, distances)) + print(part2(nodes, distances)) -- cgit v1.2.3-54-g00ecf