init commit

2 files changed, 175 insertions, 0 deletions

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))