Jeu de la poussette

D'après 2022, Métropole, J2, Ex. 2

La poussette est un jeu de cartes en solitaire. Cet exercice propose une version simplifiée de ce jeu basée sur des nombres.

On considère une pile constituée de nombres entiers tirés aléatoirement. Le jeu consiste à réduire la pile suivant la règle suivante : quand la pile contient du haut vers le bas un triplet dont les termes du haut et du bas sont de même parité, on supprime l'élément central.

Par exemple :

• Si la pile contient du haut vers le bas le triplet 1 ; 0 ; 3, on supprime le 0, car 1 et 3 sont tous les deux impairs.
• Si la pile contient du haut vers le bas le triplet 1 ; 0 ; 8, la pile reste inchangée, car 1 et 8 n'ont pas la même parité.

On parcourt la pile ainsi de haut en bas et on procède aux réductions.

Arrivé en bas de la pile, on recommence la réduction en repartant du sommet de la pile jusqu'à ce que la pile ne soit plus réductible.

Une partie est « gagnante » lorsque la pile finale est réduite à deux éléments exactement.

Voici un exemple détaillé de déroulement d'une partie.

Premier parcours de la pileDeuxième parcoursTroisième parcoursQuatrième parcours

• La première comparaison (7, 5 et 4) laisse la pile inchangée.
• On retire le 4 lors de la deuxième itération.
• On retire le 8 lors de la troisième.
• Il ne reste plus que deux valeurs en bas de la pile (9 et 6) : on a fini le premier parcours.

• On recommence à partir du haut de la pile : on retire le 5.
• Le triplet suivant (3, 9 et 6) n'entraine pas de suppression.
• Il ne reste plus que deux valeurs à étudier (9 et 6) : on a terminé le deuxième parcours.

• On recommence en haut de la pile avec 7, 3 et 9 : on retire le 3.
• Il ne reste que le 9 et le 6 : on a terminé le troisième parcours.

• On recommence en haut de la pile avec 7, 9 et 6. La pile est inchangée.
• La pile n'a pas été modifiée lors de ce parcours : la partie est terminée et cette pile n'est pas gagnante.

1.a. Donner les différentes étapes de réduction de la pile suivante :

Réponse

Il s'agit d'une pile gagnante :

Premier parcoursSecond parcoursTroisième parcours

• Lors de la première comparaison, on retire le 9.
• Lors de la seconde comparaison, on retire le 7.
• Il ne reste plus que deux valeurs en bas de la pile (4 et 2) : on a fini le premier parcours.

• Lors de la première comparaison, on retire le 8.
• Il ne reste plus que deux valeurs en bas de la pile (4 et 2) : on a fini le second parcours.

• Lors de la première comparaison, on retire le 4.
• Il ne reste plus que deux valeurs en bas de la pile (4 et 2) : la pile est gagnante.

1.b. Parmi les piles proposées ci-dessous, donner celle qui est gagnante.

Pile APile BPile C

Réponse

Seule la pile B est gagnante. On fournit ci dessous les piles en début et fin de partie :

Pile APile BPile C

L'interface d'une pile est proposée ci-dessous :

• pile_vide() renvoie une pile vide,
• est_vide(p) renvoie True si p est vide, False sinon,
• empile(p, element) ajoute element au sommet de p,
• depile(p) retire l'élément au sommet de p et le renvoie,
• sommet(p) renvoie l'élément au sommet de p sans le retirer de p,
• taille(p): renvoie le nombre d'éléments de p.

Dans la suite de l'exercice on utilisera uniquement ces fonctions.

2. La fonction reduit_triplet_au_sommet permet de supprimer l'élément central des trois premiers éléments en partant du haut de la pile, si l'élément du bas et du haut sont de même parité. Les éléments dépilés et non supprimés sont replacés dans le bon ordre dans la pile.

Recopier et compléter sur la copie le code de la fonction reduit_triplet_au_sommet prenant une pile p en paramètre et la modifiant en place. Cette fonction renvoie le booléen est_reduit indiquant si le triplet du sommet a été réduit ou non.

def reduit_triplet_au_sommet(p):
    haut = depile(p)
    milieu = depile(p)
    bas = sommet(p)
    est_reduit = ...
    if haut % 2 != ...:
        empile(p, ...)
        ...
    empile(p, ...)
    return ...

Réponse

def reduit_triplet_au_sommet(p):
    haut = depile(p)
    milieu = depile(p)
    bas = sommet(p)
    est_reduit = True
    if haut % 2 != bas % 2:
        empile(p, milieu)
        est_reduit = False
    empile(p, haut)
    return est_reduit

3. On se propose maintenant d'écrire une fonction parcourt_pile_en_reduisant qui parcourt la pile du haut vers le bas en procédant aux réductions pour chaque triplet rencontré quand cela est possible.

La pile est toujours modifiée en place.

La fonction parcourt_pile_en_reduisant renvoie un booléen indiquant si la pile a été réduite à au moins une reprise lors du parcours.

3.a. Donner la taille minimale que doit avoir une pile pour être réductible.

Résultat

Si une pile a une taille de 2 ou moins, elle n'est pas réductible.

Si une pile est réductible, alors sa taille est supérieure ou égale à 3.

3.b. Recopier et compléter sur la copie :

def parcourt_pile_en_reduisant(p):
    q = pile_vide()
    reduction_pendant_parcours = False
    while taille(p) >= 3:
        if ...:
            reduction_pendant_parcours = ...
        e = depile(p)
        empile(q, e)
    while not est_vide(q):
        ...
        ...
    return ...

Résultat

def parcourt_pile_en_reduisant(p):
    q = pile_vide()
    reduction_pendant_parcours = False
    while taille(p) >= 3:
        if reduit_triplet_au_sommet(p):
            reduction_pendant_parcours = True
        e = depile(p)
        empile(q, e)
    while not est_vide(q):
        e = depile(q)
        empile(p, e)
    return reduction_pendant_parcours

4. Partant d'une pile d'entiers p, on propose ici d'implémenter une fonction récursive joue jouant une partie complète sur la pile p.

On effectue donc autant de parcours que nécessaire.

Une fois la pile parcourue de haut en bas, on effectue un nouveau parcours à condition que le parcours précédent ait modifié la pile. Si à l'inverse, la pile n'a pas été modifiée, on ne fait rien, car la partie est terminée.

def joue(p):
    if parcourt_pile_en_reduisant(...):
        ...(...)

Résultat

def joue(p):
    if parcourt_pile_en_reduisant(p):
        joue(p)