# Class notes for Monday, February 27, 2006

# A program to generate all theorems of the MIU formal system, as
# described in the "MU-puzzle" handout from week 1.

# Rule 1: If you have a string that ends in I, you can add a U on the
# end.

def rule1(s):
    if s[-1] == 'I':
        return [s + 'U']
    else:
        return []

# Rule 2: If you have a string of the form Mx where x is any substring
# of M's, I's, or U's, then you can make Mxx.

def rule2(s):
    if s[0] != 'M':
        return []
    else:
        x = s[1:]
        s = s + x
        return [s]

# Rule 3: If III occurs somewhere in a string, you can make a new
# string with U in place of III.

def rule3(s):
    resultList = []
    for i in range(len(s)-2):
        if s[i:i+3] == 'III':
            newString = s[0:i] + 'U' + s[i+3:]
            resultList.append(newString)
    return resultList

# Rule 4: If UU occurs somewhere in a string, you can drop it.

def rule4(s):
    resultList = []
    for i in range(len(s)-1):
        if s[i:i+2] == 'UU':
            newString = s[:i] + s[i+2:]
            resultList.append(newString)
    return resultList

# returns a new list with all duplicate elements of list removed

def withoutDuplicates(list):
    resultList = []
    for element in list:
        if element not in resultList:
            resultList.append(element)
    return resultList

# returns the new strings that can be made by applying the rules once
# to all of the strings in the input list.

def applyRules(strings):
    newStrings = []
    for s in strings:
        newStrings.extend(rule1(s))
        newStrings.extend(rule2(s))
        newStrings.extend(rule3(s))
        newStrings.extend(rule4(s))
    return withoutDuplicates(newStrings)

# generates all MIU theorems reachable in a given number of steps.

def generate(steps):
    knownTheorems = []
    stepCount = 0
    currentStrings = ['MI']
    for i in range(steps):
        newStrings = applyRules(currentStrings)
        stepCount = stepCount + 1
        print 'Reached in %d steps:' % stepCount
        for s in newStrings:
            if s not in knownTheorems:
                print s
                knownTheorems.append(s)
        print
        currentStrings = newStrings