On cherche dans cet exercice à simuler le déplacement d'une balle de golf roulant sur le green.
Le terrain sera représenté par une liste Python dont chaque élément est une liste de nombres entiers positifs. Les nombres contenus dans les sous-listes sont les hauteurs des différents points du terrain.
On donne un exemple ci-dessous (en bleu foncé les points de faible hauteur, en rouge foncé ceux de grande hauteur).
La liste Python correspondant à ce terrain est donnée ci-dessous :
On peut vérifier dans la grille que le point de la ligne 2 et de la colonne 3 est le plus bas du terrain : terrain[2][3] vaut 4 qui est la valeur minimale. On repère ce point grâce au couple d'entiers (i,j)=(2,3) où i désigne l'indice de la ligne et j celui de la colonne.
Un grand terrain de jeu
La grille peut aussi prendre de grandes dimensions.
On se rend alors compte plus facilement de l'existence de plusieurs « points bas locaux » :
le point le plus bas de l'ensemble du terrain sur la ligne d'indice 50 et la colonne d'indice 3 et sa hauteur vaut terrain[50][3]=16. Il n'est pas nécessairement unique : plusieurs points du terrain peuvent avoir la même hauteur minimale ;
une bille lâchée dans le carré entouré en vert finira néanmoins sa course dans un « minimum local », sur la ligne d'indice 26 et la colonne d'indice 22. On a alors terrain[26][22]=30.
On garantit que toutes les sous-listes ont la même longueur. On précise de plus que les points des quatre bords ont tous des hauteurs strictement supérieures aux points de l'intérieur du terrain.
La balle se trouve initialement sur la ligne i et la colonne j. La hauteur du point correspondant est donc terrain[i][j].
Depuis cette position initiale, la balle va « rouler » vers l'une des cases adjacentes dont la hauteur est strictement inférieure à celle de sa position actuelle.
Elle peut se déplacer dans 8 directions :
le nord-ouest ↖,
le nord ↑,
le nord-est ↗,
l'ouest ←,
l'est →,
le sud-ouest ↙,
le sud ↓,
le sud-est ↘.
Ces déplacements sont déclarés dans la liste Python ci-dessous :
On pourra facilement parcourir ces déplacements et récupérer les déplacements dans les différentes directions à l'aide d'une boucle de la forme fordi,djinDEPLACEMENTS:.
Dans le cas où plusieurs cases adjacentes ont des hauteurs inférieures à la case de la balle, celle-ci ira vers une case dont la hauteur est minimale (ce déplacement entraîne donc une variation maximale). Dans le cas où deux déplacements entraînent la même variation, on convient de conserver le premier rencontré dans la liste des déplacements possibles DEPLACEMENTS.
La bille roule jusqu'à arriver sur un point de hauteur « minimale » : tous les points voisins ont donc une hauteur supérieure ou égale à la sienne. C'est donc un minimum local.
Écrire la fonction rouler :
qui prend en paramètres le terrain (liste de listes) et la position de départ (numéro de ligne i et numéro de colonne j),
et renvoie la position finale de la balle sous forme d'un tuple au format (indicedelaligne,indicedelacolonne).
Il ets possible de déterminer, à chaque étape, la nouvelle position de la balle en recherchant le point
voisin de hauteur minimale. Pour ce faire, on parcourt l'ensemble des déplacements possibles afin de déterminer celui qui mène vers le point voisin le plus bas.
Si aucun point voisin n'est plus bas que le point actuel, la bille est bloquée.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)