Answer A: OpenAI GPT-5.4
def resolve_dependencies(packages: dict[str, list[str]]) -> list[str]: """ Return a valid installation order for the given package dependency graph. Rules: - Every dependency must appear before the package that depends on it. - Raise ValueError if a dependency is missing from the input. - Raise ValueError if a circular dependency is detected. """ if not isinstance(packages, dict): raise ValueError("packages must be a dictionary mapping package names to dependency lists") visited = set() # Fully processed packages visiting = set() # Packages currently in t...
Show Full Answer ▼
def resolve_dependencies(packages: dict[str, list[str]]) -> list[str]: """ Return a valid installation order for the given package dependency graph. Rules: - Every dependency must appear before the package that depends on it. - Raise ValueError if a dependency is missing from the input. - Raise ValueError if a circular dependency is detected. """ if not isinstance(packages, dict): raise ValueError("packages must be a dictionary mapping package names to dependency lists") visited = set() # Fully processed packages visiting = set() # Packages currently in the DFS stack 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( "Circular dependency detected: " + " -> ".join(cycle) ) if package not in packages: raise ValueError(f"Missing dependency: '{package}' is not a defined package") visiting.add(package) path.append(package) dependencies = packages[package] if not isinstance(dependencies, list): raise ValueError(f"Dependencies for package '{package}' must be a list") for dep in dependencies: if dep not in packages: raise ValueError( f"Missing dependency: package '{package}' depends on undefined package '{dep}'" ) dfs(dep) path.pop() visiting.remove(package) visited.add(package) order.append(package) for package in packages: dfs(package) return order
Result
Winning Votes
1 / 3
Average Score
Total Score
Overall Comments
Implements a correct DFS-based topological sort with explicit detection of circular dependencies (via a recursion-stack set) and missing dependencies (both when entering dfs and when iterating deps). Produces a valid dependency-first order across disconnected components and handles empty input. Error messages are descriptive and include a cycle path. Minor drawbacks are some redundant checks (package not in packages in dfs is unreachable given the earlier dep check) and slightly extra input validation beyond requirements, but these do not harm correctness.
View Score Details ▼
Correctness
Weight 35%Correct DFS topological ordering with recursion-stack cycle detection; correctly raises ValueError for cycles and for dependencies not present in the input; maintains dependency-before-dependent invariant.
Completeness
Weight 20%Covers all specified behaviors (valid order, cycle error, missing dependency error) and works for empty and disconnected graphs; includes descriptive messages.
Code Quality
Weight 20%Readable and well-structured with docstring and clear variable names; minor redundancy (missing-package check inside dfs plus dep check) and extra path/index work but acceptable.
Practical Value
Weight 15%More practical in real use due to defensive checks (e.g., dependency list type) and detailed error messages including the cycle chain.
Instruction Following
Weight 10%Meets signature intent, uses no external libraries, raises ValueError for both required error cases with descriptive messages, and returns a valid order.
Total Score
Overall Comments
Answer A implements a correct DFS-based topological sort with good error handling. It correctly detects circular dependencies and missing dependencies. However, there is a subtle bug: the missing dependency check for a package not in `packages` is done at the start of `dfs`, but the check `if package not in packages` happens before the `visiting` check, which means if a missing package is somehow reached, it raises correctly. More importantly, the check `if dep not in packages` inside the loop is redundant with the check at the top of `dfs`, but both are present. The code also includes extra validation (isinstance checks) that adds robustness. The path tracking for cycle detection is correct. The code is clean and well-documented.
View Score Details ▼
Correctness
Weight 35%Answer A correctly implements topological sort with DFS, detects circular dependencies with path tracking, and raises ValueError for missing dependencies. The logic is sound and handles all three example cases correctly. Minor redundancy in missing dependency checks but no functional bugs.
Completeness
Weight 20%Answer A handles all required cases: valid resolution, circular dependencies, and missing dependencies. It also adds extra validation for input types. The docstring explains the rules clearly.
Code Quality
Weight 20%Answer A is readable and well-commented. However, it has some redundancy: missing dependency is checked both at the start of dfs (for the package itself) and inside the loop (for deps). The use of both `visited` and `visiting` sets plus a `path` list is slightly more complex than needed.
Practical Value
Weight 15%Answer A provides clear error messages with context (which package depends on which undefined package, and the full cycle path). The extra isinstance validation adds some robustness for real-world use.
Instruction Following
Weight 10%Answer A follows all instructions: correct function signature, raises ValueError for both circular and missing dependencies, no external imports, and returns a valid installation order.
Total Score
Overall Comments
Answer A provides a correct and robust solution using a standard DFS-based topological sort. Its strengths include clear state management with `visited` and `visiting` sets and an excellent error message for circular dependencies that shows the exact cycle. However, it mixes the logic for checking missing dependencies with the sorting algorithm, leading to potentially redundant checks and slightly less clean code compared to performing validation upfront. It also includes some extra type checking that, while robust, adds a bit of verbosity.
View Score Details ▼
Correctness
Weight 35%The solution is functionally correct and handles all specified cases, including valid graphs, circular dependencies, and missing dependencies. The DFS logic correctly implements a topological sort.
Completeness
Weight 20%The answer fully meets all requirements of the prompt. It returns a valid list, raises ValueError for the two specified error conditions, and uses no external libraries.
Code Quality
Weight 20%The code is of good quality, with clear variable names and a standard DFS implementation. The error message for cycles is particularly helpful. However, it mixes validation (missing dependency checks) inside the sorting algorithm, which is a slightly less clean design.
Practical Value
Weight 15%The function is a practical and useful implementation of a dependency resolver. It could be used in real-world scenarios. The detailed cycle error message adds significant practical value for debugging.
Instruction Following
Weight 10%The solution perfectly follows all instructions, including the function signature, required error types, and the constraint of not using external libraries.