Solution du problème LookAndSay¶
Vous trouverez ici la solution pour l'exercice suivant :
Exercice de base¶
Version naïve¶
Pour obtenir le resultat il suffit de compter le nombre de fois qu'un élément se reproduit à la suite. Dès que l'on change d'élément alors on peut stocker le résultat:
def look_and_say(items):
result = list()
count = 1
prev_item = None
for i in items:
if prev_item is None:
# get first item
prev_item = i
continue
if prev_item != i:
result.append(str(count))
result.append(str(prev_item))
prev_item = i
count = 1
else:
count += 1
if prev_item is not None:
result.append(str(count))
result.append(str(prev_item))
return result
Par contre avec cette solution ca ne marche pas pour les entiers. Nous allons donc faire en sorte de pouvoir iterer sur les chiffres qui le composent. Pour cela, nous allons le faire en duck-typing: on va convertir le paramètre en entier puis en chaine de caractères. Si jamais cela tourne mal, on devrait déjà être sur un type que l'on gère:
def look_and_say(items):
try:
items = str(int(items))
except TypeError:
pass # Not an int, so it should already be an iterator
except ValueError:
pass # in case of empty entry
result = list()
count = 1
prev_item = None
for i in items:
if prev_item is None:
# get first item
prev_item = i
continue
if prev_item != i:
result.append(str(count))
result.append(str(prev_item))
prev_item = i
count = 1
else:
count += 1
if prev_item is not None:
result.append(str(count))
result.append(str(prev_item))
return result
Voila qui résoud l'exercice de base, mais de manière peu interressante...
Version plus évoluée¶
Il serait possible d'utiliser une regex afin d'itérer sur des éléments regroupés pas valeure, mais il y a une fonction dans le module itertools qui peut nous rendre de grands services groupby().
Le but de cette fonction étant justement de donner l'ensemble des éléments d'un iterable sans leur doubles successifs, un peu comme la fonction uniq sous Unix.
Là où cette focntion se démarque de uniq c'est qu'elle retourne un iterable avec la liste des éléments identiques; dont nous pourrons extraire le nombre de dupliqués en convertissant l'iterable en tuple puis en demandant sa taille.
Voila ce que cela donne:
from itertools import groupby
def look_and_say(items):
result = list()
try:
items = str(int(items))
except TypeError:
pass # Not an int, so it should already be an iterator
except ValueError:
pass # in case of empty entry
for k, g in groupby(items):
result.extend((str(len(tuple(g))), str(k)))
return result
Avouez que cela est plus simple non?
Bonus 1¶
Pour faire la fonction inverse, cela est très simple, il suffit de lire 2 entrées consécutive. le premier c'est le nombre de fois qu'il faut afficher le second:
def look_and_say_rev(items):
result = list()
try:
items = str(int(items))
except TypeError:
pass # Not an int, so it should already be an iterator
except ValueError:
pass # in case of empty entry
count = None
for i, c in enumerate(items):
if i % 2 == 0:
count = int(c)
else:
for _ in range(count):
result.append(c)
return result
Note
On a réutilisé les mêmes méchanismes que pour la fonciton directe pour gérer les differents types d'entrées...
Il y a pourtant moyen d'itérer de manière plus simple avec des paires d'éléments d'un iterable, en utilisant zip et l'itérateur de l'itérable.
Si a est l'iterateur, si on itere sur zip(a, a) alors on va lire une première fois dans a pour le premier element puis une nouvelle fois dans a pour le second, zip retournant un tuple de 2 éléments dans ce cas, on pourra lire plus facilement le code.
def look_and_say_rev(items):
result = list()
try:
items = str(int(items))
except TypeError:
pass # Not an int, so it should already be an iterator
except ValueError:
pass # in case of empty entry
iter_items = iter(items)
for c, k in zip(iter_items, iter_items):
for _ in range(int(c)):
result.append(k)
return result
Note
En suivant cette recette grouper on peut même faire en sorte de gérer un nombre configurable d'éléments consécutifs:
def grouper(iterable, n, fillvalue=None):
"Collect data into fixed-length chunks or blocks"
# grouper('ABCDEFG', 3, 'x') --> ABC DEF Gxx"
args = [iter(iterable)] * n
return zip_longest(*args, fillvalue=fillvalue)
Bonus 2¶
Afin de faire de notre fonction un generateur qui ne consomme pas tout le générateur que l'on pourrait avoir en entrée, la manière la plus simple est d'utiliser le mot clé yield:
from itertools import groupby
def look_and_say(items):
try:
items = str(int(items))
except TypeError:
pass # Not an int, so it should already be an iterator
except ValueError:
pass # in case of empty entry
for k, g in groupby(items):
yield str(len(tuple(g)))
yield str(k)
Par contre, il reste un endroit où la consomation memoire peut exploser: len(tuple(g)).
Note: Dans la vraie suite de Conway, on n'a jamais plus de 4 éléments successifs egaux, du coup cela impacte légérement mon propos, mais soit...
Et oui si notre entrée continent un très grand nombre d'éléments identiques successifs, nous les mettons tous en mémoire,
dans un tuple, et ce simplement pour calculer leur taille, on n'en fait rien d'autre.
Avouez que ce n'est pas très optimal.
Une façon plus efficace en mémoire pourrait être sum(1 for _ in g) ce qui nous donne:
from itertools import groupby
def look_and_say(items):
try:
items = str(int(items))
except TypeError:
pass # Not an int, so it should already be an iterator
except ValueError:
pass # in case of empty entry
for k, g in groupby(items):
yield str(sum(1 for _ in g))
yield str(k)
Pour la fonction inverse on va faire pareil:
def look_and_say_rev(items):
try:
items = str(int(items))
except TypeError:
pass # Not an int, so it should already be an iterator
except ValueError:
pass # in case of empty entry
iter_items = iter(items)
for c, k in zip(iter_items, iter_items):
for _ in range(int(c)):
yield k
Voila qui clos l'exercice, j'espère que vous avez appris des choses, à la prochaine.