Programmer un robot (3)
Rappels sur le fonctionnement du Robot
On considÚre dans cet exercice un robot se déplaçant sur une grille de dimensions finies. Initialement, il se trouve sur la case en haut à gauche de la grille et est dirigé vers la droite.
Ce robot est représenté en Python par un objet de la classe Robot. L'interface de la classe Robot est la suivante :
-
robot = Robot(4, 5): instancie un objet de typeRobotévoluant dans une grille de 4 cases de haut et 5 de large. Cet objet est affecté à la variablerobot; -
robot.avance(): fait avancer le robot d'une case dans la direction actuelle. Un déplacement qui ferait sortir le robot de la grille est ignoré ; robot.droite(): fait tourner le robot d'un quart de tour vers la droite ;robot.gauche(): fait tourner le robot d'un quart de tour vers la gauche ;robot.dessine_parcours(): affiche la grille, les cases déjà parcourues et la position actuelle du robot dans la console.
Un objet de type Robot contient aussi un attribut grille. Il s'agit d'une liste de listes gardant la trace des cases visitées (marquées par "*") ou non (laissées vides " ").
Exemple d'utilisation d'un Robot
>>> robot = Robot(4, 3) # la grille fait 4 case de haut sur 3 de large
>>> robot.grille # le robot est en haut Ă gauche
[['*', ' ', ' '], [' ', ' ', ' '], [' ', ' ', ' '], [' ', ' ', ' ']]
>>> robot.dessine_parcours() # le robot pointe vers la droite
âââââ
â> â
â â
â â
â â
âââââ
>>> robot.avance()
>>> robot.avance()
>>> robot.droite()
>>> robot.avance()
>>> robot.avance()
>>> robot.avance()
>>> robot.dessine_parcours()
âââââ
â***â
â *â
â *â
â vâ
âââââ
>>> robot.gauche()
>>> robot.avance()
>>> robot.dessine_parcours()
âââââ
â***â
â *â
â *â
â >â
âââââ
>>> robot.grille
[['*', '*', '*'], [' ', ' ', '*'], [' ', ' ', '*'], [' ', ' ', '*']]
La classe Robot
MOUVEMENTS = ((0, 1), (1, 0), (0, -1), (-1, 0))
class Robot:
def __init__(self, hauteur, largeur):
self.hauteur = hauteur
self.largeur = largeur
self.grille = [[" " for _ in range(largeur)] for _ in range(hauteur)]
self.i = 0
self.j = 0
self.grille[self.i][self.j] = "*"
self.direction = 0
def avance(self):
"""Fait avancer le robot d'une case (seulement si possible)"""
di, dj = MOUVEMENTS[self.direction]
if 0 <= self.i + di < self.hauteur and 0 <= self.j + dj < self.largeur:
self.i += di
self.j += dj
self.grille[self.i][self.j] = "*"
def droite(self):
"""Fait tourner le robot d'un quart de tour vers la droite"""
self.direction = (self.direction + 1) % 4
def gauche(self):
"""Fait tourner le robot d'un quart de tour vers la gauche"""
self.direction = (self.direction - 1) % 4
def dessine_parcours(self):
"""Affiche les cases parcourues et la position actuelle du robot"""
affichage = [
["" for _ in range(self.largeur + 2)] for _ in range(self.hauteur + 2)
]
for j in range(1, self.largeur + 1):
affichage[0][j] = "â"
affichage[-1][j] = "â"
for i in range(1, self.hauteur + 1):
affichage[i][0] = "â"
affichage[i][-1] = "â"
affichage[0][0] = "â"
affichage[-1][0] = "â"
affichage[0][-1] = "â"
affichage[-1][-1] = "â"
for i in range(self.hauteur):
for j in range(self.largeur):
affichage[1 + i][1 + j] = self.grille[i][j]
affichage[self.i + 1][self.j + 1] = [">", "v", "<", "^"][self.direction]
print("\n".join("".join(ligne) for ligne in affichage))
La classe Robot est déjà chargée dans l'éditeur, vous pouvez l'utiliser sans l'importer.
On programme ce robot en lui faisant effectuer différentes actions :
- le code
"A"fait avancer le robot ; - le code
"D"le fait tourner vers la droite ; - le code
"G"le fait tourner vers la gauche.
Il est aussi possible d'utiliser des instructions du type [action, n] dans lesquelles :
actionest une des trois actions décrites ci-dessus ;nest un nombre entier positif ou nul.
Lors d'une répétition, on exécute un maximum d'actions valides. Si par exemple, le robot ne peut avancer que de 5 cases, les instructions ["A", 8] le feront avancer de 5 cases, seules les trois derniÚres actions seront ignorées.
Fonction decoupe
On fournit une fonction decoupe rudimentaire permettant de transformer une chaĂźne de caractĂšres formant une suite d'instructions en une liste.
def decoupe(instructions):
return [int(c) if c.isnumeric() else c for c in instructions]
decoupe("A3GD5") # renvoie ['A', 3, 'G', 'D', 5]
Cette fonction est déjà importée dans l'éditeur. Vous pouvez l'utiliser pour écrire des tests personnels.
Cette fonction ne gÚre que les entiers positifs strictement inférieurs à 10 et ne filtre pas les instructions incorrectes. Ainsi decoupe("Z12") renvoie ['Z', 1, 2].
Le premier exercice de la série a pour objectif d'écrire une version valide de cette fonction.
Les instructions permettant de dessiner un carré de 4 cases de cÎtés sont ["A", 3, "D", "A", 3, "D", "A", 3, "D", "A", 3]. Cette série d'instructions comporte un motif ["A", 3, "D"] répété plusieurs fois.
On autorise désormais les répétitions de motifs en écrivant des instructions au format ["(", <instructions>, ")", n] dans lesquelles :
<instructions>est une suite d'instructions valides ;nest un nombre entier positif ou nul.
En utilisant ce format, les instructions construisant le carré deviennent : ["(", "A", 3, "D", ")", 4].
Il est possible d'imbriquer des motifs répétés comme dans ["(", "(", "A", 2, "D", ")", 4, "A", 8, "D", ")", 4] qui permet d'obtenir :
ââââââââââ
â********â
â* * * *â
â*** ***â
â* *â
â* *â
â*** ***â
â* * * *â
â********â
ââââââââââ
Si certaines actions d'un motif répété font sortir le robot de la grille elles sont ignorées. Les autres instructions sont par contre exécutées.
Il existe plusieurs façon d'interpréter une série d'instructions de ce type. On souhaite dans cet exercice écrire une fonction deroule permettant de dérouler les motifs répétés avant l'exécution proprement dite.
Cette fonction transformera donc ["A", "(", "G", "D", ")", 2, "A"] en ["A", "G", "D", "G", "D", "A"].
Il s'agit d'une fonction récursive qui prend deux paramÚtres :
- la suite d'instructions Ă convertir,
- l'indice de la premiÚre instruction à considérer.
Elle renvoie un tuple formé :
- de la liste des instructions déroulées
- et de l'indice de la prochaine instruction Ă lire.
Lors de la lecture des instructions, la fonction peut rencontrer :
- une instruction simple (
"A","D","G"ou un entier positif ou nul) : la fonction l'ajoute à son résultat ; - une parenthÚse fermante ou la fin de la liste d'instructions : la fonction renvoie son résultat et l'indice immédiatement suivant ;
- une parenthĂšse ouvrante : dans ce cas, la fonction s'appelle elle-mĂȘme Ă partir de l'indice suivant. Cet appel renvoie la suite des instructions entre parenthĂšses et l'indice de l'entier suivant la parenthĂšse fermante. Il ne reste alors qu'Ă ajouter les instructions rĂ©cupĂ©rĂ©es autant de fois que nĂ©cessaire au rĂ©sultat.
Ăcrire la fonction deroule prĂ©sentĂ©e ci-dessus.
On garantit que :
- toutes les instructions sont valides (
"A","D","G","(",")"ou un entier positif ou nul), - chaque entier suit une action valide ou une parenthĂšse fermante,
- toute parenthĂšse fermante est suivie d'un entier,
- la suite d'instructions est correctement parenthésée.
Exemples
>>> instructions = ["A", "(", "G", "D", ")", 2, "A"]
>>> resultat, i_final = deroule(instructions, 0)
>>> resultat
['A', 'G', 'D', 'G', 'D', 'A']
>>> i_final
7
>>> resultat, i_final = deroule(instructions, 2)
>>> resultat
['G', 'D']
>>> i_final
5
# Tests (insensible Ă la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
# Tests(insensible Ă la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)