Exercices

Exercice 1

Exercice 5 du sujet Centres Étrangers 1 - 2021

Correction Q1.

image

Correction Q2.

image

Correction Q3.
1
2
3
4
5
6
7
8
9
def maximum(P):
    if est_vide(P):
        return None
    m = depile(P)
    while not est_vide(P):
        val = depile(P)
        if val > m:
            m = val
    return m

Avec le code ci-dessus, la pile P est vide à la fin de l'exécution. Pour éviter cela, on peut par exemple créer une pile Q temporaire qui recevra les éléments de Q, avant de retransférer à la fin du programme les éléments de Q dans P.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def maximum(P):
    Q = creer_pile()
    if est_vide(P):
        return None
    m = depile(P)
    empile(Q, m)
    while not est_vide(P):
        val = depile(P)
        empile(Q, val)
        if val > m:
            m = val
    while not est_vide(Q):
        empile(P, depile(Q))
    return m
Correction Q4.

Q4a. On va vider la pile P dans une pile Q tout en comptant le nombre d'éléments dépilés dans une variable t. On redonne ensuite à P son état initial en vidant Q dans P.

Q4b

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def taille(P):
    if est_vide(P):
        return 0
    Q = creer_pile()
    t = 0
    while not est_vide(P):
        empile(Q, depile(P))
        t += 1
    while not est_vide(Q):
        empile(P, depile(Q))
    return t

Exercice 2

Exercice 1 du sujet La Réunion J2 - 2022

Correction Q1.

image

Correction Q2.a.

La variable temp contient la valeur 25.

Correction Q2.b.

p1 est identique, elle contient toujours les valeurs 25, 3 et 7.

Correction Q3.
1
2
3
4
def addition(p):
    nb1 = depiler(p)
    nb2 = depiler(p)
    empiler(p, nb1 + nb2)
Correction Q4.
1
2
3
4
5
6
p = pile_vide()
empiler(p, 3)
empiler(p, 5)
addition(p)
empiler(p, 7)
multiplication(p)

Exercice 3

Exercice 2 du sujet Métropole Candidats Libres J1 - 2021

Correction Q1.a.
1
2
3
4
pile1 = Pile()
pile1.empiler(7)
pile1.empiler(5)
pile1.empiler(2)
Correction Q1.b.

L'affichage produit est 7, 5, 5, 2.

Correction Q2.a.
  • Cas n°1 : 3, 2
  • Cas n°2 : 3, 2, 5, 7
  • Cas n°3 : 3
  • Cas n°4 : «pile vide»
Correction Q2.b

La fonction mystere permet d'obtenir la pile retournée jusqu'à un élément particulier (s'il existe).

Correction Q3.
1
2
3
4
def etendre(pile1, pile2):
    while not pile2.est_vide():
        val = pile2.depiler()
        pile1.empiler(val)
Correction Q4.
1
2
3
4
5
6
7
8
9
def supprime_toutes_occurences(pile, element):
    p_temp = Pile()
    while not pile.est_vide():
        val = pile.depiler()
        if val != element:
            p_temp.empiler(val)
    while not p_temp.est_vide():
        val = p_temp.depiler()
        pile.empiler(val)

Exercice 4

Exercice 5 du sujet Amérique du Nord J1 - 2021

Correction Q1.a.

Le contenu de la pile P sera

| 'rouge' |
| 'vert'  |
| 'jaune' |
| 'rouge' |
| 'jaune' |
 _________
Correction Q1.b.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def taille_file(F):
    """File -> Int"""
    F_temp = creer_file_vide()
    n = 0
    while not est_vide(F):
        enfiler(F_temp, defiler(F))
        n += 1
    while not est_vide(F_temp):
        enfiler(F, defiler(F_temp))
    return n
Correction Q2.
1
2
3
4
5
6
7
8
9
def former_pile(F):
    """File -> Int"""
    P_temp = creer_pile_vide()
    P = creer_pile_vide()
    while not est_vide(F):
        empiler(P_temp, defiler(F))
    while not est_vide(P_temp):
        empiler(P, depiler(P_temp))
    return P
Correction Q3.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def nb_elements(F, elt):
    """File -> Int"""
    F_temp = creer_file_vide()
    n = 0
    while not est_vide(F):
        val = defiler(F)
        if val == elt:
            n += 1
        enfiler(F_temp, val)
    while not est_vide(F_temp):
        enfiler(F, defiler(F_temp))
    return n
Correction Q4.
1
2
3
4
5
def verifier_contenu(F, nb_rouge, nb_vert, nb_jaune):
    """File, Int, Int, Int -> Bool"""
    return nb_elements(F, 'rouge') <= nb_rouge and 
           nb_elements(F, 'vert') <= nb_vert and 
           nb_elements(F, 'jaune') <= nb_jaune

Exercice 5

Exercice 2 du sujet Centres Étrangers J1 - 2022

Correction Q1.

Il faut écrire l'instruction :

panier_1.enfiler((31002, 'café noir', 1.50, 50525))
Correction Q2.
1
2
3
4
def remplir(self, panier_temp):
    while not panier_temp.est_vide():
        article = panier_temp.defiler()
        self.enfiler(article)
Correction Q3.
1
2
3
4
5
6
7
8
9
def prix_total(self):
    total = 0
    panier_temp = Panier()
    while not self.est_vide():
        article = self.defiler()
        total += article[2]
        panier_temp.enfiler(article)
    self.remplir(panier_temp)
    return total          
Correction Q4.
1
2
3
4
5
6
7
def duree_passage_en_caisse(self):
    if self.est_vide():
        return None
    horaire_premier = self.defiler()[3]
    while not self.est_vide():
        horaire_dernier = self.defiler()[3]
    return horaire_dernier - horaire_premier                 

Exercice 6

Exercice 3 du sujet Centres Etrangers J1 - 2023

Jeu du Simon

Correction Q1.
1
2
3
4
5
def ajout(f):
    couleurs = ('bleu', 'rouge', 'jaune', 'vert')
    indice = randint(0, 3)
    enfiler(f, couleurs[indice])
    return f
Correction Q2.
def vider(f):
    while not est_vide(f):
        defiler(f)
Correction Q3.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def affich_seq(sequence):
    stock = creer_file_vide()
    ajout(sequence)
    while not est_vide(sequence):
        c = defiler(sequence)
        affichage(c)
        time.sleep(0.5)
        enfiler(stock, c)
    while not est_vide(stock):
        enfiler(sequence, defiler(stock))        
Correction Q4.a.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def tour_de_jeu(sequence):
    affich_seq(sequence)
    stock = creer_file_vide()
    while not est_vide(sequence):
        c_joueur = saisie_joueur()
        c_seq = defiler(sequence)
        if c_joueur == c_seq:
            enfiler(stock, c_seq)
        else:
            vider(sequence)
    while not est_vide(stock):
        enfiler(sequence, defiler(stock))
Correction Q4.b.

Question bizarre...

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def tour_de_jeu_modifie(sequence):
    while True:
        affich_seq(sequence)
        stock = creer_file_vide()
        while not est_vide(sequence):
            c_joueur = saisie_joueur()
            c_seq = defiler(sequence)
            if c_joueur == c_seq:
                enfiler(stock, c_seq)
            else:
                vider(sequence)
                vider(stock)
        while not est_vide(stock):
            enfiler(sequence, defiler(stock))
Le jeu ne s'arrête jamais ¯\_(ツ)_/¯

ou bien, en version récursive qui ne s'arrête jamais non plus :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def tour_de_jeu_modifie(sequence):
    affich_seq(sequence)
    stock = creer_file_vide()
    while not est_vide(sequence):
        c_joueur = saisie_joueur()
        c_seq = defiler(sequence)
        if c_joueur == c_seq:
            enfiler(stock, c_seq)
        else:
            vider(sequence)
            print('Perdu ! On rejoue !')
            tour_de_jeu_modifie(sequence)
    while not est_vide(stock):
        enfiler(sequence, defiler(stock))
    tour_de_jeu_modifie(sequence)
Exercice 7 (💀 difficile 💀)

Cet exercice est basé sur l'énigme n°5 d'Advent Of Code 2018.

Le but est de réduire le plus possible une chaîne de caractères (comme dabAcCaCBAcCcaDA ) en obéissant à la règle suivante :

Règle de simplification

Dès que deux lettres identiques mais de casse différente (majuscule-minuscule ou minuscule-majuscule) sont côte à côte dans la chaîne, on les supprime de la chaîne.

Exemple :

dabAcCaCBAcCcaDA  On enlève le premier 'cC'.
dabAaCBAcCcaDA    Cela donne naissance à un 'Aa', qu'on enlève.
dabCBAcCcaDA      On enlève alors 'cC' (ou 'Cc', cela revient au même).
dabCBAcaDA        Plus aucune simplification n'est possible.

La chaîne de caractères qu'il va falloir simplifier contient ... 50000 caractères.

1. Élaboration d'une fonction utile⚓︎

On rappelle que la fonction ord renvoie le code ASCII d'une lettre. En comparant les codes ASCII de deux lettres identiques mais de casse différentes, en déduire une fonction simplifiable qui prend en paramètres deux lettres l1 et l2 et qui renvoie un booléen indiquant si ces deux lettres sont simplifiables.

Exemples d'utilisation :

>>> simplifiable('c', 'C')
True
>>> simplifiable('C', 'c')
True
>>> simplifiable('C', 'C')
False

Correction
1
2
def simplifiable(l1, l2):
    return abs(ord(l1) - ord(l2)) == 32

2. Une seule simplification de la chaîne de caractères⚓︎

Écrire une fonction simplifie qui prend en paramètre une chaîne de caractère s et qui renvoie cette même chaîne de caractères, ayant été simplifiée une fois au maximum.

Principe : on parcourt la chaîne et dès qu'on trouve une simplification à faire, on simplifie la chaîne et on la renvoie immédiatement.

Exemples d'utilisation :

>>> simplifie('dabAcCaCBAcCcaDA')
'dabAaCBAcCcaDA'
>>> simplifie('dabAaCBAcCcaDA')
'dabCBAcCcaDA'
>>> simplifie('dabCBAcCcaDA')
'dabCBAcaDA'
>>> simplifie('dabCBAcaDA')
'dabCBAcaDA'

Pour information, on rappelle la technique de slicing de chaîne de caractères :

>>> ch = 'abcde'
>>> ch[:2]
'ab'
>>> ch[2:]
'cde'

Correction
1
2
3
4
5
def simplifie(s):
    for i in range(len(s) - 1):
        if simplifiable(s[i+1], s[i]):
            return s[:i] + s[i+2:]
    return s

3. Résolution du problème⚓︎

Après vous être demandé comment savoir facilement qu'une chaîne n'était plus simplifiable, proposer une fonction reduction qui prend en paramètre une chaîne s et qui renvoie cette chaîne s une fois effectuées toutes les simplifications possibles.

Exemple d'utilisation :

>>> reduction('dabAcCaCBAcCcaDA')
'dabCBAcaDA'

Correction
1
2
3
4
5
6
7
8
def reduction(s):
    fini = False
    while not fini:
        s_temp = s
        s = simplifie(s)
        if len(s_temp) == len(s):
            fini = True
    return s

4. Le vrai énoncé d'Advent of Code⚓︎

Dans cette énigme n°5, la réponse à donner est le nombre de caractères de la chaîne une fois simplifiée. Ce qui ne devrait pas nous poser de problème.

Par contre, la chaîne 'dabAcCaCBAcCcaDA' sur laquellle nous avons travaillé n'est qu'un exemple... La vraie chaîne contient 50000 caractères : vous pouvez télécharger le fichier la contenant ici : input.txt

Anecdotique ? Pas vraiment...

Effectuez la réduction de cette chaîne avec votre programme précédent. Que remarquez-vous ?

Correction
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
s = open('input.txt').read()

def simplifiable(l1, l2):
    return abs(ord(l1) - ord(l2)) == 32

def simplifie(s):
    for i in range(len(s) - 1):
        if simplifiable(s[i+1], s[i]):
            return s[:i] + s[i+2:]
    return s

def reduction(s):
    fini = False
    while not fini:
        s_temp = s
        s = simplifie(s)
        if len(s_temp) == len(s):
            fini = True
    return s

print(len(reduction(s)))

Le résultat (9371) est loooong à nous parvenir ! (30 secondes sur ma machine)

5. Sauvé par une pile⚓︎

Cet exercice peut être résolu beaucoup plus efficacement grâce à l'utilisation d'une pile... mais comment ?

Vous pouvez utiliser l'implémentation de pile disponible ici.

Aide à la construction de l'algorithme

Pour chaque lettre de la chaîne :

  • si la pile est vide, on empile cette lettre
  • sinon, on regarde si la lettre est simplifiable avec la lettre du haut de la pile :
    • si oui, on supprime cette lettre du haut de la pile et on passe à la lettre suivante de la chaîne
    • si non, on empile cette lettre sur la pile, et on passe à la suivante.
Correction
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
s = open('input.txt').read()
class Pile:
    def __init__(self):
        self.data = []

    def est_vide(self):
        return len(self.data) == 0       

    def empile(self,x):
        self.data.append(x)

    def depile(self):
        if self.est_vide():
            print('Vous avez essayé de dépiler une pile vide !')
            return None
        else :
            return self.data.pop()

    def taille(self):
        Q = Pile()
        n = 0
        while not self.est_vide():
            Q.empile(self.depile())
            n += 1
        while not Q.est_vide():
            self.empile(Q.depile())
        return n


p = Pile() 

def simplifiable(l1, l2):
    return abs(ord(l1) - ord(l2)) == 32

for lettre in s:
    if p.est_vide():
        p.empile(lettre)
    else:
        sommet = p.depile()
        if not simplifiable(sommet, lettre):
            p.empile(sommet)
            p.empile(lettre)

print(p.taille())

Le résultat est cette fois immédiat : 0.04 secondes sur ma machine, soit environ 1000 fois plus rapide que le code précédent.