Placement 6/6: Find Every Module in an Import Cycle

Solve this without the hints and you can skim the modules and packaging track.

An import cycle is a loop of imports. Module a imports b, and b imports a, either directly or through other modules. Python adds a module to sys.modules, its table of loaded modules, before it runs the module's code. So in a cycle, one module can find the other half-built and fail with an ImportError about a "partially initialized module". Not every cycle fails, but you want to know where they are.

You get the imports as a dictionary that maps each module to the modules it imports directly. Each module and one of its imports form an edge, an arrow from the importing module to the imported one. Together, the modules and edges form a graph. Your code only reads the dictionary. It does not import or open anything.

What to write

Write solve(imports: dict[str, list[str]]) -> frozenset[str]. Return every module that can get back to itself by following one or more edges.

solve({"a": ["b"], "b": ["c"], "c": ["a"], "d": ["a"]})
# frozenset({"a", "b", "c"})

d leads into the cycle, but no path leads back to d, so d is not on a cycle.

• A module that imports itself counts. {"a": ["a"]} returns frozenset({"a"}).
• A chain with no way back, such as a to b to c, is not a cycle.
• Include every cycle, even ones in separate parts of the graph.
• Repeated edges do not change the result.
• A name that appears only as an import target, such as "numpy", has no edges of its own in this input. It cannot be on a cycle.
• An empty dictionary returns frozenset().

The helper

Also complete reachable(graph: Mapping[str, Sequence[str]], start: str) -> frozenset[str]. It returns every name you can reach from start by following at least one edge, target-only names included. The result contains start only if some path leads back to it. A start with no edges of its own returns an empty set.

Begin the search at start's direct imports, and don't mark start as visited first. Otherwise every module would seem to reach itself without following any edge. Keep a set of visited names, so a cycle cannot make the search loop forever. Don't change the input dictionary.

Both functions return a frozenset, a set that nobody can add to or remove from. The order of the modules does not matter, and callers cannot change the result. One search per module is fast enough for these inputs.