Examen de BPI - session normale - 18 décembre 2024

Durée : 2 heures.

Aucun document autorisé à l'exception d'une feuille manuscrite format A4 recto verso.

Consignes générales

L'épreuve doit être réalisée exclusivement sur la machine et dans l'environnement mis à disposition.

Toute tentative de communication ou de fraude, oral ou via des dispositifs portables (clé USB, disques durs externes, etc.), entraînera un renvoi devant la Section Disciplinaire de Grenoble-INP.

À la fin de l'épreuve, vous devez rendre votre code comme cela vous a été expliqué en début d'examen : si vous arrêtez ou redémarrez la machine brutalement, votre code risque d'être perdu !

Il est très fortement recommandé de sauvegarder régulièrement pour ne pas risquer de perdre votre travail en cas de panne de la machine.

En cliquant sur les liens en bleu, vous pouvez accéder à la documentation Python ainsi qu'au site du cours BPI.

La clarté du code produit sera un critère déterminant dans la notation.

Le barème est donné à titre indicatif. L'examen peut être découpé en 4 parties de difficulté croissante :

• un tri sur des tableaux statiques ;
• un tri sur des listes doublement chaînées ;
• des fonctions permettant d'analyser et de traiter un fichier texte dans un format particulier ;
• des fonctions génératrices permettant de générer tous les choix possibles.

On vous recommande donc de traiter les parties séquentiellement. Les deux tris correspondent à la partie « exercices » des TP alors que les deux parties suivantes sont du niveau d'un « miniprojet ».

Le sujet paraît long, car on détaille précisément ce qui est attendu en donnant des exemples, mais les fonctions demandées sont assez courtes.

On n'écrira pas de méthodes dans cette épreuve, uniquement des fonctions.

Il est interdit d'implanter des fonctions récursives dans cette épreuve.

Pour ceux qui le souhaitent, le module traceur.py est fourni à côté des fichiers à compléter pour vous aider à débogguer vos programme.

Exercices : tris (10 pts)

Consignes générales pour les deux exercices

On va implanter dans la partie exercices deux tris classiques :

• le tri du crêpier sur des tableaux statiques d'entiers ;
• le tri du nain la tête en bas sur des listes doublement chaînées d'entiers.

Dans les deux cas, on veut trier les données par ordre croissant.

On fournit trois fichiers :

• tri_tab.py contiendra les fonctions implantant le tri sur des tableaux ;
• tri_liste.py contiendra les fonctions implantant le tri sur des listes chaînées ;
• tri.py contient le programme principal et des tests, vous n'avez pas besoin de le modifier.

Si vous appelez le programme principal simplement sans paramètre (./tri.py), il lancera une série de tests sur des tableaux et listes de petites tailles pour vous aider à repérer visuellement vos erreurs.

Si vous appelez le programme avec la commande ./tri.py --brut, il lancera des tests bruts sur beaucoup de tableaux et de listes de plus grandes tailles.

Attention : le fait que les tests bruts ne détectent aucune erreur ne veut pas forcément dire que votre code est correct. Les tests vérifient simplement que le tableau et la liste résultats contiennent les mêmes éléments dans le même ordre que le tableau original trié en utilisant la fonction sorted de Python.

Consigne importante : dans les deux exercices, vous ne devez utiliser aucune primitive fournie dans la bibliothèque Python, à l'exception de len et range qui sont autorisées.

Exercice 1 : le tri du crêpier (6 pts)

Toutes les fonctions demandées dans cette partie doivent être complétées dans le fichier tri_tab.py.

On travaillera exclusivement sur des tableaux statiques : c'est-à-dire que nous utiliserons uniquement l'opération d'accès indexé sur les list Python que nous manipulerons.

Le tri du crêpier est un algorithme de tri de tableaux inventé par un informaticien affamé muni d'une spatule souhaitant trier une pile de crêpes. Pour des questions d'hygiène alimentaire, la seule opération autorisée pour notre informaticien consiste à renverser un sous ensemble des crêpes de la pile avec la spatule.

Comme dans l'algorithme de tri par sélection du maximum, le tableau est découpé en deux parties :

• la partie déjà triée à droite du tableau, entre les indices sup (inclus) et taille (= nombre d'éléments du tableau complet) exclus : autrement dit, [sup..taille[ est la partie du tableau déjà triée ;
• la partie qui n'est pas encore triée à gauche du tableau, entre les indices 0 (inclus) et sup (exclus) : autrement dit, [0..sup[ est la partie du tableau qui n'est pas encore triée.

À chaque itération, on va chercher la valeur maximale du sous-tableau non trié pour la mettre à sa place, c'est-à-dire à l'indice sup - 1, puis déplacer sup d'une case vers la gauche.

Plus précisément, l'algorithme consiste à effectuer les actions ci-dessous tant que le sous-tableau non trié, correspondant initialement à tout le tableau, contient au moins deux éléments :

• rechercher l'indice de la valeur maximale dans le sous-tableau non trié ;
• si cet indice est égal à sup - 1, la valeur maximale est en fait déjà à sa place et on passe à l'itération suivante ;
• sinon, et uniquement si cet indice est différent de zéro, on renverse (comme une pile de crêpes avec une spatule) la tranche du tableau entre les indices zéro et l'indice de la valeur maximale inclus : après ce premier renversement, la valeur maximale est donc placée dans la case d'indice zéro ;
• on renverse ensuite tout le sous-tableau non trié : la valeur maximale est donc maintenant dans la case d'indice sup - 1 et on peut passer à l'itération suivante.

Renverser une tranche de tableau consiste simplement à inverser tous ses éléments : par exemple, si on renverse le tableau [1 2 3 4], on obtient le tableau [4 3 2 1].

Question 1 (2 pts)

Complétez la fonction renverser(tab, dern) qui renverse la tranche entre les indices 0 et dern inclus du tableau tab.

Par exemple, si tab est [1, 2, 3, 4, 5] et si on appelle renverser(tab, 2) alors tab sera [3, 2, 1, 4, 5] après l'appel.

Question 2 (2 pts)

Complétez la fonction rechercher_ix_max(tab, sup) qui renvoie l'indice de la valeur maximale dans le sous-tableau de tab d'indices [0..sup[ (sup est bien exclu).

Par exemple, si tab est [1, 5, 3, 7, 2], l'appel à rechercher_ix_max(tab, 3) renverra 1.

Question 3 (2 pts)

Compléter la fonction trier_tab(tab) qui trie tab par ordre croissant avec l'algorithme du crêpier. Vous devez bien sûr utiliser les deux fonctions précédentes.

Exercice 2 : le tri du nain de jardin la tête en bas (4 pts)

On va maintenant implanter un tri qu'on a déjà vu en TP, avec une légère variante, sur des listes doublement chaînées d'entiers.

Toutes les fonctions demandées dans cet exercice doivent être complétées dans le fichier tri_liste.py.

On donne dans ce fichier la classe Cellule représentant les cellules de nos listes doublement chaînées.

Une cellule sera composée d'une valeur, d'une référence vers la cellule précédente et d'une référence vers la cellule suivante ;

On fournit un « afficheur » __str__ qui permettra d'afficher le contenu d'une cellule cell en écrivant simplement print(cell).

On donne aussi la classe Liste représentant les listes doublement chaînées : chaque liste sera équipée d'un élément fictif (sentinelle) en tête (contenant le caractère T en tant que valeur) et d'un élément fictif en queue (contenant le caractère Q en tant que valeur).

Vous ne devez jamais accéder ni à liste.tete.val ni à liste.queue.val dans les fonctions qu'on vous demande d'implanter, mais toujours comparer les références de vos cellules avec liste.tete et liste.queue pour savoir si vous êtes au début ou au bout de la liste.

On peut donc représenter une liste doublement chaînée par le schéma suivant :

(où Ø symbolise la « référence » None).

Le constructeur de la classe Liste crée et renvoie une liste « vide », c'est-à-dire sans cellule significative, mais contenant bien les deux sentinelles.

On fournit également une fonction remplir_liste(liste, tab) qui prend en paramètre une liste vide et un tableau contenant des entiers et qui remplit la liste avec les mêmes valeurs dans le même ordre. Par exemple, le schéma ci-dessus représente la liste après avoir appelé remplir_liste(liste, [3, 1, 4, 2, 7]) ;

On donne aussi une fonction afficher_liste(liste) qui affiche le contenu de la liste (y compris les éléments fictifs en tête et en queue) sous le format T <-> 3 <-> 1 <-> 4 <-> 2 <-> 7 <-> Q.

Question 4 (2 pts)

Compléter la fonction echanger_cellules(cell) dont le but est d'échanger la cellule cell avec sa précédente cell.prec.

On considère comme prérequis que cell et cell.prec sont des cellules significatives (c'est-à-dire ni l'élément fictif en tête ni l'élément fictif en queue).

La fonction renvoie une référence vers la cellule qui maintenant remplace cell dans la liste. Pour le dire autrement, la fonction renvoie une référence vers la cellule qui était cell.prec au moment de l'appel à la fonction.

Par exemple, si on appelle echanger_cellules(cell) avec cell pointant sur la cellule contenant la valeur 4 dans la liste exemple ci-dessous :

(où Ø symbolise la « référence » None).

Alors, après l'exécution de la fonction, on a échangé les cellules contenant 1 et 4, et on renvoie une référence vers la cellule contenant 1, comme illustré dans la figure ci-dessous :

(où Ø symbolise la « référence » None).

Question 5 (2 pts)

Compléter la fonction trier_liste(liste) qui doit trier la liste selon l'algorithme du nain de jardin la tête en bas qui veut trier des pots de fleurs par ordre de taille croissante. L'algorithme est le suivant :

1. les pots sont alignés de gauche à droite et le nain se positionne devant le dernier pot ;
2. le nain compare la taille du pot devant lui à celle du pot immédiatement à sa gauche :
3. si les pots sont dans le bon ordre, le nain se déplace d'un pot vers la gauche ;
4. sinon, il échange les deux pots et avance d'un pot vers la droite ssi il n'est pas déjà devant le pot le plus à droite ;
5. le nain continue l'étape 2 tant qu'il n'est pas devant le pot le plus à gauche de la file.

Miniprojet : Au restaurant (10 pts)

Toutes les fonctions demandées dans cette partie doivent être complétées dans le fichier restaurant.py.

L'objectif de ce miniprojet est de réaliser un programme Python capable de :

1. lire la carte d'un restaurant stocké dans un fichier texte dont le nom est passé en paramètre ;
2. générer tous les choix possibles composés de n plats à partir de la carte du restaurant.

Deux fichiers contenant des cartes vous sont fournis : carte1.txt et carte2.txt.

Analyse et traitement d'un fichier texte (6 points)

Question 1 (1 pt)

Implantez la fonction parse_args() qui renvoie le nom du fichier passé en paramètre (contenant la carte à utiliser), ou qui arrête le programme.

Dans le cas où le programme est appelé avec un nombre de paramètres différent de 1, la fonction parse_args doit afficher un message indiquant comment utiliser le programme à l'utilisateur et arrêter le programme à l'aide de la fonction exit du module sys.

Question 2 (3 pts)

Implantez la fonction lire_carte(nom_fichier) qui construit et renvoie une carte à partir d'un fichier dont le nom est passé en paramètre. Une carte est un dictionnaire dont les clefs sont les types de plats (« entrée », « plat », ...) et dont les valeurs sont des tableaux dynamiques contenant tous les choix possibles pour le type de plat associé.

Attention au format d'un fichier « carte » qui est le suivant :

• il peut y avoir des lignes vides n'importe où (elles doivent être ignorée) ;
• il peut y avoir des espaces, des tabulations ou un mélange des deux au début et la fin de chaque ligne (ces caractères doivent aussi être ignorés) ;
• une ligne contenant le caractère : (deux points) est une ligne indiquant à quel type de plat les plats suivant appartiennent ;
• un même type de plat peut apparaitre plusieurs fois dans le fichier ;
• une ligne ne contenant pas le caractère : (deux points) est une ligne indiquant un ou plusieurs plats séparés par le caractère , (virgule). Ces plats appartiennent au dernier type de plat rencontré.

À titre d'exemple, voici le dictionnaire que lire_carte doit renvoyer pour le fichier carte1.txt :

{'Entrées': ['Salade verte', 'Salade de tomates'], 
 'Plats': ['Poivrons grillés', 'Poulet au citron'], 
 'Desserts': ['Poires au sirop']}

Question 3 (1 pt)

Implantez la fonction afficher_carte(carte) qui affiche la carte passée en paramètre telle que retournée par la fonction lire_carte. Toujours en utilisant la carte contenue dans le fichier carte1.txt, le format attendu, que vous devez scrupuleusement respecter, est le suivant :

Entrées
 1 Salade verte
 2 Salade de tomates
Plats
 1 Poivrons grillés
 2 Poulet au citron
Desserts
 1 Poires au sirop

En particulier, on notera :

• qu'il n'y a aucune ligne vide affichée ;
• que les lignes « type de plat » ne contiennent aucun espace ni au début ni à la fin ;
• que les lignes « plat » contiennent exactement 1 espace au début et aucun espace à la fin ;
• que les plats sont numérotés dans un type de plat donné.

Question 4 (1 pt)

Implantez la fonction choisir_menu_aleatoirement(carte) qui, comme son nom l'indique, choisit un menu aléatoirement dans une carte donnée. Un menu est composé d'exactement un plat pour chaque type de plat présent dans la carte.

Génération de tous les choix possibles (4 pts)

Question 5 (2 pts)

Implantez la fonction génératrice generer_tous_les_plats(carte) qui renvoie un itérateur permettant de parcourir tous les plats présents dans une carte indépendamment de leur type.

Question 6 (2 pts)

Implantez la fonction génératrice generer_toutes_les_possibilites(carte, nb_plats) qui renvoya un itérateur permettant de parcourir tous les choix de taille nb_plats possibles. Un choix est un tuple de taille nb_plats.

Vous devez utiliser le module itertools dont la documentation est accessible à cette adresse : https://docs.python.org/3/library/itertools.html#module-itertools.