Des règles et des lettres⚓︎
On se donne une chaine de caractères appelée motif ainsi qu'un ensemble de règles du type "Si le caractère lu est un a , remplace-le par ab".
L'ensemble de ces règles est stocké dans un dictionnaire Python dans lequel :
- une clé est un caractère lu,
- et la valeur associée est une chaine de caractères par laquelle le caractère doit être remplacé.
Si le caractère lu ne fait pas partie des clés du dictionnaire, il n'est associé à aucune règle et est donc recopié à l'identique.
Exemple
On prend pour règles {'a': 'ab', 'b': 'ac', 'c': 'd'}.
On prend pour motif de départ 'a'.
Après une transformation on obtient 'ab'.
Il est aussi possible d'effectuer cette transformation plusieurs fois de suite en l'appliquant à chaque étape au résultat de l'étape précédente.
Exemple
On garde pour règles {'a': 'ab', 'b': 'ac', 'c': 'd'}.
On prend pour encore motif de départ 'a'.
Après une transformation on obtient 'ab'.
Après deux transformations on obtient 'abac'.
Après trois transformations on obtient 'abacabd'.
Vous devez écrire deux fonctions Python :
-
transformation(motif, regles)prend en argument un motif initial (une chaine de caractères) ainsi qu'un ensemble de règles (un dictionnaire) et renvoie la chaine obtenue après une transformation. -
n_transformations(motif, regles, n)prend en argument un motif initial (une chaine de caractères), un ensemble de règles (un dictionnaire) ainsi qu'un entiernet renvoie le résultat obtenu aprèsntransformations.
Exemples
>>> regles = {"a": "ab", "b": "ac", "c": "d"}
>>> motif = "a"
>>> transformation(motif, regles)
'ab'
>>> n_transformations(motif, regles, 2)
'abac'
>>> n_transformations(motif, regles, 3)
'abacabd'
>>> motif = "abc"
>>> transformation(motif, regles)
'abacd'
>>> n_transformations(motif, regles, 3)
'abacabdabacdd'
>>> motif = "ddddd"
>>> n_transformations("ddddd", regles, 50)
'ddddd'
def transformation(motif, regles):bksl-nl ...bksl-nlbksl-nlbksl-nldef npy-undtransformations(motif, regles, n):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlregles = {"a": "ab", "b": "ac", "c": "d"}bksl-nlmotif = "a"bksl-nlassert transformation(motif, regles) == "ab"bksl-nlassert npy-undtransformations(motif, regles, 2) == "abac"bksl-nlassert npy-undtransformations(motif, regles, 3) == "abacabd"bksl-nlmotif = "abc"bksl-nlassert transformation(motif, regles) == "abacd"bksl-nlassert npy-undtransformations(motif, regles, 3) == "abacabdabacdd"bksl-nlmotif = "ddddd"bksl-nlassert npy-undtransformations("ddddd", regles, 50) == "ddddd"bksl-nlbksl-nldef transformation(motif, regles):bksl-nl resultat = ""bksl-nl for caractere in motif:bksl-nl if caractere in regles:bksl-nl resultat += regles[caractere]bksl-nl else:bksl-nl resultat += caracterebksl-nl return resultatbksl-nlbksl-nlbksl-nldef npy-undtransformations(motif, regles, n):bksl-nl for py-und in range(n):bksl-nl motif = transformation(motif, regles)bksl-nl return motifbksl-nlbksl-nl
A
Le problème s'apparente aux L-systèmes inventés en 1968 par le biologiste Aristid Lindenmayer afin de décrire le développement d'êtres vivants.
Une solution possible⚓︎
La fonction transformation commence par créer la chaine vide resultat.
On parcourt ensuite le motif. Pour chaque caractere :
-
si celui-ci fait partie des clés du dictionnaire
regles, on ajoute la valeur associée àresultat, -
sinon, on le recopie à l'identique.
On termine en renvoyant resultat.
Dans la fonction n_transformations, on réitère la transformation en prenant soin de mettre à jour le motif avec le résultat de transformation(motif, regles).
Remarque⚓︎
La concaténation de chaines de caractères (resultat += regles[caractere]) est "couteuse" en Python. Répéter cette action un grand nombre de fois peut allonger le temps d'exécution du code. Afin d'éviter ce désagrément, on préfère utiliser la méthode str.join. Dans ce cas, le code devient :
def transformation(motif, regles):
resultats = []
for caractere in motif:
if caractere in regles:
resultats.append(regles[caractere])
else:
resultats.append(caractere)
return "".join(resultats)
Solution fonctionnelle⚓︎
On pourrait aussi raccourcir le test central en faisant :
def transformation(motif, regles):
resultats = []
for caractere in motif:
resultat.append(regles[caractere] if caractere in regles else caractere)
return "".join(resultats)
En allant au bout de la démarche on obtiendrait un code fonctionnel en une ligne :
def transformation(motif, regles):
return "".join((regles[caractere] if caractere in regles else caractere for caractere in motif))
Z