Suite audioactive de Conway

Dans la suite mathématique Look and say, inventée en 1986 par le mathématicien John Horton Conway, un terme se détermine en annonçant les chiffres formant le terme précédent.

\[\begin{matrix}1\\11\\21\\1211\\111221\\312211\end{matrix}\]

Explication :

• à partir de \(111221\),
• on lit \(111\,22\,1\),
• soit trois \(1\), puis deux \(2\), et un \(1\),
• d'où \(31\,22\,11\) pour la ligne suivante.

On peut vérifier que la ligne suivante est \(13112221\).

Pour simplifier le code, on va modéliser cette suite par la liste des chiffres.

🐍 Script Python

LIGNE_1 = [1]
LIGNE_2 = [1, 1]
LIGNE_3 = [2, 1]
LIGNE_4 = [1, 2, 1, 1]
LIGNE_5 = [1, 1, 1, 2, 2, 1]
LIGNE_6 = [3, 1, 2, 2, 1, 1]
LIGNE_7 = [1, 3, 1, 1, 2, 2, 2, 1]

Écrire une fonction telle que conway_suivante(ligne) renvoie, sous forme de liste, la ligne suivante après ligne. Ceci pourrait permettre de faire des appels récursifs.

Exemples

🐍 Script Python

>>> conway_suivante([3, 1, 2, 2, 1, 1])
[1, 3, 1, 1, 2, 2, 2, 1]
>>> conway_suivante([1, 3, 1, 1, 2, 2, 2, 1])
[1, 1, 1, 3, 2, 1, 3, 2, 1, 1]

Code à compléter :

###

Lancer# testsbksl-nlbksl-nlLIGNEpy-und6 = [3, 1, 2, 2, 1, 1]bksl-nlLIGNEpy-und7 = [1, 3, 1, 1, 2, 2, 2, 1]bksl-nlLIGNEpy-und8 = [1, 1, 1, 3, 2, 1, 3, 2, 1, 1]bksl-nlassert conwaypy-undsuivante(LIGNEpy-und6) == LIGNEpy-und7bksl-nlassert conwaypy-undsuivante(LIGNEpy-und7) == LIGNEpy-und8bksl-nlbksl-nlbksl-nl# autres testsbksl-nlCONWAY = [bksl-nl [1],bksl-nl [1, 1],bksl-nl [2, 1],bksl-nl [1, 2, 1, 1],bksl-nl [1, 1, 1, 2, 2, 1],bksl-nl [3, 1, 2, 2, 1, 1],bksl-nl [1, 3, 1, 1, 2, 2, 2, 1],bksl-nl [1, 1, 1, 3, 2, 1, 3, 2, 1, 1],bksl-nl [3, 1, 1, 3, 1, 2, 1, 1, 1, 3, 1, 2, 2, 1],bksl-nl [1, 3, 2, 1, 1, 3, 1, 1, 1, 2, 3, 1, 1, 3, 1, 1, 2, 2, 1, 1],bksl-nl [1, 1, 1, 3, 1, 2, 2, 1, 1, 3, 3, 1, 1, 2, 1, 3, 2, 1, 1, 3, 2, 1, 2, 2, 2, 1],bksl-nl [3, 1, 1, 3, 1, 1, 2, 2, 2, 1, 2, 3, 2, 1, 1, 2, 1, 1, 1, 3, 1, 2, 2, 1, 1, 3, 1, 2, 1, 1, 3, 2, 1, 1],bksl-nl [1, 3, 2, 1, 1, 3, 2, 1, 3, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 2, 3, 1, 1, 3, 1, 1, 2, 2, 2, 1, 1, 3, 1, 1, 1, 2, 2, 1, 1, 3, 1, 2, 2, 1],bksl-nl [1, 1, 1, 3, 1, 2, 2, 1, 1, 3, 1, 2, 1, 1, 1, 3, 1, 2, 3, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 2, 2, 1, 1, 2, 1, 3, 2, 1, 1, 3, 2, 1, 3, 2, 2, 1, 1, 3, 3, 1, 2, 2, 2, 1, 1, 3, 1, 1, 2, 2, 1, 1],bksl-nl [3, 1, 1, 3, 1, 1, 2, 2, 2, 1, 1, 3, 1, 1, 1, 2, 3, 1, 1, 3, 1, 1, 1, 2, 1, 3, 2, 1, 1, 2, 3, 1, 1, 3, 2, 1, 3, 2, 2, 1, 1, 2, 1, 1, 1, 3, 1, 2, 2, 1, 1, 3, 1, 2, 1, 1, 1, 3, 2, 2, 2, 1, 2, 3, 1, 1, 3, 2, 2, 1, 1, 3, 2, 1, 2, 2, 2, 1],bksl-nl [1, 3, 2, 1, 1, 3, 2, 1, 3, 2, 2, 1, 1, 3, 3, 1, 1, 2, 1, 3, 2, 1, 1, 3, 3, 1, 1, 2, 1, 1, 1, 3, 1, 2, 2, 1, 1, 2, 1, 3, 2, 1, 1, 3, 1, 2, 1, 1, 1, 3, 2, 2, 2, 1, 1, 2, 3, 1, 1, 3, 1, 1, 2, 2, 2, 1, 1, 3, 1, 1, 1, 2, 3, 1, 1, 3, 3, 2, 1, 1, 1, 2, 1, 3, 2, 1, 1, 3, 2, 2, 2, 1, 1, 3, 1, 2, 1, 1, 3, 2, 1, 1],bksl-nl [1, 1, 1, 3, 1, 2, 2, 1, 1, 3, 1, 2, 1, 1, 1, 3, 2, 2, 2, 1, 2, 3, 2, 1, 1, 2, 1, 1, 1, 3, 1, 2, 2, 1, 2, 3, 2, 1, 1, 2, 3, 1, 1, 3, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 1, 3, 1, 2, 2, 1, 1, 3, 1, 1, 1, 2, 3, 1, 1, 3, 3, 2, 2, 1, 1, 2, 1, 3, 2, 1, 1, 3, 2, 1, 3, 2, 2, 1, 1, 3, 3, 1, 1, 2, 1, 3, 2, 1, 2, 3, 1, 2, 3, 1, 1, 2, 1, 1, 1, 3, 1, 2, 2, 1, 1, 3, 3, 2, 2, 1, 1, 3, 1, 1, 1, 2, 2, 1, 1, 3, 1, 2, 2, 1],bksl-nl [3, 1, 1, 3, 1, 1, 2, 2, 2, 1, 1, 3, 1, 1, 1, 2, 3, 1, 1, 3, 3, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 2, 3, 1, 1, 3, 1, 1, 2, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 2, 1, 3, 2, 1, 1, 3, 2, 1, 3, 2, 2, 1, 1, 2, 3, 1, 1, 3, 1, 1, 2, 2, 2, 1, 1, 3, 3, 1, 1, 2, 1, 3, 2, 1, 2, 3, 2, 2, 2, 1, 1, 2, 1, 1, 1, 3, 1, 2, 2, 1, 1, 3, 1, 2, 1, 1, 1, 3, 2, 2, 2, 1, 2, 3, 2, 1, 1, 2, 1, 1, 1, 3, 1, 2, 1, 1, 1, 2, 1, 3, 1, 1, 1, 2, 1, 3, 2, 1, 1, 2, 3, 1, 1, 3, 1, 1, 2, 2, 2, 1, 2, 3, 2, 2, 2, 1, 1, 3, 3, 1, 2, 2, 2, 1, 1, 3, 1, 1, 2, 2, 1, 1],bksl-nl [1, 3, 2, 1, 1, 3, 2, 1, 3, 2, 2, 1, 1, 3, 3, 1, 1, 2, 1, 3, 2, 1, 2, 3, 1, 2, 3, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 2, 2, 1, 1, 2, 1, 3, 2, 1, 1, 3, 2, 1, 2, 2, 3, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 1, 3, 1, 2, 2, 1, 1, 3, 1, 2, 1, 1, 1, 3, 2, 2, 2, 1, 1, 2, 1, 3, 2, 1, 1, 3, 2, 1, 3, 2, 2, 1, 2, 3, 2, 1, 1, 2, 1, 1, 1, 3, 1, 2, 1, 1, 1, 2, 1, 3, 3, 2, 2, 1, 1, 2, 3, 1, 1, 3, 1, 1, 2, 2, 2, 1, 1, 3, 1, 1, 1, 2, 3, 1, 1, 3, 3, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 2, 3, 1, 1, 3, 1, 1, 1, 2, 3, 1, 1, 2, 1, 1, 1, 3, 3, 1, 1, 2, 1, 1, 1, 3, 1, 2, 2, 1, 1, 2, 1, 3, 2, 1, 1, 3, 2, 1, 3, 2, 1, 1, 1, 2, 1, 3, 3, 2, 2, 1, 2, 3, 1, 1, 3, 2, 2, 1, 1, 3, 2, 1, 2, 2, 2, 1],bksl-nl [1, 1, 1, 3, 1, 2, 2, 1, 1, 3, 1, 2, 1, 1, 1, 3, 2, 2, 2, 1, 2, 3, 2, 1, 1, 2, 1, 1, 1, 3, 1, 2, 1, 1, 1, 2, 1, 3, 1, 1, 1, 2, 1, 3, 2, 1, 1, 2, 3, 1, 1, 3, 2, 1, 3, 2, 2, 1, 1, 2, 1, 1, 1, 3, 1, 2, 2, 1, 1, 3, 1, 2, 1, 1, 2, 2, 1, 3, 2, 1, 1, 2, 3, 1, 1, 3, 2, 1, 3, 2, 2, 1, 1, 2, 3, 1, 1, 3, 1, 1, 2, 2, 2, 1, 1, 3, 1, 1, 1, 2, 3, 1, 1, 3, 3, 2, 2, 1, 1, 2, 1, 1, 1, 3, 1, 2, 2, 1, 1, 3, 1, 2, 1, 1, 1, 3, 2, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 2, 3, 1, 1, 3, 1, 1, 1, 2, 3, 1, 1, 2, 1, 1, 2, 3, 2, 2, 2, 1, 1, 2, 1, 3, 2, 1, 1, 3, 2, 1, 3, 2, 2, 1, 1, 3, 3, 1, 1, 2, 1, 3, 2, 1, 2, 3, 1, 2, 3, 1, 1, 2, 1, 1, 1, 3, 1, 1, 2, 2, 2, 1, 1, 2, 1, 3, 2, 1, 1, 3, 3, 1, 1, 2, 1, 3, 2, 1, 1, 2, 3, 1, 2, 3, 2, 1, 1, 2, 3, 1, 1, 3, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 1, 3, 1, 2, 2, 1, 1, 3, 1, 2, 1, 1, 1, 3, 1, 2, 3, 1, 1, 2, 1, 1, 2, 3, 2, 2, 1, 1, 1, 2, 1, 3, 2, 1, 1, 3, 2, 2, 2, 1, 1, 3, 1, 2, 1, 1, 3, 2, 1, 1],bksl-nl]bksl-nlbksl-nlsecret = all(conwaypy-undsuivante(CONWAY[i-1]) == CONWAY[i]bksl-nl for i in range(1, len(CONWAY)))bksl-nlassert secret, "Erreur à un test secret"bksl-nlbksl-nl Valider 5/5 TéléchargerTéléverser RechargerSauvegarder

def conwaypy-undsuivante(ligne):bksl-nl precedent = ligne[0]bksl-nl nbpy-undconsecutifs = 0bksl-nl resultat = ...bksl-nl for chiffre in ligne:bksl-nl if chiffre == precedent:bksl-nl nbpy-undconsecutifs = ...bksl-nl else:bksl-nl resultat.append(...)bksl-nl resultat.append(...)bksl-nl precedent = ...bksl-nl nbpy-undconsecutifs = ...bksl-nl resultat.append(...)bksl-nl resultat.append(...)bksl-nl return ...bksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlLIGNEpy-und6 = [3, 1, 2, 2, 1, 1]bksl-nlLIGNEpy-und7 = [1, 3, 1, 1, 2, 2, 2, 1]bksl-nlLIGNEpy-und8 = [1, 1, 1, 3, 2, 1, 3, 2, 1, 1]bksl-nlassert conwaypy-undsuivante(LIGNEpy-und6) == LIGNEpy-und7bksl-nlassert conwaypy-undsuivante(LIGNEpy-und7) == LIGNEpy-und8bksl-nlbksl-nldef conwaypy-undsuivante(ligne):bksl-nl precedent = ligne[0]bksl-nl nbpy-undconsecutifs = 0bksl-nl resultat = []bksl-nl for chiffre in ligne:bksl-nl if chiffre == precedent:bksl-nl nbpy-undconsecutifs += 1bksl-nl else:bksl-nl resultat.append(nbpy-undconsecutifs)bksl-nl resultat.append(precedent)bksl-nl precedent = chiffrebksl-nl nbpy-undconsecutifs = 1bksl-nl resultat.append(nbpy-undconsecutifs)bksl-nl resultat.append(precedent)bksl-nl return resultatbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlLIGNEpy-und6 = [3, 1, 2, 2, 1, 1]bksl-nlLIGNEpy-und7 = [1, 3, 1, 1, 2, 2, 2, 1]bksl-nlLIGNEpy-und8 = [1, 1, 1, 3, 2, 1, 3, 2, 1, 1]bksl-nlassert conwaypy-undsuivante(LIGNEpy-und6) == LIGNEpy-und7bksl-nlassert conwaypy-undsuivante(LIGNEpy-und7) == LIGNEpy-und8bksl-nlbksl-nl

A

1. On complète return resultat à la fin, ligne 15, c'est la liste des nouveaux chiffres. Elle se construit par accumulation, et elle est initialisée vide à la ligne 4 resultat = [].
2. À chaque changement de chiffre,
   • on ajoute à la liste d'abord la quantité nb_consecutifs, puis le chiffre precedent. En sortie de boucle, on agit comme s'il y avait changement.
   • On met à jour precedent = chiffre, et nb_consecutifs = 1 en comptant ce chiffre juste vu. On remarque qu'à la ligne 3, on n'avait pas encore vu le premier chiffre, donc l'initialisation était à 0.
3. Si le chiffre est le même, on incrémente nb_consecutifs de 1.

Version fonctionnelle

Dans le module itertools, il y a une fonction groupby qui permet de regrouper par lot, dans un itérable, les termes consécutifs identiques.

🐍 Script Python

from itertools import groupby

def conway_suivante(ligne):
    resultat = []
    for motif, iterable in groupby(ligne):
        resultat.append(sum(1 for chiffre in iterable))
        resultat.append(motif)
    return resultat

Z