E06 - Point le plus proche⚓︎
Le problème
Proposition 1⚓︎
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⚓︎
"""
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⚓︎
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⚓︎
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⚓︎
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⚓︎
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⚓︎
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⚓︎
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⚓︎
"""
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.