csce411hw5pr5.py created by nategraf - https://repl.it/EWrq/1

csce411hw5pr5.py.py

import re
from heapq import *
rules = [
    lambda s: [s + 'U'] if s[-1] == 'I' else [s],
    lambda s: [s[:m.start()+1]+s[m.end():]*2 for m in re.finditer('M',s)],
    lambda s: [s[:m.start()]+'U'+s[m.end():] for m in re.finditer('III',s)],
    lambda s: [s[:m.start()]+s[m.end():] for m in re.finditer('UU',s)]
]

end = "MU"
start = "MI"
unvisited = [(0, len(start), start)]
discovered = {}
discovered[start] = (0, None, -1)
step = 0
timeout = 10000
while step < timeout and unvisited:
    dist, junk, curr = heappop(unvisited)
    for num, rule in enumerate(rules):
        for morph in rule(curr):
            if morph in discovered:
                if discovered[morph][0] > dist + 1:
                    discovered[morph] = (dist + 1, curr, num)
            else:
                discovered[morph] = (dist + 1, curr, num)
                heappush(unvisited, (dist + 1, len(morph), morph))
            if morph == end:
                break
        else:
            continue
        break
    else:
        step += 1
        continue
    break
    


if end in discovered:
    result = []
    curr = end
    while curr != start:
        dist, nextt, num = discovered[curr]
        result.append("{} \\gets {} (rule {})".format(nextt, curr, num+1))
        curr = nextt
    for step in reversed(result):
        print(step)
else:
    print("Pattern not found after", step, "steps")