Aller au contenu

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

🐍 Console Python
>>> est_tas_valide([])
True
>>> est_tas_valide([("gauche", 40), ("droit", 40)])
True
>>> est_tas_valide([("gauche", 40), ("gauche", 41), ("droit", 40)])
False
###
from random import shuffle, randrangebksl-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-nl# Tests supplémentairesbksl-nlbksl-nl# Nombre de lecture de valeurs inférieur à 2.001 py-str len(rollers)bksl-nlclass Liste(list):bksl-nl def py-undpy-undinitpy-undpy-und(self, valeurs):bksl-nl self.nbpy-undlectures = 0bksl-nl super().py-undpy-undinitpy-undpy-und(valeurs)bksl-nlbksl-nl def py-undpy-undgetitempy-undpy-und(self, i):bksl-nl self.nbpy-undlectures += 1bksl-nl return super().py-undpy-undgetitempy-undpy-und(i)bksl-nlbksl-nl def py-undpy-unditerpy-undpy-und(self):bksl-nl return Iterateur(self)bksl-nlbksl-nlbksl-nlclass Iterateur:bksl-nl def py-undpy-undinitpy-undpy-und(self, valeurs):bksl-nl self.valeurs = valeursbksl-nl self.indice = -1bksl-nlbksl-nl def py-undpy-unditerpy-undpy-und(self):bksl-nl return selfbksl-nlbksl-nl def py-undpy-undnextpy-undpy-und(self):bksl-nl self.indice += 1bksl-nl if self.indice < len(self.valeurs):bksl-nl return self.valeurs[self.indice]bksl-nl else:bksl-nl raise StopIterationbksl-nlbksl-nlnbpy-undpaires = 10py-und000bksl-nlrollers = [("gauche", randrange(36, 47)) for py-und in range(nbpy-undpaires)]bksl-nlrollers.extend([("droit", pointure) for py-und, pointure in rollers])bksl-nlshuffle(rollers)bksl-nlrollers = Liste(rollers)bksl-nlassert estpy-undtaspy-undvalide(rollers)bksl-nlnbpy-undlectures = rollers.nbpy-undlecturesbksl-nlnbpy-undmax = 2.001 py-str len(rollers)bksl-nlassert nbpy-undlectures <= nbpy-undmax, f"Le code a lu {nbpy-undlectures} valeurs de la liste qui comporte {nbpy-undpaires} rollers. Il faut optimiser le code..."bksl-nlbksl-nl# Listes validesbksl-nlfor py-und in range(5) :bksl-nl nbpy-undpaires = randrange(500, 1001)bksl-nl rollers = [("gauche", randrange(36, 47)) for py-und in range(nbpy-undpaires)]bksl-nl rollers.extend([("droit", pointure) for py-und, pointure in rollers])bksl-nl shuffle(rollers)bksl-nl assert estpy-undtaspy-undvalide(rollers)bksl-nlbksl-nl# Listes invalidesbksl-nl# Plus de droit que de gauchebksl-nlfor py-und in range(5) :bksl-nl nbpy-undpaires = randrange(500, 1001)bksl-nl rollers = [("gauche", randrange(36, 47)) for py-und in range(nbpy-undpaires)]bksl-nl rollers.extend([("droit", pointure) for py-und, pointure in rollers])bksl-nl rollers.append(("droit", randrange(36, 47)))bksl-nl shuffle(rollers)bksl-nl assert not estpy-undtaspy-undvalide(rollers)bksl-nl# Plus de gauche que de droitbksl-nlfor py-und in range(5) :bksl-nl nbpy-undpaires = randrange(500, 1001)bksl-nl rollers = [("gauche", randrange(36, 47)) for py-und in range(nbpy-undpaires)]bksl-nl rollers.extend([("droit", pointure) for py-und, pointure in rollers])bksl-nl rollers.append(("gauche", randrange(36, 47)))bksl-nl shuffle(rollers)bksl-nl assert not estpy-undtaspy-undvalide(rollers)bksl-nl# Autant de chaque genre mais problème de pointuresbksl-nlfor py-und in range(5) :bksl-nl nbpy-undpaires = randrange(500, 1001)bksl-nl rollers = [("gauche", randrange(36, 47)) for py-und in range(nbpy-undpaires)]bksl-nl rollers.extend([("droit", pointure) for py-und, pointure in rollers])bksl-nl rollers.append(("droit", randrange(36, 40)))bksl-nl rollers.append(("gauche", randrange(40, 47)))bksl-nl shuffle(rollers)bksl-nl assert not estpy-undtaspy-undvalide(rollers)bksl-nl 5/5

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-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-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.
🐍 Script Python
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 :

🐍 Script Python
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