**Part 1:** Given a list of list of string replacements and an input string, determine how many unique output strings are possible after one step.

```
transitions = collections.defaultdict(set)
reading_transitions = True
for line in sys.stdin:
line = line.strip()
if not line:
reading_transitions = False
elif reading_transitions:
src, dst = line.split(' => ')
transitions[src].add(dst)
else:
target = line
def expand_iter(input):
for src in transitions:
for dst in transitions[src]:
for match in re.finditer(src, input):
yield input[:match.start()] + dst + input[match.end():]
expansions = set(expand_iter(target))
print(len(expansions))
```

The basic idea here is to iterate over each possible (non-overlapping) replacement and `yield`

the results. Then we convert that to a `set`

to remove duplicates and return the sizes. Shiny.

I bet I can guess where the second half is going.

**Part 2:** This time, take the target as output and determine how many steps it would take to get from `e`

to the target.

This one is actually more of a rewrite (since I’m inverting the `transition`

map):

```
transitions = {}
reading_transitions = True
for line in sys.stdin:
line = line.strip()
if not line:
reading_transitions = False
elif reading_transitions:
src, dst = line.split(' => ')
transitions[dst] = src
else:
target = line
def build_iter(input):
for dst in transitions:
src = transitions[dst]
for match in re.finditer(dst, input):
yield input[:match.start()] + src + input[match.end():]
q = queue.PriorityQueue()
q.put((len(target), 0, target))
while True:
length, iterations, current = q.get()
if current == 'e':
break
for precursor in build_iter(current):
q.put((len(precursor), iterations + 1, precursor))
print(iterations)
```

Two basic insights here: Since each transition output is unique, we don’t have multiple possibilities and we want to solve the problem as quickly as possible. Given that, we will use a priority queue indexing on the length of the current chemical. That way, we’ll try the solutions that are already as far along as possible.

For my input, that worked very quickly. For slightly different inputs, the greedy solution doesn’t find a result and it has to backtrack, leading to a *far* longer runtime. I’m not sure what would solve those quickly. I may play with this one a bit longer.

Also, technically this solution isn’t strictly correct. It finds the first solution, rather than strictly speaking the shortest one. That could be fixed continuing to iterate on the priority queue until we’ve exhausted any branches with fewer iterations than the known best. That takes rather a while though. That’s one advantage of a contest styles–you can check your input. O:)