Apparier des rollers⚓︎
Le professeur d'EPS est mécontent. Après une séance de rollers avec ses élèves, il constate que ceux-ci ont abandonné leurs patins dans le désordre dans le vestiaire.
Il est donc face à un grand tas de rollers dans lequel les paires sont toutes mélangées... Pire : il manque peut-être certains patins !
Vous devez donc l'aider à vérifier que chaque patin pourra trouver une « âme sœur ».
Pour chaque roller, il connait deux informations : son genre ("gauche" ou "droit") et sa pointure (un entier entre 36 et 46 inclus l'un et l'autre).
Une paire valide est composée d'un patin gauche et d'un droit, l'un et autre ayant la même pointure.
Les rollers sont donnés sous forme d'une liste dans laquelle chaque élément est un tuple (genre, pointure).
Par exemple [("gauche", 40), ("gauche", 41), ("droit", 40)]. Cette liste ne permet pas d'apparier tous les patins : le patin ("gauche", 41) n'a pas de patin associé.
Écrire la fonction est_tas_valide qui prend en argument une liste décrivant les rollers et renvoie True ou False selon que chaque patin peut être apparié ou non.
Contrainte
Il est possible de résoudre ce problème en n'accédant qu'une unique fois aux caractéristiques de chaque patin.
Les tests supplémentaires vérifieront donc que, lors du traitement d'une liste de \(N\) rollers, l'algorithme utilisé n'accède pas plus de \(2 \times N\) fois à la liste.
Tri
Il est possible de résoudre cet exercice sans trier les patins ou leurs pointures. De plus pour de grandes listes de rollers, les tris sont longs à mettre en œuvre. Les fonctions de tri de Python (sorted et list.sort) sont donc interdites.
Exemples
>>> est_tas_valide([])
True
>>> est_tas_valide([("gauche", 40), ("droit", 40)])
True
>>> est_tas_valide([("gauche", 40), ("gauche", 41), ("droit", 40)])
False
def estpy-undtaspy-undvalide(rollers):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert estpy-undtaspy-undvalide([]) == Truebksl-nlassert estpy-undtaspy-undvalide([("gauche", 40), ("droit", 40)]) == Truebksl-nlassert estpy-undtaspy-undvalide([("gauche", 40), ("droit", 40), ("gauche", 41)]) == Falsebksl-nlbksl-nldef estpy-undtaspy-undvalide(rollers):bksl-nl paires = [0 for pointure in range(36, 47)]bksl-nl for genre, pointure in rollers:bksl-nl if genre == "gauche":bksl-nl paires[pointure - 36] += 1bksl-nl else:bksl-nl paires[pointure - 36] -= 1bksl-nlbksl-nl for valeur in paires:bksl-nl if valeur != 0:bksl-nl return Falsebksl-nl return Truebksl-nlbksl-nl
A
Une première approche consiste à :
- séparer les patins selon leur genre (gauche ou droit) ;
- trier chacune des deux listes obtenues ;
- s'assurer que les deux listes ont la même longueur. Dans le cas contraire on peut directement renvoyer
False; - comparer les éléments de chaque liste dans l'ordre croissant : si les éléments de même indice dans chaque liste n'ont pas la même pointure ils ne peuvent pas être appariés et la fonction peut renvoyer
False.
def est_tas_valide(rollers):
gauches = sorted([pointure for (genre, pointure) in rollers if genre == "gauche"])
droits = sorted([pointure for (genre, pointure) in rollers if genre == "droit"])
if len(gauches) != len(droits):
return False
for i in range(len(gauches)):
if gauches[i] != droits[i]:
return False
return True
Cette approche présente néanmoins l'inconvénient de trier les deux listes. Cette étape est coûteuse en nombre d'opérations et peut être évitée.
On utilise donc autant de compteurs qu'il y a de pointures différentes et l'on parcourt l'ensemble des rollers. Pour chacun, s'il est du genre "gauche", on incrémente le compteur de sa pointure, sinon on la décrémente. Ce fonctionnement ressemble
à l'utilisation d'une pile : on empile les rollers « gauche », on dépile les « droit ».
En fin de parcours, on teste la nullité de chaque valeur de paires. Si l'une des valeurs est non nulle, on renvoie immédiatement False. À l'inverse si aucun des valeurs est non nulle on renvoie True.
Ce dernier parcours testant la nullité des tests peut être écrit plus rapidement avec : return all(valeur == 0 for valeur in paires).
On utilise ici une liste afin de stocker les informations relatives à chaque pointure. Il serait aussi possible d'utiliser un dictionnaire :
def est_tas_valide(rollers):
paires = {pointure: 0 for pointure in range(36, 47)}
for genre, pointure in rollers:
if genre == "gauche":
paires[pointure] += 1
else:
paires[pointure] -= 1
for valeur in paires.values():
if valeur != 0:
return False
return True
Notons enfin que cette approche consistant à « compter » le nombre de rollers de chaque pointure est utilisée dans une méthode de tri classique : le tri par dénombrement (ou comptage).
Z