From 68615a9ad2c942254135cffb00cf25a84a3b1356 Mon Sep 17 00:00:00 2001
From: Prefetch
Date: Sat, 31 Dec 2022 22:21:39 +0100
Subject: Initial commit

---
 19/main.py | 128 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 128 insertions(+)
 create mode 100755 19/main.py

(limited to '19/main.py')

diff --git a/19/main.py b/19/main.py
new file mode 100755
index 0000000..120a44a
--- /dev/null
+++ b/19/main.py
@@ -0,0 +1,128 @@
+#!/usr/bin/python
+
+from random import shuffle
+
+
+
+def parse_input(lines):
+    rules = {}
+    for line in lines[0:-2]:
+        words = line.split()
+        k = words[0]
+        if k not in rules:
+            rules[k] = []
+        rules[k].append(words[2])
+
+    molecule = lines[-1]
+    return rules, molecule
+
+
+
+# Given a "parent" molecule, find all "child" molecules
+# that can be made from it with exactly one replacement.
+def find_children(rules, parent):
+    result = []
+    # For each replaceable string
+    for k in rules.keys():
+        # For each occurrence in the given molecule
+        p = 0
+        while p < len(parent):
+            i = parent.find(k, p)
+            if i != -1:
+                # For each replacement of the replaceable string
+                for r in rules[k]:
+                    m = parent[0 : i] + r + parent[i + len(k) : ]
+                    if m not in result:
+                        result.append(m)
+                p = i + 1
+            else: # ran out of occurrences
+                break
+    return result
+
+
+
+# Given a "child" molecule, find all "parent" molecules
+# that can be produce it using exactly one replacement.
+def find_parents(rules, child):
+    result = []
+    # For each replaceable string
+    for k in rules.keys():
+        # For each replacement of the replaceable string
+        for r in rules[k]:
+            # For each occurrence in the given molecule
+            p = 0
+            while p < len(child):
+                i = child.find(r, p)
+                if i != -1:
+                    m = child[0 : i] + k + child[i + len(r) : ]
+                    if m not in result:
+                        result.append(m)
+                    p = i + 1
+                else: # ran out of occurrences
+                    break
+    return result
+
+
+
+def solve_part1(lines):
+    rules, start = parse_input(lines)
+    result = find_children(rules, start)
+    return len(result)
+
+
+
+def solve_part2(lines):
+    rules, target = parse_input(lines)
+    molecules = [target]
+
+    # Compared to part 1, we do part 2 in reverse: from the target molecule,
+    # we work backwards through its history until we encounter "e"; because
+    # we go back one generation at a time, the first "e" must be the answer.
+    depth = 0
+    while "e" not in molecules:
+
+        # Find all ancestors of this generation; there could be HUGELY many
+        ancestors = []
+        for m in molecules:
+            parents = find_parents(rules, m)
+            for p in parents:
+                if p not in ancestors:
+                    ancestors.append(p)
+
+        # Extremely greedy algorithm: only keep shortest candidates,
+        # because they're more likely to lie on the shortest path.
+        # However, this may give the wrong answer: the optimal path
+        # may involve some strategic locally non-optimal steps.
+        min_len = min(map(len, ancestors))
+        shortest = []
+        for p in ancestors:
+            if len(p) == min_len:
+                shortest.append(p)
+        ancestors = shortest
+
+        # Sledgehammer solution to keep the runtime under control,
+        # since it turns out the above greedy approach isn't enough.
+        # Fortunately, the puzzle input is well-chosen to allow this.
+        if len(ancestors) > 42:
+            shuffle(ancestors)
+            ancestors = ancestors[0 : 42]
+
+        molecules = ancestors
+        depth += 1
+
+    return depth
+
+
+
+def main():
+    # Read replacement rules and medicine molecules from input text file
+    with open("input.txt", "r") as f:
+        lines = f.read().splitlines()
+
+    print("Part 1 solution:", solve_part1(lines)) # 509 for me
+    print("Part 2 solution:", solve_part2(lines)) # 195 for me
+
+
+
+if __name__ == "__main__":
+    main()
-- 
cgit v1.2.3