Certains s'empilent, d'autres se défilent...

Des chapeaux et des bonhommes de neige¶

Cinq chapeaux empilés sont distribués, en commençant en haut et allant vers le bas, à cinq bons hommes de neige en commençant à gauche et finissant à droite. À la fin, chaque bonhomme de neige devrait recevoir un chapeau à sa taille.

Quelle pile de chapeaux correspond à quelle rangée de bonshommes de neige ?

Une pile de chapeaux¶

On représente un chapeau par un objet de type Chapeau qui possède un attribut taille qui représente sa taille : ainsi le plus petit chapeau a une taille de 1, et le plus grand chapeau a une taille de 5. On modélise une pile de chapeaux par un objet de type Pile.

Les interfaces des classes Chapeau et Pile sont les suivantes :

classe Chapeau

Fonction Signature Description

Chapeau(c) int -> Chapeau Renvoie un chapeau de taille c

c.affiche() () -> None Affiche le chapeau c

classe Pile

Fonction	Signature	Description
`Pile()`	`() -> Pile`	Créer une pile vide
`p.est_vide()`	`() -> Bool`	Détermine si la pile `p` est vide.
`p.empiler(c)`	`Chapeau -> None`	Déposer le chapeau `c` au sommet de la pile `p`
`p.depiler()`	`() -> Chapeau`	Renvoie le chapeau au sommet de la pile `p`,
		lorsque cela est possible.
`p.affiche()`	`() -> None`	Affiche la pile `p` sans la modifier.

Exécuter le bloc ci-dessous pour charger les classes Chapeau et Pile.

###

#--- HDR ---#bksl-nlclass Chapeau:bksl-nl def py-undpy-undinitpy-undpy-und(self, t):bksl-nl self.taille = tbksl-nlbksl-nl def py-undpy-undreprpy-undpy-und(self):bksl-nl return f"Chap. {self.taille}"bksl-nlbksl-nl def affiche(self):bksl-nl print(self)bksl-nlbksl-nlclass Pile:bksl-nl def py-undpy-undinitpy-undpy-und(self, maxpy-undelt = float('inf')):bksl-nl self.contenu = []bksl-nl self.maxpy-undelt = maxpy-undeltbksl-nlbksl-nl def py-undpy-undreprpy-undpy-und(self):bksl-nl return "[" + ", ".join(b.py-undpy-undreprpy-undpy-und() for b in self.contenu) + "] (Sommet pile)" bksl-nlbksl-nl def affiche(self):bksl-nl print(self)bksl-nlbksl-nl def estpy-undvide(self):bksl-nl return self.contenu == []bksl-nlbksl-nl def estpy-undpleine(self):bksl-nl return self.maxpy-undelt == len(self.contenu)bksl-nlbksl-nl def empiler(self, c):bksl-nl # assert isinstance(c, Chapeau)bksl-nl if self.estpy-undpleine():bksl-nl raise IndexError("Capacité maximale de la pile atteinte")bksl-nl self.contenu.append(c)bksl-nlbksl-nl def depiler(self):bksl-nl if self.estpy-undvide():bksl-nl raise IndexError("Impossible de dépiler : la pile est vide.")bksl-nl return self.contenu.pop()bksl-nl#--- HDR ---#bksl-nl# Exécuter ce bloc AVANT de traiter les exercices.bksl-nl# Charge les classes Chapeau et Pile.bksl-nlbksl-nlc = Chapeau(1)bksl-nlp = Pile()bksl-nlp.empiler(c)bksl-nlp.empiler(Chapeau(2))bksl-nlp.affiche()bksl-nlprint(p.depiler())bksl-nlbksl-nl

Écrire le code python d'une fonction init_piles qui renvoie les 4 piles p1, p2, p3 et p4 représentant respectivement les piles de chapeaux 1, 2, 3, et 4.

###

def testpy-undpilepy-undexemple():bksl-nl """ Tests pour la fonction pilepy-undexemple """bksl-nl print("Tests de pilepy-undexemple passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import pilepy-undexemplebksl-nl# testpy-undpilepy-undexemple()bksl-nlbksl-nl 5/5

def initpy-undpiles():bksl-nl p1 = Pile()bksl-nl # p1.empiler(...)bksl-nl # ...bksl-nl # À compléterbksl-nl return p1, p2, p3, p4bksl-nlbksl-nl

Une file de bonshommes de neige¶

On représente un bonhomme de neige par un objet de type Bonhomme muni d'un attribut taille qui représente sa taille : ainsi le plus petit bonhomme de neige a une taille de 1, et le plus grand bonhomme de neige a une taille de 5. Si b est un objet de type Bonhomme et c un objet de type Chapeau, alors b.content(c) renvoie True si et seulement si le chapeau c est celui du bonhomme b.

On modélise une file de bonshommes de neige par un objet de type File, qui contient les bonshommes de neige.

Les interfaces des classes Bonhomme et File sont les suivantes :

classe Bonhomme

Fonction	Signature	Description
`Bonhomme(b)`	`int -> Bonhomme`	Renvoie un bonhomme de taille `b`
`b.content(c)`	`Chapeau -> Bool`	Renvoie `True` si le chapeau `c` convient au bonhomme `b`
`b.affiche()`	`() -> None`	Affiche le bonhomme `b`

classe File

Fonction	Signature	Description
`File()`	`() -> File`	Créer une file vide
`f.est_vide()`	`() -> Bool`	Détermine si la file `f` est vide.
`f.enfiler(c)`	`Bonhomme -> None`	Déposer le bonhomme `b` à la fin de la file `f`
`f.defiler()`	`() -> Bonhomme`	Renvoie le premier bonhomme de la file `f`,
		lorque cela est possible.
`f.affiche()`	`() -> None`	Affiche la file `f` sans la modifier.

Exécuter le bloc ci-dessous pour charger les classes Bonhomme et File.

###

#--- HDR ---#bksl-nlclass Bonhomme:bksl-nl def py-undpy-undinitpy-undpy-und(self, t):bksl-nl self.taille = tbksl-nlbksl-nl def py-undpy-undreprpy-undpy-und(self):bksl-nl return f"Bonh. {self.taille}"bksl-nlbksl-nl def affiche(self):bksl-nl print(self)bksl-nlbksl-nl def content(self, c):bksl-nl return c.taille == self.taillebksl-nlbksl-nlclass File:bksl-nl def py-undpy-undinitpy-undpy-und(self, maxpy-undelt = float('inf')):bksl-nl self.contenu = []bksl-nl self.maxpy-undelt = maxpy-undeltbksl-nlbksl-nl def py-undpy-undreprpy-undpy-und(self):bksl-nl return "(Début file) [" + ", ".join(b.py-undpy-undreprpy-undpy-und() for b in self.contenu) + "]"bksl-nlbksl-nl def affiche(self):bksl-nl print(self)bksl-nlbksl-nl def estpy-undvide(self):bksl-nl return self.contenu == []bksl-nlbksl-nl def estpy-undpleine(self):bksl-nl return len(self.contenu) == self.maxpy-undelt bksl-nlbksl-nl def enfiler(self, b):bksl-nl # assert isinstance(b, Bonhomme)bksl-nl if self.estpy-undpleine():bksl-nl raise IndexError("Capacité maximale de la file atteinte")bksl-nl self.contenu.append(b)bksl-nlbksl-nl def defiler(self):bksl-nl if self.estpy-undvide():bksl-nl raise IndexError("Impossible de défiler : la file est vide.")bksl-nl return self.contenu.pop(0)bksl-nl#--- HDR ---#bksl-nl# Exécuter ce bloc AVANT de traiter les exercices.bksl-nl# Charge les classes Bonhomme et File.bksl-nlbksl-nlb = Bonhomme(1)bksl-nlf = File()bksl-nlf.enfiler(b)bksl-nlf.enfiler(Bonhomme(2))bksl-nlf.affiche()bksl-nlprint(f.defiler())bksl-nlbksl-nl

Écrire le code python d'une fonction init_files qui renvoie les 4 files f1, f2, f3 et f4 représentant respectivement les files de bonshommes de neige 1, 2, 3, et 4.

###

def testpy-undfilepy-undexemple():bksl-nl """ Tests pour la fonction filepy-undexemple """bksl-nl print("Tests de filepy-undexemple passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import filepy-undexemplebksl-nl# testpy-undfilepy-undexemple()bksl-nlbksl-nl 5/5

def initpy-undfiles():bksl-nl f1 = File()bksl-nl # f1.enfiler(...)bksl-nl # ...bksl-nl # À compléter.bksl-nl return f1, f2, f3, f4bksl-nlbksl-nl

Compatiblité entre pile de chapeaux et file de bonshommes¶

On dit qu'une pile de chapeaux est compatible avec une file de bonshommes de neige si et seulement si tous les bonhommes de neige sont content lorsqu'ils prennent le premier chapeau de la pile dans l'ordre imposé par la file.

On se propose de résoudre le problème de l'association d'une pile de chapeaux avec une file de bonshommes de neige. On souhaite écrire une fonction compatibles qui étant donné une pile de chapeaux p et une file de bonshommes de neige f, renvoie True si et seulement si les deux structures sont compatibles.

###

def testpy-undcompatibles():bksl-nl """ Tests pour la fonction compatibles """bksl-nl print("Tests de compatibles passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import compatiblesbksl-nl# testpy-undcompatibles()bksl-nlbksl-nl 5/5

def compatibles(p, f):bksl-nl """ Pile, File -> Boolbksl-nl Détermine si les chapeaux sont associés aux bon bonshommes """bksl-nl passbksl-nlbksl-nl

Le problème de la mutabilité et solution du problème¶

Afficher le contenu des piles p1 et f1 après exécution de la fonction compatibles.
Que constate-t-on ? À quoi cela est-il dû ?
Quel problème cela va-t-il éventuellement poser ?

Modification de la fonction `compatibles`¶

On souhaite modifier le code de la fonction compatibles afin qu'à la fin de l'exécution de l'instruction compatibles(p, f), les piles p et f soient dans le même état qu'au début.

Pour cela, lors de l'exécution de la fonction compatibles, à chaque dépilement (resp. défilement) de la pile p (resp. f) on empilera le chapeau c (resp. enfilera le bonhomme b) obtenu dans une pile pile_aux (resp. une file file_aux), et on s'assurera de restaurer l'état initial avant toute instruction return.

On écrira pour cela une fonction restaure_pile(p, p_aux) (resp. restaure_file(f, f_aux)) restaurant l'état initial de p à l'aide de p_aux (resp. f à l'aide de f_aux). On donne ci-dessous un schéma explicatif de l'algorithme de la fonction restaure_pile. Une idée similaire est à adapter pour la fonction restaure_file.

###

def testpy-undrestaurepy-undpile():bksl-nl """ Tests pour la fonction restaurepy-undpile """bksl-nl print("Tests de restaurepy-undpile passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import restaurepy-undpilebksl-nl# testpy-undrestaurepy-undpile()bksl-nlbksl-nl 5/5

def restaurepy-undpile(p, ppy-undaux):bksl-nl """ Pile, Pile -> Nonebksl-nl Restaure p à son état initial lorsque les dépilements successifsbksl-nl on été empilés dans ppy-undaux. """bksl-nl while not p.estpy-undvide():bksl-nl c = p.depiler()bksl-nl ppy-undaux.empiler(c)bksl-nl while not ppy-undaux.estpy-undvide():bksl-nl # À compléterbksl-nlbksl-nldef restaurepy-undfile(f, fpy-undaux):bksl-nl """ File, File -> Nonebksl-nl Restaure f à son état initial lorsque les défilement successifsbksl-nl on été enfilés dans fpy-undaux. """bksl-nl passbksl-nlbksl-nldef compatibles(p, f):bksl-nl """ Pile, File -> Boolbksl-nl Détermine si les chapeaux sont associés aux bons bonshommesbksl-nl L'état de la pile p et la file f sera le même avant et après exécution """bksl-nl passbksl-nlbksl-nl

###

def testpy-undrestaurepy-undpile():bksl-nl """ Tests pour la fonction restaurepy-undpile """bksl-nl print("Tests de restaurepy-undpile passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import restaurepy-undpilebksl-nl# testpy-undrestaurepy-undpile()bksl-nlbksl-nl 5/5

def restaurepy-undpile(p, ppy-undaux):bksl-nl """ Pile, Pile -> Nonebksl-nl Restaure p à son état initial lorsque les dépilements successifsbksl-nl on été empilés dans ppy-undaux. """bksl-nl while not p.estpy-undvide():bksl-nl c = p.depiler()bksl-nl ppy-undaux.empiler(c)bksl-nl while not ppy-undaux.estpy-undvide():bksl-nl # À compléterbksl-nlbksl-nldef restaurepy-undfile(f, fpy-undaux):bksl-nl """ File, File -> Nonebksl-nl Restaure f à son état initial lorsque les défilement successifsbksl-nl on été enfilés dans fpy-undaux. """bksl-nl passbksl-nlbksl-nldef compatibles(p, f):bksl-nl """ Pile, File -> Boolbksl-nl Détermine si les chapeaux sont associés aux bons bonshommesbksl-nl L'état de la pile p et la file f sera le même avant et après exécution """bksl-nl passbksl-nlbksl-nl

Calcul de la solution du problème¶

Écrire une fonction solution qui renvoie la liste des couples solution au problème.

Par exemple, si la pile de chapeau numéro 1 correspond à la file de bonhomme de neige 2, alors on ajoutera l'entrée (1, 2) à la liste des couples solution.

###

def testpy-undsolution():bksl-nl """ Tests pour la fonction solution """bksl-nl print("Tests de solution passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import solutionbksl-nl# testpy-undsolution()bksl-nlbksl-nl 5/5

def solution():bksl-nl """ () -> [(int, int)]bksl-nl Renvoie la liste des associations pile i <-> file j """bksl-nl piles = initpy-undpiles()bksl-nl files = initpy-undfiles()bksl-nl sol = []bksl-nl # À compléterbksl-nlbksl-nl

Une rampe de billes¶

Sur une rampe, il y a 10 billes numérotées dans l'ordre. Le long de la rampe, il y a trois trous \(A\), \(B\) et \(C\) : le trou \(A\) peut contenir trois billes au maximum, le trou \(B\) deux billes et le trou \(C\) une seule bille au maximum.

Quand les billes roulent sur la rampe, elles tombent successivement dans les trous jusqu'à ce qu'elles les remplissent (les billes 1, 2 et 3 tombent dans le trou \(A\), les billes 4 et 5 tombent dans le trou \(B\) et la bille 6 tombe dans le trou \(C\)). Les autres billes passent par-dessus et continuent leur chemin jusqu'à la fin de la rampe.

Quand toutes les billes ont parcouru la rampe, les ressorts, placés dans les trous \(A\) à \(C\), éjectent les billes qu'ils contenaient : d'abord, les trois billes du trou \(A\), ensuite, celles du trou \(B\) et finalement, celle du trou \(C\). Les billes sont ainsi poussées sur la rampe. On attend que toutes les autres billes aient passé avant qu'un ressort ne soit relâché.

Dans quel ordre les billes de la séquence 1 à 10 seront-elles alignées à la fin ?

Sur une installation du même type, dix billes initialement ordonnées de 1 à 10 sur la rampe arrivent dans l'ordre : 8, 9, 10, 4, 3, 2, 1, 5, 7, 6.

Combien de trous y avait-il sur le parcours, et quelle est leur profondeur ? On justifiera la réponse. 3. Compléter la fonction arrivee_rampe(profondeurs) qui prend en paramètre une liste d'entiers donnant la profondeur de chacun des trous sur une installation du même type que celle vue précédemment, dans l'ordre dans lequel ils sont positionnés sur le parcours, et qui renvoie la liste des entiers 1 à 10, dans l'ordre dans lequel les billes 1 à 10 arriveraient sur la rampe.

On utilisera pour cela les classes Pile et File définies précédemment. Ces classes ont toutes les deux été enrichies d'un attribut max_elt et d'une méthode est_pleine qui renvoie True si et seulement si la pile (resp. file) contient max_elt éléments. Lors d'un empilement (resp. enfilement), on vérifie d'abord que la pile (resp. file) n'est pas pleine. Si la pile (resp. file) est pleine, alors on soulève une exception. On appelle ce genre de pile (resp. files) des piles (resp. files) bornées.

Fonction	Signature	Description
`Pile(max_elt = n)`	`int -> Pile`	Renvoie une pile bornée de capacité maximale `n`
`p.est_pleine()`	`() -> Bool`	Détermine si la pile a atteint sa capacité maximale.
`File(max_elt = n)`	`int -> File`	Renvoie une file bornée de capacité maximale `n`
`f.est_pleine()`	`() -> Bool`	Détermine si la file a atteint sa capacité maximale.

###

def testpy-undarrivepy-undrampe():bksl-nl """ Tests pour la fonction arrivepy-undrampe """bksl-nl print("Tests de arrivepy-undrampe passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import arrivepy-undrampebksl-nl# testpy-undarrivepy-undrampe()bksl-nlbksl-nl 5/5

def arriveepy-undrampe(profondeur):bksl-nl """ [int] -> [int]bksl-nl Détermine l'ordre d'arrivée des boules numérotées de 1 à 10 """bksl-nl rampepy-undlancement = File()bksl-nl for b in [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]:bksl-nl ... # à compléterbksl-nl piles = [Pile(maxpy-undelt = p) for p in profondeur] # liste de piles bornées, dans l'ordre du parcours.bksl-nl rampepy-undfinale = File() # billes dans l'ordre d'arrivéebksl-nl numeropy-undpile = 0 # indice de la pile à remplirbksl-nl bksl-nl # on remplit les piles dans l'ordre dans lequel elles sontbksl-nl # positionnées sur le parcours tant que cela est possiblebksl-nl # (c'est à dire tant que la dernière pile du parcours n'est pas vide)bksl-nl # Si la pile que l'on cherche à remplir est pleine,bksl-nl # alors il faut commencer par changer le numéro de la pile à remplir. bksl-nl # On empile une bille prise depuis la rampe de lancement sur la pile à remplir.bksl-nl while ...:bksl-nl ... # à compléterbksl-nl bksl-nl # Toutes les billes restantes roulent directement dans la rampe d'arrivée.bksl-nl while ...:bksl-nl ... # à compléterbksl-nl bksl-nl # On retire les ressorts dans l'ordre dans lesquels ils sontbksl-nl # positionnés sur le parcours. Les billes ressortent des trous etbksl-nl # viennent s'accumuler sur la rampe de lancement.bksl-nl for p in piles:bksl-nl while ...:bksl-nl ... # à compléterbksl-nlbksl-nl return rampepy-undfinalebksl-nlbksl-nl

Conclusion¶

En anglais, l'acronyme FILO signifie Firt In Last Out (premier entré dernier sorti), et l'acronyme FIFO signifie Fist In First Out (premier entré premier sorti).

Quel acronyme peut s'appliquer à une pile ? À une file ?

Fonction	Signature	Description
`Chapeau(c)`	`int -> Chapeau`	Renvoie un chapeau de taille `c`
`c.affiche()`	`() -> None`	Affiche le chapeau `c`