Initial commit

3 files changed, 212 insertions, 0 deletions

diff --git a/19/input.txt b/19/input.txt
new file mode 100644
index 0000000..806774f
--- /dev/null
+++ b/19/input.txt
@@ -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
+
+CRnCaSiRnBSiRnFArTiBPTiTiBFArPBCaSiThSiRnTiBPBPMgArCaSiRnTiMgArCaSiThCaSiRnFArRnSiRnFArTiTiBFArCaCaSiRnSiThCaCaSiRnMgArFYSiRnFYCaFArSiThCaSiThPBPTiMgArCaPRnSiAlArPBCaCaSiRnFYSiThCaRnFArArCaCaSiRnPBSiRnFArMgYCaCaCaCaSiThCaCaSiAlArCaCaSiRnPBSiAlArBCaCaCaCaSiThCaPBSiThPBPBCaSiRnFYFArSiThCaSiRnFArBCaCaSiRnFYFArSiThCaPBSiThCaSiRnPMgArRnFArPTiBCaPRnFArCaCaCaCaSiRnCaCaSiRnFYFArFArBCaSiThFArThSiThSiRnTiRnPMgArFArCaSiThCaPBCaSiRnBFArCaCaPRnCaCaPMgArSiRnFYFArCaSiThRnPBPMgAr
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()
diff --git a/19/test.py b/19/test.py
new file mode 100755
index 0000000..f2fab39
--- /dev/null
+++ b/19/test.py
@@ -0,0 +1,39 @@
+#!/usr/bin/python
+
+import unittest
+
+import main
+
+
+
+class Examples(unittest.TestCase):
+    def test_example1(self):
+        lines = [
+            "e => H",
+            "e => O",
+            "H => HO",
+            "H => OH",
+            "O => HH",
+            "",
+            "HOH"
+        ]
+        self.assertEqual(main.solve_part1(lines), 4)
+        self.assertEqual(main.solve_part2(lines), 3)
+
+    def test_example2(self):
+        lines = [
+            "e => H",
+            "e => O",
+            "H => HO",
+            "H => OH",
+            "O => HH",
+            "",
+            "HOHOHO"
+        ]
+        self.assertEqual(main.solve_part1(lines), 7)
+        self.assertEqual(main.solve_part2(lines), 6)
+
+
+
+if __name__ == "__main__":
+    unittest.main()