1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
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()
|
