Solution du problème Romans¶
Vous trouverez ici la solution pour l'exercice suivant:
Exercice de base¶
Tout d'abbord il va nous falloir une fonction qui convertisse un texte en chiffre.
import itertools
NUMERAL_VALUES = {
"M": 1000,
'D': 500,
'C': 100,
'L': 50,
'X': 10,
'V': 5,
'I': 1,
}
def roman_to_int(numeral):
value = 0
for current_char, next_char in itertools.zip_longest(numeral, numeral[1:]):
current_value = NUMERAL_VALUES.get(current_char, 0)
next_value = NUMERAL_VALUES.get(next_char, 0)
if next_value > current_value:
current_value = -current_value
value += current_value
return value
Maintenant que nous avons une petite fonction qui permette de transformer un texte en valeur, ecrire la classe RomanNumeral est assez simple. Il faut ecrire un constructeur qui utilise la méthode précédente. Nous devons aussi faire en sorte que l'on puisse caster notre objet en entier:
class RomanNumeral:
def __init__(self, numeral):
self.value = roman_to_int(numeral)
def __int__(self):
return self.value
Et voila. Ah mais non, IIII passe avec notre implementation actuelle.
Il va nous falloir une fonction de vérification de la légalité d'une chaine de caractères.
import re
ERRORS = (
"IL", "IC", "ID", "IM",
"VV",
"VX", "VL", "VC", "VD", "VM",
"XD", "XM",
"LL",
"LC", "LD", "LM",
"DD",
)
def is_legit_roman_numeral(numeral):
# Are characters repeated 4 times or more
if re.search(r'(.)\1{4,}', numeral):
return False
for e in ERRORS:
if e in numeral:
return False
return True
Et utiliser cette fonction dans notre constructeur:
class RomanNumeral:
def __init__(self, numeral):
if not is_legit_roman_numeral(numeral):
raise ValueError(f"'{numeral}' is not allowed in RomanNumeral")
self.value = roman_to_int(numeral)
Et si on met tout ensemble:
import itertools
import re
NUMERAL_VALUES = {
"M": 1000,
'D': 500,
'C': 100,
'L': 50,
'X': 10,
'V': 5,
'I': 1,
}
def roman_to_int(numeral):
value = 0
for current_char, next_char in itertools.zip_longest(numeral, numeral[1:]):
current_value = NUMERAL_VALUES.get(current_char, 0)
next_value = NUMERAL_VALUES.get(next_char, 0)
if next_value > current_value:
current_value = -current_value
value += current_value
return value
ERRORS = (
"IL", "IC", "ID", "IM",
"VV",
"VX", "VL", "VC", "VD", "VM",
"XD", "XM",
"LL",
"LC", "LD", "LM",
"DD",
)
def is_legit_roman_numeral(numeral):
# Are characters repeated 4 times or more
if re.search(r'(.)\1{4,}', numeral):
return False
for e in ERRORS:
if e in numeral:
return False
return True
class RomanNumeral:
def __init__(self, numeral):
if not is_legit_roman_numeral(numeral):
raise ValueError(f"'{numeral}' is not allowed in RomanNumeral")
self.value = roman_to_int(numeral)
def __int__(self):
return self.value
Voila enfin comment résoudre l'exercice de base
Bonus 1¶
Il suffit de redéfinir les fonctions spéciales de représentation en chaine de caractères.
Comme nous l'avons déjà vu auparavent, __repr__ permet de changer la représentation d'un objet, et __str__ permet de définir une conversion en chaine de caractères.
__repr__ est plus souvent utilisée pour l'affichage de debug, quand __str__ sert pour les affichages utilisateur.
(...)
class RomanNumeral:
def __init__(self, numeral):
if not is_legit_roman_numeral(numeral):
raise ValueError(f"'{numeral}' is not allowed in RomanNumeral")
self.value = roman_to_int(numeral)
self.numeral = numeral
def __str__(self):
return self.numeral
def __repr__(self):
return f"RomanNumeral('{self.numeral}')"
Et voila, le tour est joué.
Bonus 2¶
Il va nous falloir le contraire de la fonction numeral_to_int().
Il va falloir que cette methode soit dans la classe RomanNumeral et surtout qu'elle soit accessible même sans objet ROmanNumeral.
On dit que cette methode est une methode statique de la classe et non une methode qui s'applique sur une instance.
Pour parvenir à ce resultat, en python, il suffit d'ajouter le décorateur @staticmethod devant la definition de la methode,
et surtout de ne pas mettre le parametre self, car en effect cette methode peut s'executer sans instance.
Donc, il va nous falloir ecrire:
(...)
@staticmethod
def from_int(int_value):
pass
RomanNumeral.from_int(2).
Maintenant il faut reflechir a une façon de coder cette fonction. Une façon simple est de stocker la liste des valeurs de base avec leur ecriture. Ensuite pour chacune d'elles (en ordre decroissant) on retranche au fur et a mesure à notre parametre d'entrée tant que le resultat est positif:
(...)
@staticmethod
def from_int(int_value):
values = [
(1000, 'M'),
(900, 'CM'),
(500, 'D'),
(400, 'CD'),
(100, 'C'),
(90, 'XC'),
(50, 'L'),
(40, 'XL'),
(10, 'X'),
(9, 'IX'),
(5, 'V'),
(4, 'IV'),
(1, 'I'),
]
numeral = ""
for v, n in values:
while int_value >= v:
int_value -= v
numeral += n
return RomanNumeral(numeral)
Bonus 3¶
Ajoutons dorénavant le support des operations simples: addition, soustraction et multiplication.
Soit par des entires, soit par des instances de RomanNumeral.
Pour reussir cela, rien de plus simple (du moins au début). Il suffit de definir les méthodes spéciales en python:
* __add__ pour l'addition
* __sub__ pour la soustraction
* __mul__ pour la multiplication
Et oui quand on fait A + B, python appelle la méthode __add__ de la classe de A avec comme parametres A (self) et B.
Comme nous avons tout pour passer d'un type RomanNumeral a un entier et vice-versa, nous pouvons donc faire nos calculs en entier, pour ensuite retourner un RomanNumeral.
Par exemple pour l'addition:
(...)
def __add__(self, other):
return RomanNumeral.from_int(int(self) + int(other))
int mais aussi avec le type ROmanNumeral pour lequel nous avons précédement redéfini la fonction __int__. Petit bémol, on peut aussi additioner avec des flottants, ou toute autre classe qui support le cast en int, et pas seulement les entiers.
Autre problème: RomanNumeral("II") + 2 fonctionne et donne bien VI, mais 2 + RomanNumeral("II") échoue lamentablement avec ce message d'erreur:
TypeError: unsupported operand type(s) for +: 'int' and 'RomanNumeral'
Que ce passe-t-il donc? Python ne nous aime plus?
Regardons-y de plus prés. Je vous ai dit que faire A + B se traduisait par A.__add__(B)
Quand on fait 2 + B, python le traduit donc par 2.__add__(B), mais un int ne sait pas comment gerer le type B, d'où l'erreur pointée par Python.
Pour résoudre se problème (mais aussi les problèmes de non commutativité), Python permet aussi de définir une autre opération pour l'addition, l'addition a droite __radd__ qui fonctionne comme __add__ sauf que cette fois-ci, seft sera l'element de droite de l'addition.
Si on fait A + B, mais que A ne redefini pas l'addition (ou soulève une exception particulière dans ce cas), alors Python peut (si B redéfini l'addition a droite) traduire cela en B.__radd__(A).
Ici il faudra donc redéfinir aussi __radd__ afin de pouvoir faire des additions avec des ints placés à gauche.
Du coup, nous avons donc besoin de ce code:
(...)
def __add__(self, other):
return RomanNumeral.from_int(int(self) + int(other))
def __radd__(self, other):
return RomanNumeral.from_int(int(self) + int(other))
Devinez quoi, nous aurons le même problème que pour l'addition, avec la soustraction et la multiplication...
Et bien cela se resoudra de la même façon avec des opérateur à droite: __rsub__ et __rmul__
Ce qui nous donne le code suivant à rajouter:
(...)
def __add__(self, other):
return RomanNumeral.from_int(int(self) + int(other))
def __radd__(self, other):
return RomanNumeral.from_int(int(self) + int(other))
def __sub__(self, other):
return RomanNumeral.from_int(int(self) - int(other))
def __rsub__(self, other):
return RomanNumeral.from_int(int(other) - int(self))
def __mul__(self, other):
return RomanNumeral.from_int(int(self) * int(other))
def __rmul__(self, other):
return RomanNumeral.from_int(int(self) * int(other))
Notez que dans notre cas, on a affaire a des operations commutatives, donc on pourrait tout a fait appeler __add__ de puis __radd__, sauf pour la soustraction, ou la ce n'est pas commutatif (A-B n'est pas equal a B-A)!
Bonus 4¶
Ajoutons de l'ordre pour notre classe afin que l'on puisse trier cela.
Pour cela, il va nous falloir ajouter quelque methodes particulières:
* __eq__ pour l'égalité
* __gt__ pour savoir si on est plus grand
* __ge__ pour savoir si on est plus grand ou égal
* __lt__ pour plus petit
* __le__ pour plus petit ou égal
Pour l'égalité, nous devons voir si un RomanNumeral est égal ou non a un entier, un autre RomanNumeral ou une chaine de caractères.
Il suffit d'essayer de convertir les deux parties en entier et de les comparer:
def __eq__(self, other):
return int(self) == int(other)
ROmanNumeral, mais pas pour les chaines de caractères...
Je ne sais pas si vous vous souvenez, mais un des principes de Python est le duck typing; en gros, on essaie, et si ca marche pas on avise, au lieu d'essayer en amont de deviner ce qui va se passer.
Et bien la, mettons le en oeuvre avec une gestion d'exception qui sera levée par int(other) si other est ne chaine de caractères. Dans ce cas, il faudra comparer les chaines de caractères:
(...)
def __eq__(self, other):
try:
return int(self) == int(other)
except ValueError:
return str(self) == str(other)
Enfin, cela serait bien si cela ne posait pas quelques problèmes. A votre avis, que se passerait-il si on demandait au code si "III" est égal à 3.5? et bien il dirait que oui, ils sont égaux. Et si une instance de classe dont la conversion en string vallait "III", cela sera aussi égal, alors que l'on ne veut pas forcement...
Encore un autre problème, vous vous souvenez des fonctions comme __radd__? A votre avis, comment Python fait-il pour "se dire" qu'il faut utiliser __radd__? Et bien c'est assez simple, si la fonction __add__ retourne NotImplemented, alors Python cherchera une alternative comme appeler __radd__.
Donc, prenons un peu sur nous pour (une fois) ne pas utiliser le duck typing:
(...)
def __eq__(self, other):
if isinstance(other, int) or isinstance(other, RomanNumeral):
return self.value == int(other)
if isinstance(other, str):
return self.numeral == other
return NotImplemented
Pour les relations d'ordre, on va devoir faire la même chose, mais il faut interdire la vérification avec les chaines de caractères cette fois-ci. Let's go alors...
(...)
def __gt__(self, other):
if isinstance(other, int) or isinstance(other, RomanNumeral):
return self.value > int(other)
return NotImplemented
fonctools propose un décorateur total_ordering, à appliquer à une classe, qui permet de déduire les autres fonctions à partir de 2 fonctions comme == et >.
Par exemple, < est vrai si non == et non >. On peut aussi déduire les autres (vous pouvez vérifier).
Le seul hic avec cette solution, c'est si vous avez besoin de performance pour les relations d'ordre. En effet, cette solution augment le temps de calcul car il faut faire plusieurs appels (aux comparateurs écrits) au lieu d'un code dédié.
Voici donc ma solution (c'est un peu long mais finalement ca se comprend bien et ca se lit très vite):
import itertools
import functools
import re
NUMERAL_VALUES = {
"M": 1000,
'D': 500,
'C': 100,
'L': 50,
'X': 10,
'V': 5,
'I': 1,
}
def roman_to_int(numeral):
value = 0
for current_char, next_char in itertools.zip_longest(numeral, numeral[1:]):
current_value = NUMERAL_VALUES.get(current_char, 0)
next_value = NUMERAL_VALUES.get(next_char, 0)
if next_value > current_value:
current_value = -current_value
value += current_value
return value
ERRORS = (
"IL", "IC", "ID", "IM",
"VV",
"VX", "VL", "VC", "VD", "VM",
"XD", "XM",
"LL",
"LC", "LD", "LM",
"DD",
)
def is_legit_roman_numeral(numeral):
# Are characters repeated 4 times or more
if re.search(r'(.)\1{4,}', numeral):
return False
for e in ERRORS:
if e in numeral:
return False
return True
@functools.total_ordering
class RomanNumeral:
def __init__(self, numeral):
if not is_legit_roman_numeral(numeral):
raise ValueError(f"'{numeral}' is not allowed in RomanNumeral")
self.value = roman_to_int(numeral)
self.numeral = numeral
def __int__(self):
return self.value
def __str__(self):
return self.numeral
def __repr__(self):
return f"RomanNumeral('{self.numeral}')"
@staticmethod
def from_int(int_value):
values = [
(1000, 'M'),
(900, 'CM'),
(500, 'D'),
(400, 'CD'),
(100, 'C'),
(90, 'XC'),
(50, 'L'),
(40, 'XL'),
(10, 'X'),
(9, 'IX'),
(5, 'V'),
(4, 'IV'),
(1, 'I'),
]
numeral = ""
for v, n in values:
while int_value >= v:
int_value -= v
numeral += n
return RomanNumeral(numeral)
def __add__(self, other):
return RomanNumeral.from_int(int(self) + int(other))
def __radd__(self, other):
return RomanNumeral.from_int(int(self) + int(other))
def __sub__(self, other):
return RomanNumeral.from_int(int(self) - int(other))
def __rsub__(self, other):
return RomanNumeral.from_int(int(other) - int(self))
def __mul__(self, other):
return RomanNumeral.from_int(int(self) * int(other))
def __rmul__(self, other):
return RomanNumeral.from_int(int(self) * int(other))
def __eq__(self, other):
if isinstance(other, int) or isinstance(other, RomanNumeral):
return self.value == int(other)
if isinstance(other, str):
return self.numeral == other
return NotImplemented
def __gt__(self, other):
try:
return int(self) > int(other)
except ValueError:
return NotImplemented
Il est tout a fait possible d'utiliser des methodes statiques au lieu des fonctions qui sont hors de la classe dans ma solution, libre au lecteur de tester.
Voila, j'espère que ça vous à plus, à la prochaine et portez-vous bien.