Réponse A: OpenAI GPT-5.4
def resolve_dependencies(packages: dict[str, list[str]]) -> list[str]:
"""
Retourne un ordre d'installation valide pour le graphe de dépendances de paquets donné.
Règles :
- Chaque dépendance doit apparaître avant le paquet qui en dépend.
- Lève une ValueError si une dépendance est manquante dans l'entrée.
- Lève une ValueError si une dépendance circulaire est détectée.
"""
if not isinstance(packages, dict):
raise ValueError("packages doit être un dictionnaire mappant les noms de paquets à des listes de dépendances")
visited = set() # Paquets entièrement traités...
Afficher la réponse complète ▼
def resolve_dependencies(packages: dict[str, list[str]]) -> list[str]:
"""
Retourne un ordre d'installation valide pour le graphe de dépendances de paquets donné.
Règles :
- Chaque dépendance doit apparaître avant le paquet qui en dépend.
- Lève une ValueError si une dépendance est manquante dans l'entrée.
- Lève une ValueError si une dépendance circulaire est détectée.
"""
if not isinstance(packages, dict):
raise ValueError("packages doit être un dictionnaire mappant les noms de paquets à des listes de dépendances")
visited = set() # Paquets entièrement traités
visiting = set() # Paquets actuellement dans la pile DFS
order = []
path = []
def dfs(package: str) -> None:
if package in visited:
return
if package in visiting:
cycle_start = path.index(package)
cycle = path[cycle_start:] + [package]
raise ValueError(
"Dépendance circulaire détectée : " + " -> ".join(cycle)
)
if package not in packages:
raise ValueError(f"Dépendance manquante : '{package}' n'est pas un paquet défini")
visiting.add(package)
path.append(package)
dependencies = packages[package]
if not isinstance(dependencies, list):
raise ValueError(f"Les dépendances du paquet '{package}' doivent être une liste")
for dep in dependencies:
if dep not in packages:
raise ValueError(
f"Dépendance manquante : le paquet '{package}' dépend du paquet non défini '{dep}'"
)
dfs(dep)
path.pop()
visiting.remove(package)
visited.add(package)
order.append(package)
for package in packages:
dfs(package)
return order
Résultat
Votes gagnants
1 / 3
Score moyen
Score total
Commentaire global
Implémente un tri topologique correct basé sur DFS avec détection explicite des dépendances circulaires (via un ensemble de pile de récursion) et des dépendances manquantes (à la fois lors de l'entrée dans dfs et lors de l'itération des dépendances). Produit un ordre valide de dépendances d'abord à travers des composantes déconnectées et gère une entrée vide. Les messages d'erreur sont descriptifs et incluent un chemin de cycle. Les inconvénients mineurs sont quelques vérifications redondantes (le paquet n'est pas dans les paquets dans dfs est inaccessible étant donné la vérification de dépendance antérieure) et un travail supplémentaire sur la validation des entrées au-delà des exigences, mais cela ne nuit pas à la correction.
Afficher le détail de l’évaluation ▼
Exactitude
Poids 35%Ordre de tri topologique DFS correct avec détection de cycle par pile de récursion ; lève correctement ValueError pour les cycles et pour les dépendances non présentes dans l'entrée ; maintient l'invariant dépendance avant dépendant.
Complétude
Poids 20%Couvre tous les comportements spécifiés (ordre valide, erreur de cycle, erreur de dépendance manquante) et fonctionne pour les graphes vides et déconnectés ; inclut des messages descriptifs.
Qualité du code
Poids 20%Lisible et bien structuré avec docstring et noms de variables clairs ; légère redondance (vérification de paquet manquant dans dfs plus vérification de dépendance) et travail supplémentaire sur le chemin/l'index mais acceptable.
Valeur pratique
Poids 15%Plus pratique en utilisation réelle grâce à des vérifications défensives (par exemple, type de liste de dépendances) et des messages d'erreur détaillés incluant la chaîne de cycle.
Respect des consignes
Poids 10%Respecte l'intention de la signature, n'utilise aucune bibliothèque externe, lève ValueError pour les deux cas d'erreur requis avec des messages descriptifs et renvoie un ordre valide.
Score total
Commentaire global
La réponse A implémente un tri topologique correct basé sur DFS avec une bonne gestion des erreurs. Elle détecte correctement les dépendances circulaires et manquantes. Cependant, il y a un bug subtil : la vérification des dépendances manquantes pour un paquet qui n'est pas dans packages est effectuée au début de dfs, mais la vérification if package not in packages se produit avant la vérification visiting, ce qui signifie que si un paquet manquant est atteint d'une manière ou d'une autre, il est correctement signalé. Plus important encore, la vérification if dep not in packages dans la boucle est redondante avec la vérification en haut de dfs, mais les deux sont présentes. Le code inclut également une validation supplémentaire (vérifications isinstance) qui ajoute de la robustesse. Le suivi du chemin pour la détection de cycles est correct. Le code est propre et bien documenté.
Afficher le détail de l’évaluation ▼
Exactitude
Poids 35%La réponse A implémente correctement le tri topologique avec DFS, détecte les dépendances circulaires avec suivi de chemin et lève une ValueError pour les dépendances manquantes. La logique est saine et gère correctement les trois exemples de cas. Redondance mineure dans les vérifications de dépendances manquantes mais pas de bugs fonctionnels.
Complétude
Poids 20%La réponse A gère tous les cas requis : résolution valide, dépendances circulaires et dépendances manquantes. Elle ajoute également une validation supplémentaire pour les types d'entrée. La docstring explique clairement les règles.
Qualité du code
Poids 20%La réponse A est lisible et bien commentée. Cependant, elle présente une certaine redondance : la dépendance manquante est vérifiée à la fois au début de dfs (pour le paquet lui-même) et dans la boucle (pour les dépendances). L'utilisation des ensembles `visited` et `visiting` ainsi que d'une liste `path` est légèrement plus complexe que nécessaire.
Valeur pratique
Poids 15%La réponse A fournit des messages d'erreur clairs avec le contexte (quel paquet dépend de quel paquet indéfini, et le chemin complet du cycle). La validation supplémentaire isinstance ajoute une certaine robustesse pour une utilisation réelle.
Respect des consignes
Poids 10%La réponse A suit toutes les instructions : signature de fonction correcte, lève une ValueError pour les dépendances circulaires et manquantes, aucune importation externe, et retourne un ordre d'installation valide.
Score total
Commentaire global
La réponse A fournit une solution correcte et robuste utilisant un tri topologique standard basé sur DFS. Ses points forts incluent une gestion claire de l'état avec les ensembles visited et visiting et un excellent message d'erreur pour les dépendances circulaires qui montre le cycle exact. Cependant, elle mélange la logique de vérification des dépendances manquantes avec l'algorithme de tri, ce qui entraîne des vérifications potentiellement redondantes et un code légèrement moins propre par rapport à une validation effectuée au préalable. Elle inclut également des vérifications de type supplémentaires qui, bien que robustes, ajoutent un peu de verbosité.
Afficher le détail de l’évaluation ▼
Exactitude
Poids 35%La solution est fonctionnellement correcte et gère tous les cas spécifiés, y compris les graphes valides, les dépendances circulaires et les dépendances manquantes. La logique DFS implémente correctement un tri topologique.
Complétude
Poids 20%La réponse répond entièrement à toutes les exigences de la consigne. Elle renvoie une liste valide, lève une ValueError pour les deux conditions d'erreur spécifiées et n'utilise aucune bibliothèque externe.
Qualité du code
Poids 20%Le code est de bonne qualité, avec des noms de variables clairs et une implémentation DFS standard. Le message d'erreur pour les cycles est particulièrement utile. Cependant, il mélange la validation (vérifications des dépendances manquantes) à l'intérieur de l'algorithme de tri, ce qui est une conception légèrement moins propre.
Valeur pratique
Poids 15%La fonction est une implémentation pratique et utile d'un résolveur de dépendances. Elle pourrait être utilisée dans des scénarios réels. Le message d'erreur détaillé du cycle ajoute une valeur pratique significative pour le débogage.
Respect des consignes
Poids 10%La solution suit parfaitement toutes les instructions, y compris la signature de la fonction, les types d'erreurs requis et la contrainte de ne pas utiliser de bibliothèques externes.