LookAndSay¶
But de l’exercice¶
Le but de l’exercice est d’écrire une fonction look_and_say, dans un fichier conway.py dont le but est de donner le terme suivant de la suite de Conway.
Et voila le script de tests unitaires : test_lookandsay.py
Context¶
La suite de Conway est une suite mathématique dite "audioactive" qui décrit le terme N-1 avec l'élément de range N. Il suffit de donner le nombre d'occurence de chaque nombre avec ce nombre.
| Rang | élément suivant |
|---|---|
| 1 | 11 ( 1 un ) |
| 2 | 21 ( 2 un ) |
| 3 | 1211 ( 1 deux et 1 un ) |
Plus d'informations sur le site de wikipedia.
Exercice de base¶
Il va falloir écrire une fonciton qui retourne l'element N+1 a partir de l'element de rang N qui est passe en parametre. Le type d'entrée pourra etre un entier, une liste, un tuple, ou une chaine de charactère. Le type de retour sera une liste de char avec les éléments de l'itération suivante.
>>> list(look_and_say(1))
['1', '1']
>>> list(look_and_say("11"))
['2', '1']
Il faudra aussi que l'on puisse appeler la fonction sur le resultat qu'elle fournie, ainsi on peut obtenir le resultat de N+2.
>>> list(look_and_say(look_and_say(1)))
['2', '1']
Il faut aussi pouvoir gérer un générateur en entrée:
>>> list(look_and_say(range(2)))
['1', '0', '1', '1']
Dans un premier temps, essayez de résoudre ce problème sans faire appel à un module spécifique, et dans un second temps (si vous voulez) vous pourrez utiliser un module livré avec python par exemple.
Bonus numéro 1¶
Ecrire la fonction inverse, celle qui, à partir d'un élément de rang N, retourne l'élément de rang N-1:
>>> list(look_and_say_rev(1211))
['2', '1']
Donc si on combine la fonction normale et son inverse, on est censés retomber sur nos pieds:
>>> list(look_and_say_rev(look_and_say(1)))
['1']
Bonus numéro 2¶
Faire de la fonction look_and_say un iterateur qui ne consomme que peu de mémoire pour réaliser son traitement.
Même si ici cela n'a juste aucun interret; dans le cadre du big data, on peut être amené à traiter des Terras de données (qui ne tiennent pas en mémoire donc) avec un ordinateur "standard". Donc il s'agit de ne pas consommer plus que de raison.
Ici, on peut traiter une entrée de taille quasi infinie avec à peine quelques entiers en meme temps en mémoire car au final on n'a besoin que de compter les elements identiques avant de retourner leur nombre et passer à l'élément suivant.
>>> a = iter("12345")
>>> b = look_and_say(a)
>>> next(b)
"1"
>>> next(a)
"3"
Si vous avez le temps, faites de même avec la fonction inverse:
>>> a = iter("12345")
>>> b = look_and_say_rev(a)
>>> next(b)
"2"
>>> next(a)
"3"
Aide¶
Si vraiment vous êtes bloqué·e·s, vous pouvez regarder ces articles :