|
| 1 | +# -------------------------------- Input data -------------------------------- # |
| 2 | +import os |
| 3 | + |
| 4 | +test_data = {} |
| 5 | + |
| 6 | +test = 1 |
| 7 | +test_data[test] = {"input": """e => H |
| 8 | +e => O |
| 9 | +H => HO |
| 10 | +H => OH |
| 11 | +O => HH |
| 12 | +
|
| 13 | +HOH""", |
| 14 | + "expected": ['4', 'Unknown'], |
| 15 | + } |
| 16 | + |
| 17 | +test += 1 |
| 18 | +test_data[test] = {"input": """e => H |
| 19 | +e => O |
| 20 | +H => HO |
| 21 | +H => OH |
| 22 | +O => HH |
| 23 | +
|
| 24 | +HOHOHO""", |
| 25 | + "expected": ['7', 'Unknown'], |
| 26 | + } |
| 27 | + |
| 28 | +test = 'real' |
| 29 | +input_file = os.path.join(os.path.dirname(__file__), 'Inputs', os.path.basename(__file__).replace('.py', '.txt')) |
| 30 | +test_data[test] = {"input": open(input_file, "r+").read().strip(), |
| 31 | + "expected": ['535', '212'], |
| 32 | + } |
| 33 | + |
| 34 | +# -------------------------------- Control program execution -------------------------------- # |
| 35 | + |
| 36 | +case_to_test = 'real' |
| 37 | +part_to_test = 2 |
| 38 | +verbose_level = 1 |
| 39 | + |
| 40 | +# -------------------------------- Initialize some variables -------------------------------- # |
| 41 | + |
| 42 | +puzzle_input = test_data[case_to_test]['input'] |
| 43 | +puzzle_expected_result = test_data[case_to_test]['expected'][part_to_test-1] |
| 44 | +puzzle_actual_result = 'Unknown' |
| 45 | + |
| 46 | + |
| 47 | +# -------------------------------- Actual code execution -------------------------------- # |
| 48 | + |
| 49 | +molecules = set() |
| 50 | +from random import shuffle |
| 51 | + |
| 52 | +def find_nth(haystack, needle, n): |
| 53 | + i = -1 |
| 54 | + for _ in range(n): |
| 55 | + i = haystack.find(needle, i + len(needle)) |
| 56 | + if i == -1: |
| 57 | + break |
| 58 | + return i |
| 59 | + |
| 60 | +if part_to_test == 1: |
| 61 | + source_molecule = puzzle_input.split('\n')[-1] |
| 62 | + for string in puzzle_input.split('\n'): |
| 63 | + if string == '' or string == source_molecule: |
| 64 | + continue |
| 65 | + |
| 66 | + source, _, replacement = string.split() |
| 67 | + |
| 68 | + |
| 69 | + for i in range (1, source_molecule.count(source)+1): |
| 70 | + molecules.add(source_molecule[:find_nth(source_molecule, source, i)] + replacement + source_molecule[find_nth(source_molecule, source, i)+len(source):]) |
| 71 | + |
| 72 | + |
| 73 | + |
| 74 | + puzzle_actual_result = len(molecules) |
| 75 | + |
| 76 | + |
| 77 | + |
| 78 | + |
| 79 | +else: |
| 80 | + # This algorithm is wrong, in the sense that the result is not guaranteed (the replacements are applied in a random way...) |
| 81 | + # However, it's extremely fast, and running it many times then taking the minimum should be the right way (with my input, the result was always 212...) |
| 82 | + target_molecule = puzzle_input.split('\n')[-1] |
| 83 | + replacements = list() |
| 84 | + for string in puzzle_input.split('\n'): |
| 85 | + if string == '' or string == target_molecule: |
| 86 | + continue |
| 87 | + |
| 88 | + replacement, _, source = string.split() |
| 89 | + replacements.append((source, replacement)) |
| 90 | + |
| 91 | + new_molecule = target_molecule |
| 92 | + step = 0 |
| 93 | + shuffle(replacements) |
| 94 | + while puzzle_actual_result == 'Unknown': |
| 95 | + molecule_before = new_molecule |
| 96 | + for source, replacement in replacements: |
| 97 | + step += new_molecule.count(source) |
| 98 | + new_molecule = new_molecule.replace(source, replacement) |
| 99 | + if new_molecule == 'e': |
| 100 | + puzzle_actual_result = step |
| 101 | + break |
| 102 | + # Restart if we're stuck at some point |
| 103 | + if molecule_before == new_molecule: |
| 104 | + shuffle(replacements) |
| 105 | + new_molecule = target_molecule |
| 106 | + step = 0 |
| 107 | + |
| 108 | + |
| 109 | + |
| 110 | + # This would be the correct algorithm (ensures the result is correct), but it runs wayyyy too slow |
| 111 | + # target_molecule = puzzle_input.split('\n')[-1] |
| 112 | + # replacements = set() |
| 113 | + # for string in puzzle_input.split('\n'): |
| 114 | + # if string == '' or string == target_molecule: |
| 115 | + # continue |
| 116 | + |
| 117 | + # source, _, replacement = string.split() |
| 118 | + # replacements.add((source, replacement)) |
| 119 | + |
| 120 | + # molecules = set('e') |
| 121 | + # new_molecules = set() |
| 122 | + # step = 0 |
| 123 | + # while puzzle_actual_result == 'Unknown': |
| 124 | + # step += 1 |
| 125 | + # for molecule in molecules: |
| 126 | + # for source, replacement in replacements: |
| 127 | + # if not source in molecule: |
| 128 | + # new_molecules.add(molecule) |
| 129 | + # continue |
| 130 | + # for i in range (1, molecule.count(source)+1): |
| 131 | + # new_molecule = molecule[:find_nth(molecule, source, i)] + replacement + molecule[find_nth(molecule, source, i)+len(source):] |
| 132 | + # if new_molecule == target_molecule: |
| 133 | + # puzzle_actual_result = step |
| 134 | + # break |
| 135 | + # new_molecules.add(new_molecule) |
| 136 | + # molecules = new_molecules.copy() |
| 137 | + # print (step, len(molecules)) |
| 138 | + |
| 139 | + |
| 140 | + |
| 141 | +# -------------------------------- Outputs / results -------------------------------- # |
| 142 | + |
| 143 | +if verbose_level >= 3: |
| 144 | + print ('Input : ' + puzzle_input) |
| 145 | +print ('Expected result : ' + str(puzzle_expected_result)) |
| 146 | +print ('Actual result : ' + str(puzzle_actual_result)) |
| 147 | + |
| 148 | + |
| 149 | + |
| 150 | + |
0 commit comments