Programmer un robot (4)
SĂ©rie d'exercices
Cet exercice fait partie d'une série :
-
« Programmer un robot (0) »,
-
« Programmer un robot (1) »,
-
« Programmer un robot (2) »,
-
« Programmer un robot (3) »,
-
« Programmer un robot (4) ».
Il est fortement conseillé d'avoir traité les exercices précédents avant d'entreprendre celui-ci.
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 gauche ;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.
On autorise aussi 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.
Il est possible d'imbriquer des motifs répétés comme dans ["(", "(", "A", 2, "D", ")", 4, "A", 8, "D", ")", 4].
Malgré la possibilité de répéter des motifs introduite dans cet exercice, certaines suites d'instructions restent longues. Par exemple, la liste suivante permet de dessiner deux rectangles identiques séparés de 15 pas : ["(", "A", 5, "D", "A", 3, "D", ")", 4, "G", "A", 15, "(", "A", 5, "D", "A", 3, "D", ")", 4].
On introduit donc la possibilité de déclarer des motifs et de les utiliser dans les instructions.
La déclaration d'un motif suit la syntaxe ["debut_motif", <nom_motif>, <instructions>, "fin_motif"] :
<nom_motif>est une chaßne de caractÚres quelconque, différente de"A","D","G","(",")","debut_motif"et"fin_motif";<instructions>est une suite d'instructions valides.
L'utilisation d'un motif se fait en appelant simplement son nom.
Ainsi, l'exemple précédent peut s'écrire : ["debut_motif", "rect", "(", "A", 5, "D", "A", 3, "D", ")", 2, "fin_motif", "rect", "G", "A", 15, "rect"]
On précise les points suivants :
-
la déclaration d'un motif peut avoir lieu avant ou aprÚs sa premiÚre utilisation ;
-
les motifs peuvent contenir des instructions ou des suites d'instructions répétées ;
-
les motifs eux-mĂȘmes peuvent ĂȘtre rĂ©pĂ©tĂ©s (par exemple
["rect", 4]) ; -
si un motif est déclaré à plusieurs reprises, la déclaration située le plus loin dans la liste d'instructions prévaut.
La gestion des motifs se fait à l'aide d'un dictionnaire memoire qui associé à un nom de motif la série d'instructions correspondante.
L'interprétation des motifs peut se faire en utilisant une fonction deroule analogue à celle rencontrée dans l'exercice 3 à ceci prÚs qu'elle prend désormais un paramÚtre supplémentaire (la mémoire) et renvoie celle-ci en plus de la série d'instructions et de l'indice de la prochaine instruction à lire. On doit simplement faire en sorte, lorsque l'on rencontre un motif, de ne pas l'ajouter à la suite d'instructions déroulées mais plutÎt à la mémoire. La fonction deroule permet donc de :
-
dérouler les motifs répétés entre parenthÚses,
-
nettoyer la série d'instructions des déclarations de motifs qui sont seulement ajoutés à la mémoire.
Une fois la fonction deroule effectuée, on peut exécuter les instructions « déroulées » à l'aide de la fonction execute_brut qui prend en paramÚtres le robot, la liste d'instructions « déroulée » ainsi que la mémoire.
Lors de l'exécution de ces instructions élémentaires, si l'on rencontre un appel à un motif, il est possible de l'exécuter en faisant execute_brut(robot, memoire[<nom_motif>], memoire).
Ăcrire la fonction execute (et les fonctions deroule et execute_brut si vous le souhaitez) qui prend en paramĂštres un objet de type Robot et une liste d'instructions et fait effectuer chacune de ces instructions par le robot.
On garantit que :
-
toutes les instructions sont valides (
"A","D","G","(",")"ou un entier positif ou nul), -
chaque entier suit une action, un motif valide ou une parenthĂšse fermante,
- la suite d'instructions est correctement parenthésée,
- les déclarations de motifs sont correctement formées,
- les motifs utilisés ont tous été déclarés dans la suite d'instructions,
- les motifs n'appellent pas d'autres motifs1.
Exemple
>>> robot = Robot(4, 4)
>>> instructions = ["debut_motif", "carré", "(", "A", 3, "D", ")", 4, "fin_motif", "carré"]
>>> execute(robot, instructions)
>>> robot.dessine_parcours()
ââââââ
â>***â
â* *â
â* *â
â****â
ââââââ
# Tests (insensible Ă la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
-
l'approche utilisĂ©e ici permettrait des appels imbriquĂ©s mais il faudrait toutefois mettre en place un mĂ©canisme limitant la profondeur d'appels rĂ©cursifs ! ↩
# Tests(insensible Ă la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)