Final 2025

Instructions
Sujet : Ressources et prérequis
Questions

Instructions

Plus exactement, voici toutes les consignes officielles qui s’appliquaient à ce midterm :

Vous disposez de une heure et quarante-cinq minutes pour faire cet examen (9h15 – 11h00). Amendement : 30 minutes supplémentaires ont été accordées lors de cet examen ; il a donc duré 2h15.
Vous avez droit à toute documentation papier, mais aucun matériel électronique.
Vous pouvez répondre en français ou en anglais.
L’examen comporte une seule “situation problème”. Lisez-la complètement, ainsi que toutes les questions, avant de commencer à répondre. Certaines questions pourraient avoir une influence sur votre compréhension de la situation problème, ou sur votre design.
Lorsque vous écrivez du code, veuillez à ce que les types soient corrects. Votre code devrait passer mypy en mode strict (même si vous ne pouvez pas le vérifier avec une machine), sauf subtilité que vous n’auriez aucun moyen de connaître.
Marquez l’indentation. L’indentation est importante en Python, mais a tendance à se perdre sur papier. Faites en sorte que vos fins de blocs soient claires.
Si une classe doit comporter un __init__ “standard” (avec des paramètres qui correspondent aux attributs, et où l’init ne fait qu’éventuellement appeler super puis assigner les attributs), vous pouvez simplement écrire “... # init standard” dans votre définition de classe.
Vous pouvez écrire @DC pour @dataclass, et @DCF pour @dataclass(frozen=True). Pour les définitions d’Enum, il n’est pas nécessaire d’écrire les = auto().
N’hésitez pas à “refactoriser” au long de votre examen en expliquant vos changements en français, ou en modifiant des réponses précédentes. Vous pouvez ajouter des méthodes, ajouter des classes, généraliser des fonctions, “déplacer” des choses, etc.
Il n’est pas requis d’écrire d’import, ni de documentation, ni de __str__/__repr__, ni de tests.
La duplication de code (y compris du “copier/coller”) sera pénalisée (d’où le refactoring).
L’usage de la fonction cast, du type Any ou de # type: ignore sera pénalisé (si ça ne vous dit rien, tant mieux).

Sujet : Ressources et prérequis

Nous allons modéliser la gestion des ressources et prérequis du jeu de société Terraforming Mars. Bien qu’il y ait eu une série d’exercices parlant de ce jeu, nous modélisons ici de tout autres aspects ; il n’y a donc pas de lien.

Dans ce jeu, chaque joueur ou joueuse incarne une corporation. Une corporation possède des forêts et des ressources. Il y a 6 types de ressources différentes dans le vrai jeu, mais nous allons nous limiter à 4 : l’argent, les plantes, l’énergie et la chaleur. Pour chaque type de ressource, une corporation possède une certaine quantité, ainsi qu’une production. À chaque tour, pour chaque ressource, la quantité est augmentée en fonction de la production. Par exemple, si une corporation a 6 plantes en quantité, et une production de 3 plantes, au début d’un tour elle passera à 9 en quantité, mais restera à une production de 3. Il n’y a pas de “production” de forêts ; c’est seulement le cas pour les ressources. Toutes ces données (nombre de forêts, quantités et productions de ressources) vont évoluer au cours de la partie. Elles sont toutes des valeurs entières.

Une subtilité concerne l’énergie : au début d’un tour, et avant d’appliquer les productions, toute la quantité d’énergie d’une corporation est transférée en quantité de chaleur. La corporation perd donc toute sa quantité d’énergie, mais gagne autant de quantité de chaleur.

Le jeu possède 3 paramètres globaux : le pourcentage d’oxygène dans l’atmosphère, la température ambiente, et le nombre d’océans. Ces valeurs sont entières et vont également évoluer au cours de la partie.

Les corporations vont jouer des cartes pour améliorer leur économie. Les cartes ont des prérequis (requirements) qui dictent des conditions requises pour pouvoir les jouer. Elles ont aussi une série d’actions qui vont influer sur le jeu : par exemple, modifier les quantités et/ou productions de ressources.

Il y a un très grand nombre de cartes différentes dans ce jeu (plus de 200, rien que dans le jeu de base). On ne veut pas toutes les coder dans le programme, mais plutôt les charger depuis un fichier externe. La structure de ce fichier pourrait par exemple être du YAML, mais ce n’est pas le sujet. Ce qui nous intéresse, c’est comment représenter les prérequis et les actions des cartes. On les représente sous forme de texte dans le fichier. On utilise des " dans cette description pour représenter une chaîne de caractères, imitant la notation Python, mais ces guillements ne font pas partie de ce qu’on écrirait dans le fichier.

Pour les prérequis :

"OK" : toujours vrai (pour les cartes qui n’ont pas de prérequis)
"temperature <= -8" : la température globale doit être maximum -8
"oxygen >= 5" : la taux d’oxygène doit être minimum 5
"oceans >= 3" : le nombre global d’océans doit être minimum 3
"player_forests <= 10" : la corporation qui joue la carte doit avoir maximum 10 forêts
"(prérequis1) AND (prérequis2)" : les deux prérequis doivent être vrais
"(prérequis1) OR (prérequis2)" : au moins un des deux prérequis doit être vrai

La structure est récursive : on peut avoir une condition du nombre d’océans dans un AND, lui-même dans un OR. Les comparaisons ne sont pas récursives ; elles ont toujours une “variable” à gauche et un entier littéral à droite. Les seuls opérateurs possibles sont <= et >=. Les variables peuvent être un des 3 paramètres globaux (temperature, oxygen ou oceans) ou le nombre de forêts de la corporation qui veut jouer la carte (player_forests).

Pour les actions, on a une liste de chaînes de la forme suivante :

"plants amount +3" : augmente la quantité de plantes de 3 (évidemment, la ressource et le nombre peuvent varier)
"money amount -2" : diminue la quantité d’argent de 2
"energy production -1" : diminue la production d’énerge de 1
"heat production +2" : augment la production de chaleur de 2
"build forest" : construit une forêt

De manière générale, on a donc soit "resource amount/production +/-x", soit "build forest".

Certaines cartes ont aussi une action spéciale ; il y a plusieurs dizaines d’actions spéciales dans le jeu. On ne les modélisera pas, mais pensez au fait qu’elles devraient exister dans le futur, lorsque vous concevez votre solution. Autrement dit, les actions possibles ne sont pas bornées.

Lexique anglais, dans l’ordre d’apparition des mots en italique : corporation, forest, resource, money, plants, energy, heat, amount, production, oxygen, temperature, oceans, requirement, action.

Remarque générale 1 : à tout moment, vous pouvez décider de “revenir en arrière” pour ajouter des méthodes ou des attributs à vos classes, si vous le désirez. Pensez à laisser de la place dans vos classes, au cas où. Vous pouvez toujours aussi définir plus de classes, de méhodes et de fonctions que demandé, bien entendu ! Les points par question sont donc un peu flexibles.

Remarque générale 2 : quand on dit qu’une fonction doit accepter un certain type de données $B$, il est permis de l’écrire de sorte qu’elle accepte en fait des valeurs de type $A$ à la place, si $B <: A$.

Remarque générale 3 : quand on vous demande d’écrire une fonction, vous pouvez définir une méthode à la place, et inversement. On ne fait pas la différence.

Remarque générale 3 : vous avez spécifiquement le droit de “copier-coller” du code entre la gestion des AND et des OR, même une classe entière si besoin. Il est même encouragé de ne pas écrire le code gérant les OR. Vous pouvez écrire des “, ou une ligne horizontale, ou tout autre moyen d’indiquer explicitement qu’on fait “la même chose” pour OR que pour AND. Ou ne rien noter du tout.

Fonctions utiles

La méthode str.split sépare une chaîne en sous-chaînes séparées par des espaces. Par exemple, pour s = "hello world", on a s.split() == ["hello", "world"].

Voici aussi un rappel d’un usage des fonctions d’expressions régulières :

import re

date_re = re.compile('([0-9]+)/([0-9]+)/([0-9]+)')

result = date_re.fullmatch('22/5/2025')
if result:
    print(result.group(1)) # '22'
    print(result.group(2)) # '5'
    print(result.group(3)) # '2025'

Il est possible, ou pas, que ces fonctions vous servent dans cet examen.

Questions

1. Définissez (en Python et/ou sous forme de diagramme) des types de données pour représenter une corporation et tout ce qu’elle possède : forêts, quantités de ressources et productions de ressources.

Définissez aussi un type de données pour représenter les 3 paramètres globaux (température, oxygène et océans).

2. Définissez et implémentez une fonction start_turn qui accepte une corporation, et applique les changements de début de tour à ses ressources :

Transférer la quantité d’énergie en quantité de chaleur ;
Appliquer les productions.

3. Définissez un type de données Action pour représenter une action, avec potentiellement des types de données auxiliaires. Vous ne devez pas modéliser les actions spéciales, mais votre conception doit supporter l’ajout d’actions spéciales dans le futur.

Attention : on parle bien de représenter/modéliser les actions. On veut une forme structurée, pas une simple str. Au besoin, relisez la question 5 pour clarifier.

4. Définissez et implémentez une fonction apply_actions qui accepte la corporation dont c’est le tour, et une list[Action]. Elle doit appliquer ces actions.

5. On rappelle qu’on veut lire les actions des cartes depuis un fichier. On vous épargne la lecture du fichier en tant que telle, ainsi qu’en extraire la structure. On suppose qu’on a déjà extrait une list[str] dont les éléments sont la représentation textuelle des actions, telle que définie dans le scénario.

Définissez et implémentez une fonction load_actions qui accepte cette list[str] et renvoie une list[Action] correspondante, dans le modèle que vous avez défini à la question 3. Si une des str ne correspond pas à une description d’action valide, votre fonction doit déclencher une exception de type ValueError ou KeyError.

6. Définissez un type de données Requirement pour représenter un prérequis, avec potentiellement des types de données auxiliaires.

Attention : on parle bien de représenter/modéliser les prérequis. On veut une forme structurée, pas une simple str. Au besoin, relisez la question 9 pour clarifier.

Conseil : relisez les questions 7 et 8 avant de commencer cette question. On peut supposer qu’il y aura, dans le futur, d’autres bizarreries telles que celle décrite à la question 8.

Rappel de la Remarque générale 3 : vous avez spécifiquement le droit de “copier-coller” du code entre la gestion des AND et des OR, même une classe entière si besoin. Il est même encouragé de ne pas écrire le code gérant les OR. Vous pouvez écrire des “, ou une ligne horizontale, ou tout autre moyen d’indiquer explicitement qu’on fait “la même chose” pour OR que pour AND. Ou ne rien noter du tout.

7. Définissez et implémentez une fonction test_requirement qui accepte un Requirement, une corporation dont c’est le tour, et l’état des paramètres globaux. Elle doit renvoyer True si le prérequis est satisfait par la corporation et les paramètres globaux, et False sinon.

8. Une des innombrables cartes du jeu permet de relâcher partiellement les prérequis pour d’autres cartes. Elle permet d’élargir de 2 unités les valeurs possibles pour les paramètres globaux du jeu (température, oxygène et océans). Par exemple, si un prérequis demande normalement “au moins 3 océans”, la présence de cette carte relâche ce prérequis à “au moins 1 océan”. Si un prérequis demande “maximum 2 de température”, elle devient “maximum 4 de température” (remarquez que ça ne va pas dans le même sens en fonction de l’opérateur de comparaison). Si un prérequis demande “minimum 1 forêt” appartenant à la corporation qui joue, il reste inchangé (les forêts ne sont pas un des paramètres globaux). Évidemment, si un prérequis est une combinaison avec AND ou OR, cela s’applique à tous les “sous-prérequis”.

Définissez et implémentez une fonction relax_requirement qui accepte un Requirement $A$ et renvoie un autre Requirement $B$. Le prérequis $B$ doit représenter la version relâchée de $A$, suivant la spécification ci-dessus.

Remarque : la question 9 a été transformée en bonus.

9. On rappelle qu’on veut lire les prérequis des cartes depuis un fichier. De nouveau, on suppose qu’on a déjà extrait une unique str qui est la représentation textuelle d’un prérequis, telle que définie dans le scénario.

La présence des AND et OR rend l’analyse de cette chaîne très compliquée, à cause de sa nature récursive. On va se servir d’une “bibliothèque fictive” pour transformer une représentation textuelle d’un prérequis (str) en un Requirement, tel que vous l’avez défini à la question 6. Évidemment, la bibliothèque ne connaît pas Requirement. Il faut donc lui donner une sorte de “configuration” qui lui permette de créer les bouts de votre représentation. Cette configuration se fera sous forme de fonctions que l’on transmet à la bibliothèque.

Cette bibliothèque fournit donc une seule fonction parse, qui prend les arguments suivants :

une str qui est la représentation textuelle ;
une valeur Requirement qui représente un prérequis “OK” ;
une fonction qui crée un Requirement de comparison de variable, à partir de 3 str : le nom de la variable, le nom de l’opérateur (">=" ou "<="), et la valeur à laquelle la comparer (qui est donc une chaîne représentant un entier, comme "-5") ;
une fonction qui combine deux autres Requirement pour former un Requirement AND ; elle prend donc deux Requirement, et renvoie un Requirement.
une fonction qui combine deux autres Requirement pour former un Requirement OR ; elle prend donc deux Requirement, et renvoie un Requirement.

La définition de parse ressemblerait donc à ceci (où les ? devraient être remplacés par de vrais types) :

def parse(text: str, ok: ?, make_comparison: ?, make_and: ?, make_or: ?) -> ?:
    ... # code within the library; not shown

Exemple : si la chaîne passée en paramètre pour text était "(temperature <= 2) AND (OK)", cette fonction se comporterait comme si elle était écrite comme suit :

def parse(text: str, ok: ?, make_comparison: ?, make_and: ?, make_or: ?) -> ?:
    return make_and(
        make_comparison("temperature", "<=", "2"),
        ok
    )

(a) Définissez et implémentez une fonction parse_requirement qui accepte une str et renvoie un prérequis sous forme de Requirement, en se servant de parse. Vous pouvez supposer qu’aucune erreur ne se produit pour cette question (la représentation texte est valide).

(b) Puis, complétez la déclaration de parse avec les types manquants, sans l’implémenter. Vous devez donc uniquement ajouter les types dans sa signature. Vous ne devez pas écrire son implémentation !

Conseil : commencez par définir parse comme si elle avait le droit de connaître le type Requirement (ça vaut déjà des points !). Ensuite, faites en sorte d’éliminer les références à Requirement dans sa définition. Rappelez-vous que cette fonction est en fait définie dans une bibliothèque, qui ne connaît pas votre Requirement.