Source

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:)