enigme_mu.py

Created on April 22, 2018

907 Bytes

Ce programme génère, à partir de la chaîne MI, des chaînes de caractères, étape par étape, selon les 4 règles de formation suivante:1-Si on possède une chaîne se terminant par I, on peut lui ajouter U à la fin ; 2-Si on possède la chaîne Mx, on peut lui ajouter x pour obtenir la chaîne Mxx ; 3-Si on possède une chaîne contenant III, on peut remplacer III par U ; 4-Si une chaîne contient UU, on peut supprimer ce UU. Peut-on obtenir MU? (l’idée vient du livre de D. Hofstadter : Gödel Escher Bach)

def regle1(m):
    if m[-1:]=='I'and m+'U' not in nouveaux:
        nouveaux.append(m+'U')
def regle2(m):
    X=m[1:]
    if m+X not in nouveaux:
        nouveaux.append(m+X)
def regle3(m):
    R=m.find('III',0)
    while R>=0:
        if m[0:R]+'U'+m[R+3:] not in nouveaux:
            nouveaux.append(m[0:R]+'U'+m[R+3:])
        R=m.find('III',R+1)
def regle4(m):
    R=m.find('UU',0)
    while R>=0:
        if m[0:R]+m[R+2:] not in nouveaux:
            nouveaux.append(m[0:R]+m[R+2:])
        R=m.find('UU',R+1)

anciens,n=['MI'],0
print('Generation 0:',anciens)
while 'MU' not in anciens:
    nouveaux,n=[],n+1
    for m in anciens:
        regle1(m)
        regle2(m)
        regle3(m)
        regle4(m)
    if n<3:print('Generation {}:'.format(n),nouveaux)
    else:print('Generation {}: {} chaines'.format(n,len(nouveaux)))
    anciens=nouveaux
print('MU trouve a la generation',n)