From 68615a9ad2c942254135cffb00cf25a84a3b1356 Mon Sep 17 00:00:00 2001 From: Prefetch Date: Sat, 31 Dec 2022 22:21:39 +0100 Subject: Initial commit --- 19/input.txt | 45 +++++++++++++++++++++ 19/main.py | 128 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 19/test.py | 39 ++++++++++++++++++ 3 files changed, 212 insertions(+) create mode 100644 19/input.txt create mode 100755 19/main.py create mode 100755 19/test.py (limited to '19') 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() -- cgit v1.2.3