Aller au contenu

Olympiades⚓︎

Première NSI, Académie de Toulouse

Avertissement

Dans l'ensemble du sujet, nous nous autorisons quelques changements de nommage par rapport au sujet initial qui tord le coup aux conventions PEP8.

Images vectorielles pour le décor d'un jeu vidéo⚓︎

On dispose des fonctions de dessins élémentaires suivantes :

  • point qui prend deux entiers x et y en paramètres et trace un point aux coordonnées (x, y)
  • segment qui prend quatre entiers x1, y1, x2, y2 en paramètres et trace le segment entre les points de coordonnées (x1, y1) et (x2, y2)
  • cercle qui prend trois entiers en paramètres x, y et r et trace le cercle de centre (x, y) et de rayon r

Manipulation de formes élémentaires⚓︎

Question 1

Réaliser le dessin "N8i" en utilisant les fonctions de dessins élémentaires.

N8i

Réponse
def ligne_brisee(points):
    for i in range(len(points) - 1):
        x1, y1 = points[i]
        x2, y2 = points[i+1]
        segment(x1, y1, x2, y2)

def dessin_1():
    # le N :
    ligne_brisee([(10, 10), (10, 32), (20, 10), (20, 32)])

    # le 8
    cercle(30, 18, 8)
    cercle(30, 26, 8)

    # le i
    segment(40, 10, 40, 42)
    point(40, 44)
Question 2

Écrire le code d’une fonction carre prenant en paramètres x et y deux entiers positifs et c un entier strictement positif et qui trace un carré dont les côtés sont horizontaux ou verticaux, dont le coin inférieur gauche a pour coordonnées (x, y) et dont les côtés sont des segments de longueur c.

Réponse
def carre(x, y, c):
    ligne_brisee([(x, y), (x+c, y), (x+c, y+c), (x, y+c), (x, y)])
Question 3

On souhaite désormais tracer une maison à base carrée dont la forme est donnée ci-dessous. La hauteur de la base de la maison sera toujours égale au double de la hauteur du toit et la pointe du toit à l’aplomb au milieu de la base.

maison

Réponse
def maison(x, y, h):
    c = 2 * h
    carre(x, y, c)
    ligne_brisee([(x, y+c), (x+c, y+c), (x+h, y+c+h), (x, y+c)])
Question 4

On souhaite tracer un quadrillage, comme sur l’image ci-dessous, qui forme une grille telle que chacune de ses cases est un carré. Dans l’exemple ci-dessous, la grille comporte \(8\) lignes et \(10\) colonnes.

quadrillage

Réponse
def quadrillage(x, y, ecart, nb_lignes, nb_colonnes):
    # les lignes verticales
    for i in range(nb_colonnes + 1):
        segment(x + i*ecart, y, x + i*ecart, y + ecart*nb_lignes)

    # les lignes horizontales
    for i in range(nb_lignes + 1):
        segment(x, y + i*ecart, x + ecart*nb_colonnes, y + i*ecart)
Question 5

Écrire le code d’une fonction rectangle_plein qui prend en paramètres x et y deux entiers positifs, larg et haut deux entiers strictement positifs et qui trace un rectangle rempli en noir de largeur larg et de hauteur haut et dont le coin inférieur gauche a pour coordonnées (x,y). Pour simplifier, on supposera que les côtés de ce rectangle sont horizontaux ou verticaux et que pour remplir une forme, il suffit de mettre en noir tous les points à coordonnées entières qui la composent.

Réponse
def rectangle_plein(x, y, larg, haut):
    for x1 in range(x, x+larg):
        for y1 in range(y, y+haut):
            point(x1, y1)
    ligne_brisee([(x, y), (x+larg, y), (x+larg, y+haut), (x, y+haut), (x, y)])

Modélisation d'un décor fixe de jeu vidéo⚓︎

Dans cette partie, il est question d'un décor de jeu, appelé "forêt" :

decor

Chaque élément du décor est modélisé par un tuple de la forme :

element_decor = ("nom_fonction", param1, param1, param3, param4)
Tronc

Dans la "forêt", le tronc du sapin est modélisé par le quintuplet suivant :

tronc = ("carré", 200, 200, 100, None)
Question 6
  1. Indiquer l’instruction permettant de créer le tuple soleil modélisant le soleil présent dans le décor "forêt".
  2. Indiquer de même l’instruction permettant de créer le tuple modélisant le bord gauche du sapin dans le décor "forêt".
Réponses
  1. Pour le soleil :

    soleil = ("cercle", 700, 700, 100, None)
    

  2. Pour le bord gauche du sapin :

    bord_gauche_sapin = ("segment", 100, 300, 250, 800)
    

Question 7
  1. Combien d'éléments graphiques simples sont nécessaires pour modéliser le décor "forêt" ?
  2. Écrire l’instruction permettant de créer la liste de tuples foret modélisant la totalité du décor "forêt".
Réponses
  1. Il semble y avoir \(11\) éléments graphiques simples pour le décor "forêt"
  2. Les voici :
    sapin_bord_gauche = ("segment", 100, 300, 250, 800)
    sapin_bord_droit = ("segment", 400, 300, 250, 800)
    sapin_base = ("segment", 100, 300, 400, 300)
    sapin_tronc = ("carré", 200, 200, 100, None)
    route_bord_gauche = ("segment", 400, 0, 600, 300)
    route_bord_droit = ("segment", 1000, 0, 800, 300)
    soleil = ("cercle", 700, 700, 100, None)
    maison_murs = ("carré", 1000, 200, 300, None)
    maison_toit_pente_gauche =  ("segment", 1000, 500, 1150, 600)
    maison_toit_pente_droite =  ("segment", 1300, 500, 1150, 600)
    maison_toit_base = ("segment", 1000, 500, 1300, 500)
    
    foret = [sapin_bord_gauche, sapin_bord_droit, sapin_base, sapin_tronc,
             route_bord_gauche, route_bord_droit, soleil, maison_murs,
             maison_toit_pente_gauche, maison_toit_pente_droite, maison_toit_base]
    

Une fois un décor modélisé à travers ses différents éléments, il faut dessiner ces éléments. On crée pour cela une fonction dessine_element qui prend en paramètre un quintuplet modélisant un élément graphique simple et qui exécute la fonction de tracé associée.

Question 8

Recopier et compléter la fonction dessine_elementci-dessous.

1
2
3
4
5
def dessine_element(elt):
    if elt[0] == 'segment':
        segment(elt[1], elt[2], elt[3], elt[4])
    elif ...
    # plusieurs lignes à compléter
Réponse
1
2
3
4
5
6
7
8
9
def dessine_element(elt):
    if elt[0] == 'segment':
        segment(elt[1], elt[2], elt[3], elt[4])
    elif elt[0] == 'carré':
        carre(elt[1], elt[2], elt[3])
    elif elt[0] == 'cercle':
        cercle(elt[1], elt[2], elt[3])
    elif elt[0] == 'point':
        point(elt[1], elt[2])
Question 9

Écrire la fonction dessine_decor prenant en paramètre decor_complet une liste de quintuplets représentant le décor à dessiner et dessinant le décor en entier.

Réponse
1
2
3
def dessine_decor(decor_complet):
    for elt in decor_complet:
        dessine_element(elt)

Animation d'un personnage dans le décor⚓︎

Question 10

Sur chacun des exemples précédents, quel est le lien entre les coordonnées du scarabée et le décalage réalisé ?

Réponse

Si on note \((x_s, y_s)\) les coordonnées du scarabée et \((x_e, y_e)\) les coordonnées d'un des points de l'élément à afficher alors les coordonnées réelles à utiliser sont :

\[ \begin{array}{l} x = x_e - x_s\\ y = y_e - y_s \end{array}\]
Question 11

De manière générale, compléter la fonction suivante qui affiche le décor de manière décalée en adéquation avec la position du scarabée dont les coordonnées sont notées x_s et y_s.

1
2
def affiche_ecran(decor_complet, x_s, y_s):
    # à compléter
Réponse
1
2
3
4
5
6
7
8
def affiche_ecran(decor_complet, x_s, y_s):
    for elt in decor_complet:
        if elt[4] is None:
            elt_decale = (elt[0], elt[1] - x_s, elt[2] - y_s, elt[3], None)
        else:
            elt_decale = (elt[0], elt[1] - x_s, elt[2] - y_s, 
                          elt[3] - x_s, elt[4] - y_s)
        dessine_element(elt_decale)
Question 12

On souhaite simuler un déplacement horizontal point par point du scarabée dans le décor "forêt". Pour cela, on décale au fur et à mesure la zone du décor qui est affichée à l’écran. Écrire les instructions nécessaires à l’animation d’un tel déplacement du point (400, 0) au point (600, 0).

Réponse

En supposant foret définie comme à la question 7 :

for x_s in range(400, 601):
    affiche_ecran(foret, x_s, 0)
    pause()
    efface()
affiche_ecran(foret, 600, 0)
Question 13

Écrire une fonction deplacement_vertical qui prend en paramètres decor_complet une liste de quintuplets représentant le décor, x et y deux entiers représentant la position initiale du scarabée et h un entier strictement positif et qui simule le déplacement vertical entre les points de coordonnées (x, y) et (x, y+h). À la fin de l’appel de la fonction le décor devra être visible.

Réponse
def deplacement_vertical(decor_complet, x, y, h):
    for i in range(h):
        affiche_ecran(decor, x, y+i)
        pause()
        efface()
    affiche_ecran(decor, x, y+h)

Gestion des formes hors zone d'affichage⚓︎

Un écran est caractérisé par : - les coordonnées de son coin inférieur gauche, - une largeur - une hauteur

Il sera modélisé par un n-uplet nommé.

Un example d'écran
>>> ecran_1 = {'position': (0, 0), 'largeur': 600, 'hauteur': 450}
Question 14

Écrire une fonction est_dans_ecran_point qui prend en paramètres x et y deux entiers positifs représentant la position d’un point et ecran un dictionnaire représentant un écran comme expliqué précédemment et qui renvoie True si le point de coordonnées (x, y) est dans la zone de l’écran, False sinon.

Réponse
def est_dans_ecran_point(x, y, ecran):
    x_s, y_s = ecran['position']
    l, h = ecran['largeur'], ecran['hauteur']
    return (x_s <= x < x_s + l) and (y_s <= y < y_s + h)

Dans un premier temps, on cherche à écrire une fonction est_dans_ecran_element qui prend en paramètres un quintuplet elt représentant un point, un segment ou un carré et un dictionnaire ecran comme décrit précédemment. Cette fonction doit renvoyer True si l’élément graphique est intégralement dans l’écran, False sinon.

Question 15
  1. En supposant la fonction est_dans_ecran_element créée, quelle est la valeur de la variable verif_1 après l’exécution des instructions suivantes ?

    elt_1 = ('segment', 100, 200, 500, 400)
    ecran_1 = {'position': (0, 0), 'largeur': 600, 'hauteur': 450}
    verif_1 = est_dans_ecran_element(elt_1, ecran_1)
    

  2. En supposant la fonction est_dans_ecran_element créée, quelle est la valeur de la variable verif_1 après l’exécution des instructions suivantes ?

    elt_2 = ('carre', 100, 200, 500, 400)
    ecran_2 = {'position': (100, 250), 'largeur': 600, 'hauteur': 450}
    verif_2 = est_dans_ecran_element(elt_2, ecran_2)
    

Réponses
  1. le segment elt_1 est bien entièrement dans l'écran défini par ecran_1, verif_1 vaut donc True;
  2. certains points du carré elt_2 ne sont pas dans la zone de l'écran ecran_2 (par exemple le coin inférieur gauche), verif_2 vaut donc False.
Question 17

Comment faire en sorte qu’une forme partiellement hors écran soit en partie tracée pour sa partie dans l’écran et non tracée pour sa partie hors écran ? Dans cette question ouverte, il vous est demandé d’expliquer avec clarté et précision votre démarche. Toute tentative de raisonnement cohérent même partiel sera valorisée.

Réponse

Il faudrait probablement intégrer le paramètre écran aux fonctions élémentaires (segment, point, cercle) ainsi le segment dessiné serait une portion seulement, le point pourrait ne pas l'être, de même que le cercle qui ne serait dessiné que sur les parties à l'intérieur de l'écran.

Course à pieds sur un circuit⚓︎

Représentation d'un circuit⚓︎

Un circuit est constitué de segments de droite et de virages à angle droit. Un tel circuit est représenté par une liste de chaines de caractères dont les éléments peuvent être seulement 'A', 'G' ou 'D' et où :

  • 'A' représente une portion de ligne droite de longueur déterminée d,
  • 'G' représente un virage à 90° à gauche et
  • 'D' représente un virage à 90° à droite.

Puis le sujet expose le fait que les combinaisons inutiles (e.g. ['G', 'D']) n'apparaitront jamais.

Orientation à droite

De plus, pour représenter un circuit, on suppose que l’orientation au départ est toujours vers la droite. Ainsi le circuit ci-dessous est représenté par la liste suivante :

['A', 'G', 'A', 'D', 'A', 'G', 'A', 'G', 'A', 'A', 'G', 'A', 'A']

circuit_1

Question 1

Tracer le circuit correspondant à la liste suivante.

['A', 'G', 'A', 'D', 'A', 'D', 'A', 'A', 'D', 'A', 'G', 'A', 'D', 'A', 'D', 'A', 'A']
Réponse

circuit_q1

import turtle

def depart():
    """place un point au départ et masque la tortue"""
    turtle.hideturtle()
    turtle.dot()

def avance(d):
    """avance d'une longueur d puis rajoute une
    petite flèche et un petit espace à la suite du trait
    """
    turtle.fd(d)
    turtle.stamp()
    turtle.up()
    turtle.fd(5)
    turtle.down()

def gauche():
    """pivote la tortue de 90° vers la gauche, sans bouger"""
    turtle.left(90)

def droite():
    """pivote la tortue de 90° vers la droite, sans bouger"""
    turtle.right(90)

def trace(circuit, d=50):
    """trace le circuit modélisé par la liste circuit
    en prenant d comme longueur d'une portion de droite
    """
    depart()
    for instruction in circuit:
        if instruction == 'A':
            avance(d)
        elif instruction == 'G':
            gauche()
        elif instruction == 'D':
            droite()

circuit_q1 = ['A', 'G', 'A', 'D', 'A', 'D', 'A', 'A', 'D', 'A', 'G', 'A', 'D', 'A', 'D', 'A', 'A']
trace(circuit_q1)
turtle.mainloop()
Question 2

À quelle liste correspond le tracé ci-dessous :

circuit_q2

Réponse

La liste correspondante est :

['A', 'A', 'D', 'A', 'D', 'A', 'G', 'A', 'D', 
 'A', 'D', 'A', 'G', 'A', 'D', 'A', 'D', 'A']

Longueur d'un parcours⚓︎

Question 3

Écrire une fonction longueur qui prend en paramètres circuit une liste représentant un circuit et portion la longueur en mètres d’une portion de ligne droite et qui renvoie la longueur totale du circuit en mètres.

Réponse
def longueur(circuit, portion):
    longueur_totale = 0
    for instruction in circuit:
        if instruction == 'A':
            longueur_totale += portion
    return longueur_totale
Question 4

Écrire une fonction nb_tours qui prend en paramètres un circuit, la longueur d'une portion en mètres, la distance_totale de la course en mètres et qui renvoie le nombre de tours entiers à effectuer (un entier qui comptabilise le nombre de tours entiers nécessaires pour réaliser la distance de la course).

Réponse
def nb_tours(circuit, portion, distance_totale):
    longueur_circuit = longueur(circuit, portion)
    return distance_totale // longueur_circuit

Dessiner un circuit⚓︎

Question 5

En utilisant la bibliothèque turtle, écrire une fonction tracer_circuit qui prend en paramètres circuit une liste représentant un circuit, d la longueur en pixels d’une portion de ligne droite et qui dessine le circuit correspondant.

Réponse
def tracer_circuit(circuit, d):
    for instruction in circuit:
        if instruction == 'A':
            turtle.forward(d)
        elif instruction == 'G':
            turtle.left(90)
        elif instruction == 'D':
            turtle.right(90)      
Question 6

En prenant pour échelle 10 pixels = 1 centimètre, dessiner la trace de la tortue lorsqu’on exécute le code suivant.

for k in range(4):
    tracer_tortue(['D', 'A', 'G', 'A', 'G', 'A'], 20)
Réponse

circuit_q6

Virages et demi-tours⚓︎

Lorsqu’on tourne deux fois à gauche, ou deux fois à droite, sans avancer entre les deux virages, on revient sur ses pas. Ainsi, dans une liste représentant un circuit, on appellera demi-tour deux occurrences consécutives de 'G', ou deux occurrences consécutives de 'D'. Par exemple la liste ['G','A','G','G','A','D','D','A','A','D'] présente deux demi-tours, le premier à l’indice \(2\), le second à l’indice \(5\).

Question 7

Écrire une fonction detection_demi_tour qui prend en paramètre un circuit et qui renvoie True si le circuit a un demi-tour et False sinon.

Réponse
def detection_demi_tour(circuit):
    for i in range(len(circuit) - 1):
        pas, suivant = circuit[i], circuit[i+1]
        if (pas == 'G' or pas == 'D') and pas == suivant:
            return True
    return False
Question 8

Écrire une fonction distance_1_demi_tour qui prend en paramètres un circuit, portion la longueur en mètres d’une portion de ligne droite et qui renvoie la distance en mètres entre le début du circuit et le premier demi-tour. S’il n’y a pas de demi-tour, la fonction renvoie \(−1\).

Réponse
def distance_1_demi_tour(circuit, portion):
    distance_avant = 0
    for i in range(len(circuit) - 1):
        pas, suivant = circuit[i], circuit[i+1]
        if pas == 'A':
            distance_avant += portion
        elif pas == suivant:
            return distance_avant
    return -1
Question 9

Écrire une fonction sans_demi_tours qui prend en paramètre un circuit et qui renvoie la liste circuit sans ses demi-tours.

Avertissement

La consigne n'est pas claire du tout ici. Doit-on modifier la liste passée et si oui, pourquoi demander de la renvoyer ? doit-on supprimer le doublon entier ou simplement la \(2^e\) occurrence provoquant le demi-tour ?

Réponse

Si on suppose que les listes de Python ne sont pas vues en classe de \(1^{re}\), et qu'on modélise donc les circuit à l'aide de tableau, la construction d'un nouveau tableau en compréhension semble difficile, mais après tout nous sommes sur une olympiade, concours sélectif.

def sans_demi_tour(circuit):
    return [circuit[i] for i in range(len(circuit)) if circuit[i] == 'A'
            or (0 < i < len(circuit)-1 and circuit[i] != circuit[i-1]
                and circuit[i] != circuit[i+1])
            or (i == 0 and circuit[0] != circuit[1])
            or (i == len(circuit)-1 and circuit[i] != circuit[i-1])]

La solution sans compréhension n'est pas plus simple, notamment avec l'astuce de travailler avec un circuit temporaire fictif qui est le circuit d'origine auquel on a ajouté des extrémités bidons :

def sans_demi_tour(circuit):
    fictif = [''] + circuit + ['']
    circuit_sans = []
    i = 1
    while i < len(fictif):
        pas = fictif[i]
        precedent = fictif[i-1]
        suivant = fictif[i+1]
        if pas == 'A':
            circuit_sans.append(pas)
        elif pas != precedent and pas != suivant:
            circuit_sans.append(pas)
        else:
            i += 1
        i += 1
    return circuit_sans
Question 10

On sait que pour faciliter la course, il est important de minimiser le nombre de virages. Écrire une fonction nb_virages qui prend en paramètre un circuit et qui renvoie le nombre de virages qu’il y a dans ce circuit.

Réponse
def nb_virages(circuit):
    compte = 0
    for i in range(1, len(circuit) - 1):
        if circuit[i] != 'A':
            compte += 1
    return compte
Question 11

Définir une fonction nb_barrieres qui prend en paramètre un circuit et qui calcule le nombre de petites et grandes barrières nécessaires pour sécuriser ce circuit. Cette fonction renverra un couple (p, g)p est le nombre de petites barrières, et g le nombre de grandes barrières.

Pour simplifier, on suppose que le circuit ne termine pas par un virage, et ne revient jamais sur lui-même, de sorte qu’il n’y pas de croisement ni de jonction à prendre en compte.

Réponse
def nb_barrieres(circuit):
    p, g = 0, 0
    for i in range(len(circuit)):
        pas = circuit[i]
        precedent, suivant = 'A', 'A'
        if i > 0:
            precedent = circuit[i-1]
        if i < len(circuit) - 1:
            suivant = circuit[i+1]
        if pas == 'A':
            g += 6  # par défaut une ligne droite c'est 6 grandes barrières
            if precedent != 'A':
                # un virage avant : il faut remplacer 1 grande par 1 petite
                # et ajouter une petite sur l'extérieur du virage
                g -= 1
                p += 2
            if suivant != 'A':
                # idem pour un virage qui suit la ligne droite
                g -= 1
                p += 2
    return p, g

Validité du circuit⚓︎

Dans cette dernière partie, on s'intéresse à la notion de validité d'un circuit. Les tronçons de ligne droite auront une longueur de \(1\).

Définition de la validité

Pour être valide, un circuit doit vérifier deux conditions :

  1. être fermé, c’est-à-dire que le point d’arrivée du circuit est le même que celui de départ (c’est d’ailleurs ce qui justifie qu’on parle de circuit et non de chemin) ;
  2. être simple, c’est-à-dire qu’il ne s’auto-intersecte pas en dehors du point de départ et d’arrivée, autrement dit lors du parcours du circuit, le seul moment où il est permis de revenir sur ses pas est la fin du parcours, et dans ce cas le point sur lequel on revient doit être le point de départ.

On donne ci-après 5 exemples de circuits non valides, les circuits tracés dans les sections 1 à 4 de cet exercice en revanche étaient tous valides.

Circuits non valides

non valides

Définition d'état

Pour tester la validité d’un circuit, il suffit de connaitre la position courante à chaque étape du parcours (disons qu’une étape correspond à une lettre de la liste représentant le circuit). En revanche pour connaitre la position à une étape, il ne suffit pas de connaitre la position à l’étape précédente et la lettre lue, il faut aussi connaitre l’orientation à l’étape précédente.

En effet, la lecture d’un 'A' indique qu’il faut avancer d’une unité de longueur, mais pas dans quelle direction, car celle-ci dépend de l’orientation au point de départ et de tous les virages réalisés depuis...

On appelle donc état la donnée de deux informations :

  • la position, qui dit où on est ; représenté par un couple d'entiers (le point de départ sera toujours en (0, 0))
  • l’orientation, qui donne la direction dans laquelle on s’apprête à aller ; là aussi, on a un couple :
  • (0, 1) pour \(\uparrow\) ;
  • (0, -1) pour \(\downarrow\) ;
  • (1, 0) pour \(\rightarrow\) ;
  • (-1, 0) pour \(\leftarrow\).
Les états courants

On donne ci-après les états successivement atteints lors du parcours du circuit re- présenté par : ['G','A','D','A','D','A','A','G','A','A','G','A','G','A','A','A'].

Dernière lettre lue Position Orientation
- (0, 0) (1, 0)
'G' (0, 0) (0, 1)
'A' (0, 1) (0, 1)
'D' (0, 1) (1, 0)
'A' (1, 1) (1, 0)
'D' (1, 1) (0, -1)
'A' (1, 0) (0, -1)
'A' (1, -1) (0, -1)
'G' (1, -1) (1, 0)
'A' (2, -1) (1, 0)
'A' (3, -1) (1, 0)
'G' (3, -1) (0, 1)
'A' (3, 0) (0, 1)
'G' (3, 0) (-1, 0)
'A' (2, 0) (-1, 0)
'A' (1, 0) (-1, 0)
'A' (0, 0) (-1, 0)
12

Dessiner le circuit considéré dans l’exemple précédent. Ce circuit est-il valide ? Justifier.

Réponses

circuit q12

Le circuit est non simple, il n'est donc pas valide. On le voit aussi par le fait que l'avant dernière position courante après une étape 'A' soit (1, 0), déjà rencontrée.

13

Donner les états successivement atteints lors du parcours du circuit représenté par la liste suivante : ['A','A','D','A','D','A','G'].

Réponse
Dernière lettre lue Position Orientation
- (0, 0) (1, 0)
'A' (1, 0) (1, 0)
'A' (2, 0) (1, 0)
'D' (2, 0) (0, -1)
'A' (2, -1) (0, -1)
'D' (2, -1) (-1, 0)
'A' (1, -1) (-1, 0)
'G' (1, -1) (0, -1)

L’état initial étant fixé, les lettres du circuit peuvent être vues comme des instructions qui modifient l’état courant :

  • 'A' indique qu’il faut avancer d’une unité dans la direction donnée par l’orientation courante, c’est-à-dire modifier la position courante,
  • 'G' (resp. 'D') indique qu’il faut changer de direction, c’est-à-dire modifier l’orientation courante.

On remarque d’ailleurs dans l’exemple ci-dessus qu’à chaque étape, c’est soit la position qui est modifiée, soit l’orientation, jamais les deux simultanément. On va donc créer deux fonctions différentes, celle qui gère les modifications de la position, appelée avance et définie ci-dessous, et une autre qui gère les modifications de l’orientation.

La fonction avance
1
2
3
4
5
6
7
8
def avance (pos, ori):
    """ hypothèse : ori est un vecteur unité
    retourne la position courante après la lecture d'un 'A'
    depuis l'état défini par la position pos et l'orientation ori
    """
    x, y = pos
    dx, dy = ori
    return x + dx, y + dy
Question 14
  • Que renvoie avance((1, 1), (0, 1)) ?
  • Que renvoie avance((2, 1), (-1, 0)) ?
Réponses
  • (1, 2)
  • (1, 1)
Question 15

Écrire une fonction tourne qui prend en paramètres une orientation et une etape qui peut être 'G' ou 'D', et qui renvoie l’orientation après la lecture de cette lettre.

Réponse

Nous appuyons notre fonction sur quelques constantes :

NORD = 0, 1
SUD = 0, -1
EST = 1, 0
OUEST = -1, 0

GAUCHE = {EST: NORD, NORD: OUEST, OUEST: SUD, SUD: EST}
DROITE = {EST: SUD, SUD: OUEST, OUEST: NORD, NORD: EST}

def tourne(orientation, etape):
    """vers est un vecteur unité"""
    if etape == 'G':
        return GAUCHE[orientation]
    elif etape == 'D':
        return DROITE[orientation]
Question 16

Écrire une fonction etat_suivant qui prend en paramètres une position, une orientation et une etape qui peut être 'A', 'G' ou 'D', et qui donne la position et l’orientation après la lecture de la lettre.

Réponse
def etat_suivant(position, orientation, etape):
    if etape == 'A':
        return avance(position, orientation), vers
    else:
        return position, tourne(orientation, etape)
Question 17

Écrire une fonction est_ferme qui prend en paramètre un circuit et qui renvoie True si le circuit est fermé et False sinon.

Réponse
DEPART = 0, 0

def est_ferme(circuit):
    position = DEPART
    orientation = EST
    for etape in circuit:
        position, orientation = etat_suivant(position, orientation, etape)
    return position == DEPART
Question 18

Écrire une fonction est_simple qui prend en paramètre un circuit et qui renvoie True si le circuit est simple et False sinon.

Réponse

On s'appuie sur la remarque déjà formulée : si à la suite d'une étape de type 'A', on tombe sur une position déjà visitée, alors le circuit n'est pas simple. Si ce cas de figure ne se produit jamais alors le circuit est simple.

def est_simple(circuit):
    position = 0, 0
    orientation = EST
    visitees = {}
    for etape in circuit:
        position, orientation = etat_suivant(position, orientation, etape)
        if etape == 'A':
            if position in visitees:
                return False
            else:
                visitees[position] = True
    return True
Question 19

Écrire une fonction est_valide qui prend en paramètre un circuit et qui renvoie True si le circuit est valide et False sinon.

Réponse

Le sujet nous suggère donc d'écrire :

def est_valide(circuit):
    return est_ferme(circuit) and est_simple(circuit)

Mais cela n'est pas très optimal puisque ça oblige à deux parcours du circuit... alors qu'en un parcours on peut répondre. En effet, il suffit de combiner les deux fonctions : on parcourt et si on croise une position rencontrée on sait que le circuit n'est pas simple, et donc pas valide. À la fin du parcours, si on n'est pas sur la position de départ c'est que le circuit n'est pas fermé et donc pas valide, et dans le cas contraire il l'est.

def est_valide(circuit):
    position = DEPART
    orientation = EST
    visitees = {}
    for etape in circuit:
        position, orientation = etat_suivant(position, orientation, etape)
        if etape == 'A':
            if position in visitees:
                return False
            else:
                visitees[position] = True
    return position == DEPART
Question 20

Écrire une fonction dimensions qui prend en paramètre un circuit et qui calcule les dimensions (largeur puis hauteur) nécessaires pour implanter ce circuit dans un espace rectangulaire.

Réponse

Il s'agit de mémoriser, lors du parcours du circuit, les minima et maxima des coordonnées en \(x\) et en \(y\) des positions rencontrées. On utilise la constante INF = float('inf') comme valeur Python de \(+\infty\).

def dimensions(circuit):
    position = DEPART
    orientation = EST
    x_min, x_max, y_min, y_max = INF, 0, INF, 0
    for etape in circuit:
        position, orientation = etat_suivant(position, orientation, etape)
        x, y = position
        if x_min > x:
            x_min = x
        if x_max < x:
            x_max = x
        if y_min > y:
            y_min = y
        if y_max < y:
            y_max = y
    return x_max - x_min, y_max - y_min