Aller au contenu

E03 - Carte au trésor⚓︎

Le problème

Carte au trésor

Proposition 1⚓︎

🐍 Script Python
def deplac(nb_deplacement, deplacement, jardin_long, scoreS, scoreE, score_final) -> str :

    """
    Cette fonction va renvoyer le chemin à prendre tout en ne sortant pas du jardin

    >>> deplac(8, "OEESSNOS", [4,  4], 0, 0, "")
    2 1 


    """

    for d in deplacement:

        if d == "O" :
            if scoreE - 1 >= 0 :
                scoreE -= 1 

        elif d == "N" :
            if scoreS - 1 >= 0 : 
                scoreS -= 1

        elif d == "S":
            if scoreS + 1 < jardin_long[0]:
                scoreS += 1 

        elif d == "E":
            if scoreE + 1 < jardin_long[1]:
                scoreE += 1

    score_final = str(scoreS) + " " +  str(scoreE)

    return score_final


nb_deplacement = int(input())
deplacement = input()
jardin_long = list(map(int, input().split()))
scoreS = 0
scoreE = 0
score_final = ""



print(deplac(nb_deplacement, deplacement, jardin_long, scoreS, scoreE, score_final))
  • Bon doctest, mais il faudrait le lancer...

  • La sortie de la fonction pourrait être un tuple, plutôt que str.

  • Ici les variables globales sont à éviter, et de meilleurs noms sont à choisir.

  • Mieux choisir les paramètres des fonctions.

Proposition 2⚓︎

🐍 Script Python
"""
Auteur : ****** 
https://prologin.org/train/2004/semifinal/carte_au_tresor
"""

def carte_au_trèsor(nb_déplacements, déplacements, taille_x, taille_y):
    """Renvoie la chemin le plus court a parcourir pour arriver au 
    trèsor cacher dans le jardin

    >>>carte_au_trèsor(8, OEESSNOS, 4, 4)

    2 1

    """
    déplacements_x = 0
    déplacements_y = 0
    for i in range(nb_déplacements):
        if déplacements[i] == 'O':
            déplacements_x -= 1
            if déplacements_x < 0:
                déplacements_x += 1
        elif déplacements[i] == 'E':
            déplacements_x += 1
            if déplacements_x >= taille_x:
                déplacements_x -= 1
        if déplacements[i] == 'N':
            déplacements_y -= 1
            if déplacements_y < 0:
                déplacements_y += 1
        elif déplacements[i] == 'S':
            déplacements_y += 1
            if déplacements_y >= taille_x:
                déplacements_y -= 1
    print(déplacements_y, déplacements_x, sep=' ')



import doctest
doctest.testmod

#Entrée
nb_déplacements = int(input())
déplacements = input()

#Sortie
taille_jardin_x, taille_jardin_y = map(int, input().split())
carte_au_trèsor(nb_déplacements, déplacements,taille_jardin_x, taille_jardin_y)
  • Erreurs de doctest !!!

  • (i, j) semblent de meilleurs identifiants que (x, y) pour une grille...

  • Idée originale que d'annuler le déplacement en cas de sortie de grille... Mais il vaut souvent mieux tester avant pour éviter d'annuler une action, cela peut être parfois délicat.

Proposition 3⚓︎

🐍 Script Python
def recherche_trésor(nb_d,dep,taille):
    o=0
    n=0
    se=[]
    d=dep.upper()
    for i in range(nb_d):
        if d[i]=="O":
            if o>0:
                o=o-1
        if d[i]=="E":
            if o<taille[1]-1:
                o=o+1
        if d[i]=="N":
            if n>0:
                n=n-1
        if d[i]=="S":
            if n<taille[0]-1:
                n=n+1               
    se.append(n)
    se.append(o)
    return se

nb_déplacement = int(input())
déplacement =input()
taille_jardin=list(map(int,input().strip().split()))[:2]
z=recherche_trésor(nb_déplacement,déplacement,taille_jardin)
print(z[0],z[1])

import doctest
doctest.testmod()
  • PEP8 à bien mieux respecter... URGENT !

  • Inutile de créer une liste avec append pour envoyer deux valeurs.

  • On attend un doctest à la fonction. Il faut le placer avant l'utilisation...

Proposition 4⚓︎

🐍 Script Python
def carte_au_tresors(nb_caractère, chaine, taille_S, taille_E):
    """renvoie le nombre de pas à faire vers l'Est, et le nombre de pas à faire
    vers le Sud, pour trouver le trésor.
    les valeur faisant sortir des limit du jardin ne seron pas prise en compte

    >>> carte_au_tresors(8, 'OEESSNOS', 4, 4)
    '2 1'

    """
    nb_pas_Sud = 0
    nb_pas_Est = 0
    for i in range(nb_caractère):
        if chaine[i] == 'S':
            if nb_pas_Sud < taille_S -1:
                nb_pas_Sud += 1

        elif chaine[i] == 'E':
            if nb_pas_Est < taille_E -1:
                nb_pas_Est += 1

        elif chaine[i] == 'N':
            if nb_pas_Sud > 0:
                nb_pas_Sud -= 1

        elif chaine[i] == 'O':
            if nb_pas_Est > 0:
                nb_pas_Est -= 1

    return str(nb_pas_Sud) + " " + str(nb_pas_Est)

# test

import doctest
doctest.testmod()

# entré

nb_caractère = int(input())
chaine = input()
taille_S, taille_E = input().split()
taille_S = int(taille_S)
taille_E = int(taille_E)

# sortie

print(carte_au_tresors(nb_caractère, chaine, taille_S, taille_E))
  • Ici, tout est correct, bon doctest...
  • Mais on aurait préféré une sortie en tuple, plutôt qu'en str.

Proposition 5⚓︎

🐍 Script Python
def carte_au_trésor(taillex, tailley, deplacements):
    """
    Vous devez écrire une ligne sur la sortie, contenant deux entiers séparés par une espace : 
    le nombre de pas à faire vers le Sud, 
    et le nombre de pas à faire vers l'Est, 
    pour trouver le trésor caché.

    >>> carte_au_trésor(4, 4, "OEESSNOS")
    '2 1'
    """
    position = [0, 0]

    for i in range(len(deplacements)):
        if deplacements[i] == "O":
            if position[0] == 0:
                pass
            else:
               position[0] -= 1
        if deplacements[i] == "E":
            if position[0] == taillex - 1:
                pass
            else:
               position[0] += 1
        if deplacements[i] == "N":
            if position[1] == 0:
                pass
            else:
               position[1] -= 1
        if deplacements[i] == "S":
            if position[1] == tailley - 1:
                pass
            else:
               position[1] += 1
    return str(position[1]) + " " + str(position[0])

#tests
import doctest
doctest.testmod

#input
_ = int(input())
chaine = input()
taillex, tailley = map(int, input().split())

#output
print(carte_au_trésor(taillex, tailley, chaine))
  • Erreur
Diff
-doctest.testmod
+doctest.testmod()
  • Ne pas renvoyer une str, mais un tuple, et l'afficher en dehors de la fonction.

  • Éviter les pass.

  • Choisir de meilleurs identifiants : tailley c'est vilain.

  • On peut itérer sans indices ici, ce serait plus clair.

  • De même, il vaut mieux extraire les deux composantes et les nommer plutôt que d'utiliser [0] et [1].

Proposition 6⚓︎

🐍 Script Python
"""
Auteur : ******
https://prologin.org/train/2004/semifinal/carte_au_tresor
"""
def est_dans_le_jardin(coordonnée: list, taille_jardin: tuple)-> bool:
    """
    Renvoie True si les coordonnées sont dans le jardin

    >>> est_dans_le_jardin([2,1],(4,4))
    True
    >>> est_dans_le_jardin([4,4],(4,4))
    False
    >>> est_dans_le_jardin([3,3],(4,4))
    True
    """
    return (0 <= coordonnée[0] < taille_jardin[0]) and (0 <= coordonnée[1] < taille_jardin[1])

def trouve_tresor(instructions: str, taille_jardin: list) -> list:
    """
    Renvoie les coordonnées du tresor sous forme d'un tuple

    >>> trouve_tresor('OEESSNOS', (4, 4))
    [2, 1]
    """
    position = [0, 0]
    signification_instructions = {'O':(0, -1),'N':(-1, 0),'S':(1,0), 'E':(0,1)}
    for instruction in instructions:
        direction = signification_instructions[instruction]
        if est_dans_le_jardin([position[0] + direction[0], position[1] + direction[1]], taille_jardin):
            position[0] += direction[0]
            position[1] += direction[1]
    return position

import doctest
doctest.testmod()

# Entrées
nb_caractere_chaine = int(input())
instructions = input()
taille_jardin = tuple(map(int, input().split()))

# Sortie

print(*trouve_tresor(instructions, taille_jardin))
  • Très bien, sauf l'utilisation de [0] et [1] ; tu aurais pu extraire dans une variable avec un nom plus explicite.

Corrigé du professeur⚓︎

Version basique⚓︎

🐍 Script Python
"""
author: Franck CHAMBON
problem: https://prologin.org/train/2004/semifinal/carte_au_tresor
"""

def coord_tresor(chemin: str, nb_lignes: int, nb_colonnes: int):
    """Renvoie les coordonnées du trésor,
    en suivant le chemin dans le jardin de dimensions données.

    >>> coord_tresor("OEESSNOS", 4, 4)
    (2, 1)

    """
    i, j = 0, 0
    for sens in chemin:
        if sens == 'S':
            if i + 1 < nb_lignes:
                i += 1
        elif sens == 'N':
            if 0 <= i - 1 :
                i -= 1
        elif sens == 'E':
            if j + 1 < nb_colonnes:
                j += 1
        elif sens == 'O':
            if 0 <= j - 1 :
                j -= 1
        else:
            raise ValueError(f"Caractère invalide : {sens}")
    return i, j

# Tests
import doctest
doctest.testmod()

# Entrée
n = int(input())
chemin = input()
assert n == len(chemin)
nb_lignes, nb_colonnes = map(int, input().split())

# Sortie
i, j = coord_tresor(chemin, nb_lignes, nb_colonnes)
print(i, j)

Vérifications

Votre professeur a vérifié l'entrée grâce à assert et raise. Parfois, il a découvert des erreurs, et elles ont été signalées puis corrigées. Il n'est pas demandé aux élèves de vérifier l'entrée ; vous devez faire confiance au juge.

Meilleure version⚓︎

🐍 Script Python
"""
author: Franck CHAMBON
problem: https://prologin.org/train/2004/semifinal/carte_au_tresor
"""

def coord_tresor(chemin: str, nb_lignes: int, nb_colonnes: int) -> tuple:
    """Renvoie les coordonnées du trésor,
    en suivant le chemin dans le jardin de dimensions données.

    >>> coord_tresor("OEESSNOS", 4, 4)
    (2, 1)

    """
    def suivant(i, j, sens):
        """Renvoie les coordonnées du point (i, j) qui a subit
        un déplacement dans un sens.
        """
        dico = {'S': (1, 0), 'N': (-1, 0), 'E': (0, 1), 'O': (0, -1)}
        di, dj = dico[sens]
        return i + di, j + dj

    def est_dans_jardin(i, j):
        return (0 <= i < nb_lignes) and (0 <= j < nb_colonnes)

    i, j = 0, 0  # le point de départ, au Nord-Ouest.
    for sens in chemin:
        idi, jdj = suivant(i, j, sens)
        if est_dans_jardin(idi, jdj):
            i, j = idi, jdj
    return i, j

# Tests
import doctest
doctest.testmod()

# Entrée
n = int(input())
chemin = input()
assert n == len(chemin), f"{n}{len(chemin)}"
nb_lignes, nb_colonnes = map(int, input().split())

# Sortie
i, j = coord_tresor(chemin, nb_lignes, nb_colonnes)
print(i, j)
  • On utilise un dictionnaire pour les vecteurs en fonction du sens.
  • Des fonctions découpent mieux chaque étape.

Version POO⚓︎

🐍 Script Python
class Grille():
    def __init__(self, nb_lignes, nb_colonnes):
       self.nb_lignes = nb_lignes
       self.nb_colonnes = nb_colonnes
       self.i = None
       self.j = None

    def get_coord(self):
        # action éventuelle...
        return (self.i, self.j)

    def set_coord(self, i, j):
        # test si on veut...
        self.i = i
        self.j = j
        # autre_action_si_on_veut(...)

    def est_dans_grille(self, i, j) -> bool:
        return (0 <= i < self.nb_lignes) and (0 <= j < self.nb_colonnes)

    def deplace_si(self, instruction):
        vecteur = {'S': (1, 0), 'N': (-1, 0), 'E': (0, 1), 'O': (0, -1)}
        di, dj = vecteur[instruction]
        i = self.i + di
        j = self.j + dj
        if self.est_dans_grille(i, j):
            self.i = i
            self.j = j

    def suivre(self, chemin):
        for instruction in chemin:
            self.deplace_si(instruction)

# Entrée
n = int(input())
chemin = input()
nb_lignes, nb_colonnes = map(int, input().split())

# calcul
jardin = grille(nb_lignes, nb_colonnes)
jardin.set_coord(0, 0)  # on part du N-O
jardin.suivre(chemin)
i, j = jardin.get_coord()

# Sortie
print(i, j)