#!/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()