Aller au contenu

E06 - Point le plus proche⚓︎

Le problème

Point le plus proche

Proposition 1⚓︎

🐍 Script Python
def point_plus_proche(position, nombre_point, point, score, score1, score2):



    for i in range(nombre_point):
        point = list(map(int, input().split()))
        score1 = position[0] - point[0]
        score2 = position[1] - point[1]
        if abs(score1) + abs(score2) < score:
            score = abs(score1) + abs(score2)
    return score



position = list(map(int, input().split()))
nombre_point = int(input())
point = []
score1 = 0
score2 = 0
score = 1000
print(point_plus_proche(position, nombre_point, point, score, score1, score2))
  • Mauvais noms de variables

  • score ne devrait pas être global au départ, et initialisé à au moins 4000, voire l'infini...

  • Les seuls paramètres à passer sont le point de départ et la liste des points.

  • La lecture devrait se faire avant l'appel de la fonction, et non pendant.

Proposition 2⚓︎

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

def point_le_plus_proche(x_1, y_1 , nb_points):
    distance_min = 4000     #distance max qu'on peut avoir(-1000;-1000 et 1000;1000)
    distance_variable = 0
    for i in range(nb_points):
        x, y = map(int, input().split())
        distance_variable = (abs(x_1 - x) + abs(y_1 - y))
        if distance_variable < distance_min:
            distance_min = distance_variable
    return distance_min


#Entrée
point_x, point_y = map(int, input().split())
nb_points = int(input())

#Sortie
print(point_le_plus_proche(point_x, point_y, nb_points))
  • C'est très bien d'avoir justifié la présence et la valeur de 4000.

  • Ce serait mieux de lire l'entrée entièrement avant l'appel à la fonction !

  • Il faut une espace après # dans un commentaire, et au moins deux avant sauf seul sur une ligne.

Proposition 3⚓︎

🐍 Script Python
def calcul_distance(debut,nb_fin,fins):
    """
    debut liste de 2 entiers
    nbfin entiers
    fins liste de liste de 2 entiers 
    nbliste defini par nbfin
    """
    distance = 1000
    for i in range(nb_fin-1):
        horizontale =abs( fins[i][0]- debut[0])
        verticale = abs(fins[i][1] - debut[1])
        calcul = horizontale+verticale
        if calcul < distance:
            distance = calcul
    return distance
depart =list(map(int,input(). strip(). split()))[:2]
nb_destination=int(input())
destination = list()
for u in range(nb_destination):
    dest=list(map(int,input(). strip(). split()))[:2]
    destination.append(dest)

print(calcul_distance(depart,nb_destination,destination))
import doctest
doctest.testmod()
  • Il faut initialiser distance à 4000, et non à 1000.

  • On attend de meilleurs noms de variable. (Calcul n'est pas évocateur !)

  • On effectue les tests avant d'utiliser la fonction.

  • Il faut passer de meilleurs paramètres à la fonction, seuls ceux qui sont utiles.

Proposition 4⚓︎

🐍 Script Python
def point_le_plus_proche(departx, departy, destinationx, destinationy):
    """
    Vous devez afficher un entier sur la sortie : la distance entre le point de départ, et le plus proche des points de destination.

    >>> point_le_plus_proche(10, 10, 0, 0)
    20
    >>> point_le_plus_proche(10, 10, -2, 10
    12
    >>> point_le_plus_proche(10, 10, 10, 25)
    15
    >>> point_le_plus_proche(10, 10, 5, 18)
    13
    """
    longueur_trajet = abs(departx - destinationx) + abs(departy - destinationy)
    return longueur_trajet

#input
depart_x, depart_y = list(map(int, input().split()))
nb_points = int(input())
liste = [0 for _ in range(nb_points*2)]
index = 0
for _ in range(nb_points):
    liste[index], liste[index+1] = list(map(int, input().split()))
    index += 2

#output
liste_longueurs = []
index = 0
for _ in range(nb_points):
    liste_longueurs.append(point_le_plus_proche(int(depart_x), int(depart_y), liste[index], liste[index+1]))
    index += 2
print(min(liste_longueurs))
  • Ta fonction est mal nommée, elle devrait s'appeler distance ; tu fais le calcul du plus proche en dehors...

  • Il vaudrait mieux utiliser une liste de tuple, plutôt que jouer avec des index à décaler de deux... Ça fait bricolage avec un vieux langage, comme du C...

Proposition 5⚓︎

🐍 Script Python
def le_plus_proche(nb_destination: int, distance_minimale: int, x_1: int, x_2: int, destinations: list) -> int:
    """

    Renvoie la distance entre le point de départ, et le plus proche des points de destination.

    >>> le_plus_proche(3, 10000, 10, 10, [[0, 0], [-2, 10], [10, 25], [5, 18]])
    12

    """


    d_1 = destinations[-1][0]
    d_2 = destinations[-1][1]

    if nb_destination == 0:
        return distance_minimale
    else:
        if d_1 >= x_1 and d_2 >= x_2:
            distance = abs(d_1 - x_1 + d_2 - x_2)

        elif d_1 <= x_1 and d_2 <= x_2:
            distance = abs(x_1 - d_1 + x_2 - d_2)

        elif d_1 >= x_1 and d_2 <= x_2:
            distance = abs(d_1 - x_1 + x_2 - d_2)

        elif d_1 <= x_1 and d_2 >= x_2:
            distance = abs(x_1 - d_1 + d_2 - x_2)

        if distance < distance_minimale:
            distance_minimale = distance
        destinations.pop()
        return le_plus_proche(nb_destination - 1, distance_minimale, x_1, x_2, destinations)


# Test

import doctest
doctest.testmod()

# Entrée

x_1, x_2 = input().split()
nb_destination = int(input())

destinations = [list(map(int, input().split())) for _ in range(nb_destination)]



# Sortie

print(le_plus_proche(nb_destination - 1, 10000, int(x_1), int(x_2), destinations))
  • Ne pas traiter le cas où il n'y a pas de destination... Il n'y a alors pas de minimum !!! (Ou alors renvoyer l'infini.)

    • On commencera le cas à une distance.
  • Les 4 cas testés peuvent se traiter en un seul avec la valeur absolue !

  • Version récursive possible, oui, mais la version itérative n'est pas plus difficile à écrire ; on préférera alors la version itérative ! Mais c'est un bel effort ; bravo.

Proposition 6⚓︎

🐍 Script Python
def le_plus_proche(position: tuple, liste_points: list) -> int:
    """
    Renvoie la distance du point de départ au plus proche des points de destination.

    >>> le_plus_proche((10, 10), [(0, 0),(-2, 10),(10, 25),(5, 18)])
    12

    """
    min = 4000
    for point in liste_points:
        calcul = abs(point[0] - position[0]) + abs(point[1] - position[1])
        if calcul < min:
            min = calcul
    return min

import doctest
doctest.testmod()

# Entrées
position = tuple(map(int, input().split()))
nombre_points = int(input())
liste_points = [tuple(map(int, input().split())) for _ in range(nombre_points)]

# Sortie
print(le_plus_proche(position, liste_points))
  • Attention, tu as écrasé la fonction min.
  • Tu aurais pu initialiser à l'infini au lieu de 4000.
  • Tu aurais pu définir une fonction distance.
  • calcul porte peu de sens, il vaut mieux un meilleur nom.
  • il vaut mieux extraire le tuple dans (x, y) et ne plus utiliser d'indice ; le code est plus lisible.

Proposition 7⚓︎

🐍 Script Python
def point_le_plus_proche(destination, nb_point, point_depart):
    """
    Renvoie destance du point le plus proche
    """
    score = 4000
    somme_x = 0
    somme_y = 0
    for i in range(nb_point):
        if destination[i][0] < point_depart[0]:
            while destination[i][0] + somme_x < point_depart[0]:
                somme_x += 1
        if destination[i][0] > point_depart[0]:
            while destination[i][0] - somme_x > point_depart[0]:
                somme_x += 1
        if destination[i][1] == point_depart[1]:
            somme_y = 0
        if destination[i][1] < point_depart[1]:
            while destination[i][1]+ somme_y < point_depart[1]:
                somme_y += 1
        if destination[i][1] > point_depart[1]:
            while destination[i][1]-somme_y > point_depart[1]:
                somme_y += 1
        somme = somme_x + somme_y
        if somme < score:
            score = somme
        somme = 0
        somme_y = 0
        somme_x = 0
    return score

#Entrée
x, y = list(map(int, input().split()))
point_depart = [x, y]
nb_point_destination = int(input())
destination = [[]for _ in range(nb_point_destination)]
for i in range(nb_point_destination):
    point_destination = list(map(int, input().split()))
    destination[i] = point_destination

#Sortie
print(point_le_plus_proche(destination, nb_point_destination, point_depart))
  • Il y a bien plus simple pour calculer la distance, avec deux soustractions au lieu de deux boucles...

Proposition 8⚓︎

🐍 Script Python
def le_plus_proche(COORD_DEPART : tuple, nb_destinations : int, liste_destinations : list, mini : int)-> int:
    """
    Fonction renvoyant la distance la plus courte par rapport aux coordonnées de départ.

    >>> le_plus_proche((10, 10), 4, [(0, 0), (-2, 10), (10, 25), (5, 18)], 4000)
    12

    >>> le_plus_proche((12, 4), 0, [], 4000))
    4000

    """
    if nb_destinations == 0:
        return mini
    else:
        résultat = abs(COORD_DEPART[0] - liste_destinations[nb_destinations -1][0]) + abs(COORD_DEPART[1] - liste_destinations[nb_destinations -1][1])
        if résultat < mini:
            mini = résultat
    return le_plus_proche(COORD_DEPART, nb_destinations -1, liste_destinations, mini)


# Entrées

mini = 4000
COORD_DEPART = tuple(map(int, input().split()))
nb_destinations = int(input())
liste_destinations = [tuple(map(int, input().split())) for _ in range(nb_destinations)]

# Sortie

print(le_plus_proche(COORD_DEPART, nb_destinations, liste_destinations, mini))
  • Ici la version récursive n'est pas plus facile à écrire que l'itérative ; choix très discutable. Cela rend tes paramètres de fonctions peu lisibles. Cela reste un bel exercice !

Corrigé du professeur⚓︎

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

def distance_min(depart: tuple, points: list) -> int:
    """Renvoie la distance entre le point de départ,
     et le plus proche des points destination.

    >>> depart = (10, 10)
    >>> points = [(0, 0), (-2, 10), (10, 25), (5, 18)]
    >>> distance_min(depart, points)
    12

    """
    def distance_1(x_1, y_1, x_2, y_2):
        "Distance de Manhattan"
        return abs(x_2 - x_1) + abs(y_2 - y_1)

    d_mini = float('inf')  # l'infini, oui.
    # Peut-on faire moins ?
    x_0, y_0 = depart
    for x, y in points:
        d = distance_1(x_0, y_0, x, y)
        if d < d_mini:
            d_mini = d
    return d_mini

# Tests
import doctest
doctest.testmod()

# Entrée
x_0, y_0 = map(int, input().split())
assert -1000 <= x_0 <= +1000
assert -1000 <= y_0 <= +1000
depart = (x_0, y_0)

nb_points = int(input())
points = []
for _ in range(nb_points):
    x, y = map(int, input().split())
    assert -1000 <= x <= +1000
    assert -1000 <= y <= +1000
    points.append((x, y))

# Sortie
print(distance_min(depart, points))

Exercice : Créer une classe point avec une méthode distance_1 et réécrire cette solution dans un style POO.

Rappel

Il sera inutile de reprendre les vérifications de l'entrée par le professeur (avec assert). Faire confiance à l'entrée fournie.