Exercices de programmation pour classes préparatoires
On modelise un jeu a deux joueurs (J1 et J2) par un graphe oriente dont les sommets sont les positions du jeu et ou il y a une arete de u vers v si, depuis la position u, le joueur dont c'est le tour peut amener la partie en position v. Chaque sommet est controle par exactement un joueur : c'est lui qui choisit le coup quand la partie est sur ce sommet.
Un sous-ensemble de sommets finals designe les positions d'arrivee. Quand la partie atteint une telle position, J1 gagne.
Une position est dite gagnante pour J1 si J1 peut forcer la victoire en partant de cette position, quels que soient les choix de J2. Formellement : - toute position finale est gagnante pour J1 ; - une position controlee par J1 (non finale) est gagnante pour J1 s'il existe un coup menant a une position gagnante pour J1 ; - une position controlee par J2 (non finale) est gagnante pour J1 si tous les coups de J2 menent a une position gagnante pour J1.
Convention : un joueur qui n'a aucun coup possible (hors positions finales) perd la partie. Autrement dit, si J2 est bloque (transitions[u] == []) sur une position non finale, J1 gagne ; si J1 est bloque, J1 perd.
Ecrire une fonction positions_gagnantes(transitions, finals, controle) qui renvoie l'ensemble (type set) des positions gagnantes pour J1.
transitions : dictionnaire d'adjacence (transitions[u] est la liste des voisins sortants).finals : itereable des positions finales.controle : dictionnaire tel que controle[u] vaut 1 si le sommet u est controle par J1 et 2 s'il est controle par J2.On supposera que toutes les positions mentionnees dans les listes d'adjacence sont egalement des cles de transitions et de controle.
| Appel | Résultat attendu |
|---|---|
| positions_gagnantes({0: [1], 1: [2], 2: []}, [2], {0: 1, 1: 1, 2: 1}) | {0, 1, 2} |
| positions_gagnantes({0: [1, 3], 1: [2], 2: [], 3: []}, [2], {0: 2, 1: 1, 2: 1, 3: 1}) | {1, 2} |
Connectez-vous pour soumettre du code.