Certains claviers de téléphones, virtuels ou « physiques », associent à chaque touche des caractères comme illustré sur la figure ci-dessous :
Il est ainsi possible d'encoder un message sous la forme d'un nombre. Toutefois, le message ne doit être constitué que de caractères alphabétiques, écrits en minuscule et non accentués. Il est aussi possible de représenter l'espace en utilisant le numéro 0. Dans toute la suite, on désignera par caractères valides ces caractères utilisables dans les messages.
Ce codage permet donc d'écrire le message "bonjour le monde" sous la forme du nombre 2665687053066633.
On souhaite utiliser cette méthode afin d'encoder et de décoder des messages.
1. Représenter le codage
On décide de représenter le codage illustré plus haut par un dictionnaire Python associant à chaque caractère valide, l'entier qui lui correspond.
Ce dictionnaire sera nommé CARACTERE_CHIFFRE et contiendra tous les caractères valides (lettres en minuscules et non accentuées, espace). On aura donc CARACTERE_CHIFFRE["a"]=2 et CARACTERE_CHIFFRE[" "]=0.
Le code représentant le message "abeille" est égal à 10 fois celui représentant le message "abeill" augmenté du code représentant "e".
3.1 Décoder un nombre (str)
type(code)isstr
Dans cette question, on représente les codes sous forme de chaînes de caractères.
L'opération inverse est plus problématique : en effet, les nombres 2 à 9 correspondent chacun à plusieurs caractères.
Le même code peut donc être interprété comme plusieurs messages distincts. C'est le cas par exemple du code "865387" qui représente, entre autres, les messages "voleur" et "volets".
On fournit le dictionnaire CHIFFRE_CARACTERE={"0":" ","2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs","8":"tuv","9":"wxyz"} qui associe à chaque chiffre valide, les caractères représentés. Le chiffre "1" ne représente aucun caractère ce qui explique qu'il n'apparaisse pas dans le dictionnaire.
Écrire la fonction decode qui prend en paramètre un code valide et renvoie la liste des chaînes de caractères représentées par cet entier.
On garantit que le code passé en paramètre compte moins de 5 chiffres valides et ne contient aucun chiffre "1" (qui ne représente aucun caractère valide).
La liste renvoyée pourra contenir des messages dans n'importe quel ordre : les tests compareront les versions triées des différentes listes.
soit une fonction récursive prenant en paramètres le code, l'indice du chiffre à lire dans celui-ci et un message en cours de construction ;
soit approche itérative utilisant une pile contenant des couples (indiceduchiffreàliredanslecode,message).
Aide (2)
Quelle que soit l'approche choisie, un message est entièrement construit lorsque l'indice du chiffre à lire est égal à la longueur du code.
On l'ajoute alors une liste de résultats.
Aide (3)
Dans le cas où l'indice du chiffre à lire est strictement inférieur à la longueur du code, on lit ce chiffre.
On ajoute alors chaque caractère qui lui est associé au message et, pour chaque message ainsi construit :
(approche récursive) on lance un appel récursif avec comme paramètres le code, l'indice suivant et le nouveau message ;
(approche itérative) on empile le couple formé de l'indice suivant et de ce nouveau message.
Dans le cas de la pile, le traitement est terminé lorsque la pile est vide.
3.2 Décoder un nombre (int)
type(code)isint
Dans cette question, on représente les codes sous forme de nombres entiers.
L'opération inverse est plus problématique : en effet, les chiffres de 2 à 9 correspondent chacun à plusieurs caractères.
Le même code peut donc être interprété comme plusieurs messages distincts. C'est le cas par exemple du nombre 865387 qui représente, entre autres, les messages "voleur" et "volets".
On fournit la liste CHIFFRE_CARACTERE=[" ",None,"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"] qui associe à chaque numéro/indice, les caractères représentés. Le nombre 1 ne représente aucun caractère ce qui explique que l'on ait CHIFFRE_CARACTERE[1]=None.
Écrire la fonction decode qui prend en paramètre un entier 0<code<10**4 et renvoie la liste des chaînes de caractères représentées par cet entier.
On garantit que le code passé en paramètre est strictement positif et ne contient aucun chiffre 1 (qui ne représente aucun caractère valide).
La liste renvoyée pourra contenir des messages dans n'importe quel ordre : les tests compareront les versions triées des différentes listes.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)