清蒸萌新literal @[email protected]

# S -> iS | M
# M -> iMeS | O
# -----
# S = statement, M = matched_statement, O = other
# i = if, e = else
import copy

class Obj:
    def __init__(self, init):
        self.value = init
        self.path = []

        self.path.append(init)

    def push(self, ns):
        self.value = ns
        self.path.append(ns)

    def __repr__(self):
        return self.value

    def __hash__(self):
        return hash(self.value)

    def __eq__(self, other):
        return self.value == other.value

cur = [Obj('S')]
nxt = []
ahs = set() # all history
ahl = []

assert(Obj('SS') == Obj('SS'))
assert(Obj('SS') != Obj('SSb'))

def cfind(s : str):
    spos = s.find('S')
    mpos = s.find('M')

    if spos == -1 and mpos == -1:
        return 'O'

    if spos == -1:
        return 'M'
    if mpos == -1:
        return 'S'

    if spos < mpos:
        return 'S'
    else:
        return 'M'

for i in range(100):
    for mem in cur:
        svar = cfind(mem.value)
        if svar == 'S':
            # 1
            prod1 = copy.deepcopy(mem)
            prod1.push(prod1.value.replace('S', 'iS', 1))
            nxt.append(prod1)
            # 2
            prod2 = copy.deepcopy(mem)
            prod2.push(prod2.value.replace('S', 'M', 1))
            nxt.append(prod2)
        elif svar == 'M':
            # 1
            prod1 = copy.deepcopy(mem)
            prod1.push(prod1.value.replace('M', 'iMeS', 1))
            nxt.append(prod1)
            # 2
            prod2 = copy.deepcopy(mem)
            prod2.push(prod2.value.replace('M', 'O', 1))
            nxt.append(prod2)

    ahl.extend(nxt)
    for nmem in nxt:
        if nmem in ahs:
            print(nmem.path)
            for s in ahl:
                if s == nmem:
                    print(s.path)
        ahs.add(nmem)
        

    print(i+1)
    input('next>')
    cur = nxt
    nxt = []