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

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 = "MUIIU"
start = "MI"
unvisited = [start]
discovered = {}
discovered[start] = (0, None, -1)
step = 0
timeout = 100
while step < timeout and unvisited:
    curr = heappop(unvisited)
    dist = discovered[curr][0]
    if end in discovered:
        if discovered[end][0] <= dist:
            break
    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, morph)
    step += 1
    
if end in discovered:
    curr = end
    while curr != start:
        dist, nextt, num = discovered[curr]
        print("{} \\gets {} (rule {})".format(nextt, curr, num+1))
        curr = nextt
else:
    print("Pattern not found after", step, "steps")