Trois moutons sauteurs
Trois moutons indifférenciés font une partie de « saute-moutons » sur un terrain comportant \(n\) emplacements numérotés par leurs indices allant de 0 à n - 1. Ils sont initialement placés tout à gauche du terrain. Deux moutons ne peuvent pas être sur le même emplacement.
À chaque instant, on représente la « configuration » des moutons par un triplet ordonné (a, b, c) : le mouton le plus à gauche est sur l'emplacement d'indice a, celui du milieu sur l'emplacement d'indice b et le plus à droite sur celui d'indice c. Toutes les configurations vérifient donc a < b < c. La configuration initiale est représentée par le triplet (0, 1, 2).
À chaque tour, un mouton peut :
- se déplacer d'une case à droite ou à gauche sur un emplacement libre ;
- faire un saut sur un emplacement libre. Pour réaliser le saut, un mouton doit tout d'abord choisir n'importe lequel de ses deux camarades. Il saute alors par dessus celui-ci et atterrit sur l'emplacement symétrique de son emplacement actuel par rapport au mouton choisi. Si par exemple, le mouton situé sur l'emplacement d'indice
0saute par dessus celui placé à l'indice2, il atterrit sur l'emplacement d'indice4.
La figure ci-dessous représente les configurations successives de trois moutons sur une ligne de \(10\) emplacements.
Des moutons qui jouent à « saute-moutons »
En appliquant ces règles dans le cas d'une ligne comptant 5 emplacements, à la fin du premier tour les différentes configurations possibles sont :
(0, 1, 3): le mouton en2s'est décalé de2à3;(1, 2, 4): le mouton en0a sauté par-dessus de celui en2et se retrouve désormais en4;(0, 2, 3): le mouton en1a sauté par-dessus de celui en2et se retrouve désormais en3;
On imagine que les moutons jouent de façon à découvrir toutes les différentes configurations. On souhaite obtenir un dictionnaire qui associe à chaque configuration son coût, à savoir le nombre minimum de tours pour l'atteindre à partir de la position initiale.
1. Configurations voisines
La fonction configurations_voisines prend en paramètres un triplet d'entiers config ainsi qu'un entier n. Le triplet config représente la configuration prise par les moutons à un certain instant et l'entier n le nombre d'emplacements sur la ligne.
Cette fonction renvoie la liste des triplets représentant les configurations possibles au tour suivant. Cette liste pourra être renvoyée dans n'importe quel ordre.
On garantit que :
-
nest un entier de3à32; -
config = (a, b, c)est un triplet bien formé, c'est-à-dire avec0 <= a < b < c < n.
Attention, la liste renvoyée ne devra contenir que des triplets bien formés à l'image du triplet config : 0 <= a < b < c < n.
Écrire la fonction configurations_voisines.
Exemples
>>> configurations_voisines((0, 1, 2), 10)
[(0, 1, 3), (1, 2, 4), (0, 2, 3)]
>>> configurations_voisines((7, 8, 9), 10)
[(6, 8, 9), (6, 7, 9), (5, 7, 8)]
>>> configurations_voisines((2, 4, 7), 10)
[(1, 4, 7), (3, 4, 7), (2, 3, 7), (2, 5, 7), (2, 4, 6), (2, 4, 8), (4, 6, 7), (0, 2, 7), (1, 2, 4)]
2. Coût des positions
La fonction couts prend en paramètre un entier n donnant le nombre d'emplacements sur la ligne.
Cette fonction renvoie le dictionnaire associant à chaque configuration que peuvent prendre les moutons, le nombre minimum de tours nécessaires pour l'atteindre à partir de la position initiale.
Une version correcte de la fonction configurations_voisines de la question précédente est déjà chargée en mémoire.
Écrire cette fonction.
Exemples
>>> couts(4)
{(0, 1, 2): 0, (0, 1, 3): 1, (0, 2, 3): 1, (1, 2, 3): 2}
>>> couts(5)
{(0, 1, 2): 0, (0, 1, 3): 1, (1, 2, 4): 1, (0, 2, 3): 1, (0, 1, 4): 2, (1, 2, 3): 2, (0, 2, 4): 2, (1, 3, 4): 2, (2, 3, 4): 2, (0, 3, 4): 2}
Aide
On peut modéliser le problème à l'aide d'un graphe dans lequel les sommets sont les différentes configurations possibles. Deux configurations voisines sont reliées par une arête.
On fournit ci-dessous deux représentations de la situation pour \(n=5\).
Le graphe comportant toutes les arêtes est complexe. On en a représenté ici une version simplifiée comportant tous les sommets mais en supprimant de nombreuses arêtes de façon à ce qu'il n'existe qu'un unique chemin entre la configuration initiale et chaque configuration accessible.1
Afin de construire le graphe précédent, on a pris soin de ne pas repasser par un sommet correspondant à une configuration déjà rencontrée (en pointillés ci-dessous).
Plusieurs configurations accessibles ne sont pas représentées afin d'alléger la figure.
Ces représentations fournissent une approche permettant de résoudre le problème : le dictionnaire souhaité peut être obtenu à l'aide d'un parcours en largeur du graphe des configurations.
On pourra utiliser une file et enfiler, à chaque étape du parcours, le couple (configuration, distance) précisant la configuration à envisager et sa distance à la configuration initiale.
La classe File décrite ci-dessous est à ce titre déjà chargée dans l'éditeur.
La classe File
from collections import deque
class File:
"""Classe définissant une structure de file"""
def __init__(self):
self.valeurs = deque([])
def est_vide(self):
"""Renvoie le booléen True si la file est vide, False sinon"""
return len(self.valeurs) == 0
def enfile(self, x):
"""Place x à la queue de la file"""
self.valeurs.appendleft(x)
def defile(self):
"""Retire et renvoie l'élément placé à la tête de la file.
Provoque une erreur si la file est vide
"""
if self.est_vide():
raise ValueError("La file est vide")
return self.valeurs.pop()
def __repr__(self):
"""Convertit la file en une chaîne de caractères"""
if self.est_vide():
return "∅"
return f"(queue) {' -> '.join(str(x) for x in self.valeurs)} (tête)"
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
-
il s'agit d'un arbre couvrant du graphe. Il en existe d'autres dans lesquels les chemins entre deux configurations peuvent différer. ↩
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)