py_package_dependency_resolver

Código comentado línea a línea y paso a paso:

Entregas: py_package_dependency_resolver.py con package_dependency_resolver(packages). Rank 04 · nivel 3.

Qué pide (en palabras normales)

Subject (enunciado original)
Write a function that determines a valid package installation order by resolving dependencies. Use topological sorting to ensure dependencies are installed before the packages that require them.

The function should:
- Take a dictionary where keys are package names and values are lists of dependencies
- Return packages in installation order (dependencies first)
- Return empty list if no valid order exists (circular dependencies)
- Handle empty input and isolated dependency chains
- Ignore references to packages not in the input dictionary

Algorithm requirements:
- Use topological sorting (e.g., Kahn's algorithm)
- Process packages with no remaining dependencies first
- Ensure deterministic output when multiple valid orders exist

Edge cases to handle:
- Empty input: return empty list
- Packages with no dependencies: include in output first
- Multiple independent chains: process all chains
- Circular dependencies: return empty list
- Non-existent dependencies: ignore missing packages
- Self-dependencies: return empty list

Notes:
- For deterministic output, process packages alphabetically when choices exist
- A package cannot be installed until all its dependencies are installed
- If any circular dependency exists, no valid installation order is possible

Expected file: py_package_dependency_resolver.py
Function signature:
def package_dependency_resolver(packages: dict[str, list[str]]) -> list[str]:
Forbidden: graphlib.TopologicalSorter

Examples:
package_dependency_resolver({"app": ["database"], "database": ["driver"], "driver": []})
=> ["driver", "database", "app"]
package_dependency_resolver({"A": [], "B": ["A"], "C": ["A", "B"]})
=> ["A", "B", "C"]
package_dependency_resolver({})
=> []
package_dependency_resolver({"X": ["Y"], "Y": ["X"]})
=> []
package_dependency_resolver({"web": [], "api": [], "frontend": ["web"], "backend": ["api"]})
=> ["api", "web", "backend", "frontend"]

Kahn por niveles

remaining = {name: {d for d in deps if d in packages} for name, deps in packages.items()}
order = []
while remaining:
    ready = sorted(name for name, deps in remaining.items() if not deps)
    if not ready:
        return []
    order.extend(ready)
    for name in ready:
        del remaining[name]
    for deps in remaining.values():
        deps.difference_update(ready)
return order

Cada ronda instalo todo lo que ya no espera a nadie, en orden alfabético, y lo descuento de los demás. Si en alguna ronda nadie está listo y aún quedan paquetes, es que se esperan entre sí: ciclo.

El orden del ejemplo

{"web": [], "api": [], "frontend": ["web"], "backend": ["api"]} → ["api", "web", "backend", "frontend"]. Fíjate: backend va después de web aunque alfabéticamente sea menor. Es porque web estaba lista en la primera ronda y backend no. Un Kahn que elige siempre el menor alfabético de todo lo listo daría api, backend, web, frontend y falla. Por eso se procesa por rondas.

Trampas