From e82eac08de8966e49ecc909c8a5e3593db7e158b Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Sun, 12 Dec 2021 15:59:41 +0700 Subject: [aoc/2021] Finish day 12 --- aoc/2021/12/part-one.py | 19 +++++++++++++++++++ aoc/2021/12/part-two.py | 20 ++++++++++++++++++++ 2 files changed, 39 insertions(+) create mode 100644 aoc/2021/12/part-one.py create mode 100644 aoc/2021/12/part-two.py diff --git a/aoc/2021/12/part-one.py b/aoc/2021/12/part-one.py new file mode 100644 index 0000000..7ab0e56 --- /dev/null +++ b/aoc/2021/12/part-one.py @@ -0,0 +1,19 @@ +from collections import defaultdict, deque +from itertools import permutations +from sys import stdin + +edges = defaultdict(list) +for line in stdin.read().strip().split(): + for key, value in permutations(line.split('-')): + if key != 'end' and value != 'start': edges[key].append(value) +paths = set() +queue = deque([('start',)]) +while queue: + if (head := queue.popleft()) in paths: continue + paths.add(head) + if (chin := head[-1]) == 'end': continue + for neck in edges[chin]: + if neck.islower() and neck in head: continue + top = head + (neck,) + queue.append(top) +print(sum(path[-1] == 'end' for path in paths)) diff --git a/aoc/2021/12/part-two.py b/aoc/2021/12/part-two.py new file mode 100644 index 0000000..7d87da7 --- /dev/null +++ b/aoc/2021/12/part-two.py @@ -0,0 +1,20 @@ +from collections import defaultdict, deque +from itertools import groupby, permutations +from sys import stdin + +edges = defaultdict(list) +for line in stdin.read().strip().split(): + for key, value in permutations(line.split('-')): + if key != 'end' and value != 'start': edges[key].append(value) +paths = set() +queue = deque([('start',)]) +while queue: + if (head := queue.popleft()) in paths: continue + paths.add(head) + if (chin := head[-1]) == 'end': continue + for neck in edges[chin]: + top = head + (neck,) + if sum(len(tuple(group)) - 1 for cave, group in groupby(sorted(top)) + if cave.islower()) > 1: continue + queue.append(top) +print(sum(path[-1] == 'end' for path in paths)) -- cgit 1.4.1