From a7a6b86002b595bc167af72606b14c67ed1bdf8f Mon Sep 17 00:00:00 2001 From: Tomasz Kramkowski Date: Wed, 24 Nov 2021 22:25:42 +0000 Subject: init commit --- 19/input | 45 ++++++++++++++++++++ 19/solution.py | 130 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 175 insertions(+) create mode 100644 19/input create mode 100644 19/solution.py (limited to '19') diff --git a/19/input b/19/input new file mode 100644 index 0000000..a245944 --- /dev/null +++ b/19/input @@ -0,0 +1,45 @@ +Al => ThF +Al => ThRnFAr +B => BCa +B => TiB +B => TiRnFAr +Ca => CaCa +Ca => PB +Ca => PRnFAr +Ca => SiRnFYFAr +Ca => SiRnMgAr +Ca => SiTh +F => CaF +F => PMg +F => SiAl +H => CRnAlAr +H => CRnFYFYFAr +H => CRnFYMgAr +H => CRnMgYFAr +H => HCa +H => NRnFYFAr +H => NRnMgAr +H => NTh +H => OB +H => ORnFAr +Mg => BF +Mg => TiMg +N => CRnFAr +N => HSi +O => CRnFYFAr +O => CRnMgAr +O => HP +O => NRnFAr +O => OTi +P => CaP +P => PTi +P => SiRnFAr +Si => CaSi +Th => ThCa +Ti => BP +Ti => TiTi +e => HF +e => NAl +e => OMg + +CRnCaCaCaSiRnBPTiMgArSiRnSiRnMgArSiRnCaFArTiTiBSiThFYCaFArCaCaSiThCaPBSiThSiThCaCaPTiRnPBSiThRnFArArCaCaSiThCaSiThSiRnMgArCaPTiBPRnFArSiThCaSiRnFArBCaSiRnCaPRnFArPMgYCaFArCaPTiTiTiBPBSiThCaPTiBPBSiRnFArBPBSiRnCaFArBPRnSiRnFArRnSiRnBFArCaFArCaCaCaSiThSiThCaCaPBPTiTiRnFArCaPTiBSiAlArPBCaCaCaCaCaSiRnMgArCaSiThFArThCaSiThCaSiRnCaFYCaSiRnFYFArFArCaSiRnFYFArCaSiRnBPMgArSiThPRnFArCaSiRnFArTiRnSiRnFYFArCaSiRnBFArCaSiRnTiMgArSiThCaSiThCaFArPRnFArSiRnFArTiTiTiTiBCaCaSiRnCaCaFYFArSiThCaPTiBPTiBCaSiThSiRnMgArCaF diff --git a/19/solution.py b/19/solution.py new file mode 100644 index 0000000..91106b3 --- /dev/null +++ b/19/solution.py @@ -0,0 +1,130 @@ +import re +from collections import defaultdict, Counter, deque +from functools import cache + +Chemical = tuple # [int, ...] + +def part1(reactions: dict[int, set[Chemical]], target: Chemical) -> int: + outputs: set[Chemical] = set() + counts: Counter[int] = Counter(target) + for chemical, results in reactions.items(): + for result in results: + for i in range(counts[chemical]): + output: list[int] = list() + n: int = 0 + for c in target: + if c == chemical: + if n == i: + output.extend(result) + else: + output.append(c) + n += 1 + else: + output.append(c) + outputs.add(tuple(output)) + return len(outputs) + +# def part2(reactions: dict[int, set[Chemical]], target: Chemical) -> int: +# unreactions: dict[Chemical, Chemical] = dict() +# for chemical, results in reactions.items(): +# for result in results: +# unreactions[result] = chemical +# @cache +# def path_len(c: Chemical) -> int: +# if c == (0,): +# print('found e') +# return 0 +# depth = float('inf') +# for search, replace in unreactions.items(): +# for i in range(len(c)): +# for j, comp in enumerate(search): +# if i + j >= len(c): +# break +# if c[i + j] != comp: +# break +# else: +# new = c[:i] + (replace,) + c[i + len(search):] +# depth = min(depth, path_len(new)) +# if depth == float('inf'): +# return depth +# return depth + 1 +# l = path_len(target) +# print(path_len.cache_info()) +# return l + +# def part2(reactions: dict[int, set[Chemical]], target: Chemical) -> int: +# unreactions: dict[Chemical, Chemical] = dict() +# for chemical, results in reactions.items(): +# for result in results: +# unreactions[result] = chemical +# queue: deque[tuple[Chemical, int]] = deque([(target, 0)]) +# while queue: +# c, depth = queue.popleft() +# if c == (0,): +# return depth +# for search, replace in unreactions.items(): +# for i in range(len(c) - len(search) + 1): +# for j, comp in enumerate(search): +# if c[i + j] != comp: +# break +# else: +# new = c[:i] + (replace,) + c[i + len(search):] +# print(f'{c} -> {new}') +# queue.append((new, depth + 1)) +# #print(queue) + +def part2(reactions: dict[int, set[Chemical]], target: Chemical) -> int: + unreactions: dict[Chemical, Chemical] = dict() + for chemical, results in reactions.items(): + for result in results: + unreactions[result] = chemical + def path_len(c: Chemical) -> int: + if c == (0,): + return 0 + for search, replace in unreactions.items(): + for i in range(len(c)): + for j, comp in enumerate(search): + if i + j >= len(c): + break + if c[i + j] != comp: + break + else: + new = c[:i] + (replace,) + c[i + len(search):] + l = path_len(new) + if l is not None: + return l + 1 + return None + return path_len(target) + +if __name__ == '__main__': + chem_id: dict[str, int] = dict(e=0) + next_chem_id: int = 1 + reactions: defaultdict[int, set[Chemical]] = defaultdict(set) + chempattern: re.Pattern = re.compile(r'e|[A-Z][a-z]?') + + def add_chem(chem: str) -> int: + global next_chem_id + if chem not in chem_id: + chem_id[chem] = next_chem_id + next_chem_id += 1 + return chem_id[chem] + with open('input_reddit') as f: + for line in f: + if line == '\n': + break + chem, expansion = line.strip().split(' => ') + reactions[add_chem(chem)].add(tuple(add_chem(c) for c in chempattern.findall(expansion))) + + target = tuple(add_chem(c) + for c in chempattern.findall(next(f).strip())) + test_reactions: dict[int, set[Chemical]] = { + 0: set([(1,), (2,)]), + 1: set([(1, 2), (2, 1)]), + 2: set([(1, 1)]), + # 0: set([(0, 1), (1, 0)]), + # 1: set([(0, 0)]), + } + test_target: Chemical = (1, 2, 1, 2, 1, 2) + # test_target: Chemical = (0, 1, 0) + print(part1(reactions, target)) + print(part2(reactions, target)) -- cgit v1.2.3-54-g00ecf