Package Dependency Planner

Problem
Develop a tool named pkgplan that resolves the installation order of dependencies given a JSON file containing a list of packages and their dependencies.
Time limit: 90-120 minutes
Difficulty: medium
Limitation: standard library only

These JSON files cover valid dependencies, a missing dependency, and a circular dependency:

{
  "packages": {
    "webapp": {
      "depends": ["python", "nginx"]
    },
    "python": {
      "depends": ["libc", "openssl"]
    },
    "nginx": {
      "depends": ["libc", "openssl"]
    },
    "openssl": {
      "depends": ["libc"]
    },
    "libc": {
      "depends": []
    }
  }
}

{
  "packages": {
    "webapp": {
      "depends": ["python", "nginx"]
    },
    "python": {
      "depends": ["libc", "openssl"]
    },
    "nginx": {
      "depends": ["libc", "openssl"]
    },
    "openssl": {
      "depends": ["libc"]
    }
  }
}

{
  "packages": {
    "webapp": {
      "depends": ["python", "nginx"]
    },
    "python": {
      "depends": ["libc", "openssl"]
    },
    "nginx": {
      "depends": ["libc", "openssl"]
    },
    "openssl": {
      "depends": ["libc"]
    },
    "libc": {
      "depends": ["openssl"]
    }
  }
}

From the code directory, run:

pkgplan tests/json/pacakges.json webapp

The expected output for each JSON file is:

Installation plan for webapp:

1. libc
2. openssl
3. python
4. nginx
5. webapp

Requires installing 5 packages.

Error: Missing dependency 'libc' required by 'python'.

Error: Circular dependency detected: libc -> openssl -> libc.

Fundamental logic

The standard library in Python provides the TopologicalSorter in the graphlib module. This class contains the core logic for resolving previous JSON file into an installation plan. We can use the CycleError to detect circular dependencies. Regarding missing packages, we must implement our own logic. For the CLI logic, we can use the argparse module.

Architecture

The layout for this application follows the usual one for CLI applications.

pkgplan/
├── src
│   └── pkgplan
│       ├── __init__.py
│       ├── __main__.py
│       ├── cli.py
│       ├── dependencies.py
│       ├── loader.py
│       └── print.py
├── tests
│   ├── expected
│   │   ├── broken.txt
│   │   ├── circular.txt
│   │   └── packages.txt
│   ├── json
│   │   ├── broken.json
│   │   ├── circular.json
│   │   └── pacakges.json
│   └── test_pkgplan.py
├── pyproject.toml
└── README.rst

Metadata

pyproject.toml uses Flit to build the package. With dynamic = ["version"], Flit reads __version__ from __init__.py. The [project.scripts] entry creates the pkgplan command and connects it to pkgplan.__main__:main. README.rst provides the package description and instructions for installation, use, and testing.

Package Dependency Planner
==========================

About
-----

``pkgplan`` reads a JSON package catalog and prints the installation order for
the requested package and its dependencies.

Prerequisites
-------------

You need Python 3.12 or later and pip. The planner uses only the Python standard
library at runtime.

Getting Started
---------------

From this directory, install the package:

.. code-block:: console

   python -m pip install .

Generate an installation plan:

.. code-block:: console

   pkgplan tests/json/pacakges.json webapp

User Guide
----------

The installed package also supports module execution:

.. code-block:: console

   python -m pkgplan tests/json/pacakges.json webapp

Use ``pkgplan --help`` to see the command-line arguments.

The JSON file must contain a ``packages`` object. Each package has a ``depends``
list of package names. Use an empty list for packages with no dependencies:

.. code-block:: json

   {
     "packages": {
       "app": {
         "depends": ["libc"]
       },
       "libc": {
         "depends": []
       }
     }
   }

The planner includes only the requested package and its dependencies. Shared
dependencies appear once, before the packages that require them. Every
package's metadata is validated, but missing references and cycles are checked
only in the requested dependency graph.

Successful plans go to standard output and return exit status 0. File errors,
invalid catalogs, unknown packages, missing dependencies, and cycles go to
standard error and return status 1. These failures produce no partial plan.
Invalid or missing command-line arguments return status 2.

The ``tests/json`` directory contains test inputs, including valid,
missing-dependency, and circular examples. Their expected output is stored in
``tests/expected``. To run the error examples:

.. code-block:: console

   pkgplan tests/json/broken.json webapp
   pkgplan tests/json/circular.json webapp

Flit builds the package using ``pyproject.toml``. The version is declared once
as ``__version__`` in ``src/pkgplan/__init__.py`` and read by Flit through
``dynamic = ["version"]``. The ``[project.scripts]`` entry creates the
``pkgplan`` command and calls ``pkgplan.__main__:main``.

The suite has one test each for valid, circular, and broken dependencies.
Each test loads a catalog from ``tests/json`` and checks the result against
the corresponding text file in ``tests/expected``. The tests call the loader,
resolver, and printer directly.

Run the standard-library tests from this directory:

.. code-block:: console

   python -m unittest discover -s tests

[build-system]
build-backend = "flit_core.buildapi"
requires = [ "flit_core>=3.11,<5" ]

[project]
name = "pkgplan"
dynamic = [ "version" ]
description = "Plan package installation from JSON dependencies."
readme = "README.rst"
requires-python = ">=3.12"
authors = [ { name = "Jorge Martinez" } ]
dependencies = []

[project.scripts]
pkgplan = "pkgplan.__main__:main"

[tool.flit.sdist]
include = [ "tests/" ]

"""Resolve package installation order using the Python standard library.

The loader validates JSON catalogs, the dependency resolver builds an
installation plan, and the printing module formats plans and errors.
Importing this package does not run the command-line interface.

Notes
-----
Flit reads ``__version__`` when building the package. Update this value to
change the distribution version.
"""

__version__ = "1.0.dev0"

Implementation

Use Python 3.12 or later. Install the package from the code directory with python -m pip install .. You can then run pkgplan or python -m pkgplan.

"""Run the package dependency planner.

The `main` function connects argument parsing, catalog loading, dependency
resolution, and output. Both the installed ``pkgplan`` command and
``python -m pkgplan`` use this entry point.
"""

from collections.abc import Sequence

from .cli import parse_args
from .dependencies import resolve_dependencies
from .loader import load_packages
from .print import print_error, print_pkgplan


def main(argv: Sequence[str] | None = None) -> int:
    """Run the planner and return its exit status.

    Load the requested catalog, build the installation plan, and print it.
    File, decoding, catalog, and dependency errors are written to standard
    error without printing an installation plan.

    Parameters
    ----------
    argv : sequence of str, optional
        Command-line arguments, excluding the executable name. If ``None``,
        use ``sys.argv[1:]``.

    Returns
    -------
    int
        0 if the plan was printed successfully, or 1 if reading the file,
        validating the catalog, or resolving dependencies failed.

    Raises
    ------
    SystemExit
        If argument parsing exits: status 0 for ``--help`` or status 2
        for invalid or missing arguments.

    See Also
    --------
    pkgplan.loader.load_packages : Read and validate the catalog.
    pkgplan.dependencies.resolve_dependencies : Build the installation plan.
    pkgplan.print.print_pkgplan : Print the plan and package count.

    Notes
    -----
    The catalog is opened as UTF-8 text and closed before dependencies are
    resolved. The caller converts the returned status into a process exit
    status; calling this function directly does not exit after planning.
    """
    args = parse_args(argv)
    try:
        with args.jsonfile.open(encoding="utf-8") as file:
            packages = load_packages(file)
        plan = resolve_dependencies(packages, args.package)
    except (OSError, UnicodeError, ValueError) as error:
        print_error(error)
        return 1

    print_pkgplan(args.package, plan)
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

"""Define arguments for the package dependency planner.

The ``parse_args`` function reads two positional command-line arguments:
``jsonfile``, converted to a ``pathlib.Path``, and ``package``, kept as a string.
Parsing does not open the file or resolve dependencies.

Notes
-----
The parser exits with status 0 for ``--help`` and status 2 for invalid
arguments. The application calls ``parse_args`` from its entry point.
"""

import argparse
from collections.abc import Sequence
from pathlib import Path


def parse_args(argv: Sequence[str] | None = None) -> argparse.Namespace:
    """Parse arguments, using the command line when ``argv`` is ``None``."""
    parser = argparse.ArgumentParser(
        prog="pkgplan",
        description="Find the installation order for a package and its dependencies.",
    )
    parser.add_argument(
        "jsonfile",
        type=Path,
        help="JSON file containing available packages and their dependencies.",
    )
    parser.add_argument("package", help="Package to install.")
    return parser.parse_args(argv)

"""Resolve installation order and detect dependency errors.

The resolver collects the requested package's dependency graph and uses
`graphlib.TopologicalSorter` to order packages before their dependents.
"""

from collections.abc import Mapping, Sequence
from graphlib import CycleError, TopologicalSorter


def resolve_dependencies(
    packages: Mapping[str, Sequence[str]], package: str
) -> list[str]:
    """Return the installation order for a package and its dependencies.

    Include only packages reachable from the requested package. Shared
    dependencies appear once in the returned plan.

    Parameters
    ----------
    packages : mapping of str to sequence of str
        Package names mapped to dependency lists, as returned by the
        catalog loader. The mapping is not modified.
    package : str
        Name of the package to install.

    Returns
    -------
    list of str
        Package names in dependency order, ending with `package`. Each
        dependency appears before the packages that require it.

    Raises
    ------
    ValueError
        If `package` is unknown, a reachable package requires a missing
        dependency, or the reachable graph contains a cycle. Cycle errors
        include a closed path through the conflicting packages.

    See Also
    --------
    pkgplan.loader.load_packages : Read and validate a package catalog.
    graphlib.TopologicalSorter : Order a graph by predecessor relationships.

    Notes
    -----
    An explicit stack collects the reachable graph without recursion.
    Dependencies are pushed in reverse order to visit them in their listed
    order. The graph maps each package to its prerequisites, as required by
    `graphlib.TopologicalSorter`. Multiple installation orders can be valid
    when packages do not depend on one another.

    Missing references and cycles in unrelated packages do not affect the
    plan. Traversal and sorting take O(V + E) time and space for the
    reachable graph, where V is the number of packages and E the number of
    dependency references.

    Examples
    --------
    >>> from pkgplan.dependencies import resolve_dependencies
    >>> packages = {"app": ["python"], "python": ["libc"], "libc": []}
    >>> resolve_dependencies(packages, "app")
    ['libc', 'python', 'app']
    """
    if package not in packages:
        raise ValueError(f"Unknown package '{package}'.")

    graph: dict[str, Sequence[str]] = {}
    pending = [package]
    while pending:
        name = pending.pop()
        if name in graph:
            continue
        dependencies = packages[name]
        for dependency in dependencies:
            if dependency not in packages:
                raise ValueError(
                    f"Missing dependency '{dependency}' required by '{name}'."
                )
        graph[name] = dependencies
        pending.extend(reversed(dependencies))

    try:
        return list(TopologicalSorter(graph).static_order())
    except CycleError as error:
        cycle = " -> ".join(error.args[1])
        raise ValueError(f"Circular dependency detected: {cycle}.") from error

"""Load and validate JSON package catalogs.

The loader converts package metadata into the dependency mapping accepted
by the resolver. It checks the catalog structure before graph traversal.
"""

import json
from typing import TextIO


def load_packages(file: TextIO) -> dict[str, list[str]]:
    """Read and validate package dependencies from a JSON file.

    Convert the catalog's ``packages`` object into a mapping from package
    names to their dependency lists.

    Parameters
    ----------
    file : file-like object
        Readable text stream containing a JSON object with a ``packages``
        mapping. Each package must have a metadata object whose ``depends``
        value is a list of strings, including an empty list for no
        dependencies. Reading starts at the stream's current position.

    Returns
    -------
    dict of str to list of str
        Package names mapped to dependency lists in catalog order.

    Raises
    ------
    json.JSONDecodeError
        If the stream contains invalid JSON.
    ValueError
        If the catalog has no ``packages`` object, package metadata is not
        an object, or a ``depends`` value is not a list of strings.
    OSError
        If reading the stream fails.
    UnicodeError
        If decoding the text stream fails.

    See Also
    --------
    pkgplan.dependencies.resolve_dependencies : Check dependency references.

    Notes
    -----
    The caller owns the stream and must close it. This function validates
    every package's metadata, including packages outside the requested
    graph. Missing dependency references and cycles are checked later by
    the resolver.

    Examples
    --------
    >>> import io
    >>> from pkgplan.loader import load_packages
    >>> catalog = io.StringIO('{"packages": {"libc": {"depends": []}}}')
    >>> load_packages(catalog)
    {'libc': []}
    """
    catalog = json.load(file)
    if not isinstance(catalog, dict) or not isinstance(catalog.get("packages"), dict):
        raise ValueError("JSON file must contain a 'packages' object.")

    packages: dict[str, list[str]] = {}
    for name, metadata in catalog["packages"].items():
        if not isinstance(metadata, dict):
            raise ValueError(f"Package '{name}' must be an object.")
        dependencies = metadata.get("depends")
        if not isinstance(dependencies, list) or not all(
            isinstance(dependency, str) for dependency in dependencies
        ):
            raise ValueError(f"Package '{name}' must have a 'depends' list of strings.")
        packages[name] = dependencies
    return packages

"""Print installation plans and errors.

Plans are written to standard output. Error messages are written to
standard error so callers can capture them separately.
"""

import sys
from collections.abc import Iterable


def print_pkgplan(package: str, plan: Iterable[str]) -> None:
    """Print the installation order and package count to standard output.

    Write the package heading, numbered installation steps, and total
    count using the command-line output format.

    Parameters
    ----------
    package : str
        Name of the requested package, used in the heading.
    plan : iterable of str
        Package names in installation order. The iterable must be finite.
        A generator is consumed once and materialized before printing.

    See Also
    --------
    pkgplan.dependencies.resolve_dependencies : Build the installation plan.
    print_error : Write an error to standard error.

    Notes
    -----
    The count includes the requested package. This function preserves the
    supplied order and does not validate or deduplicate the plan.

    Examples
    --------
    >>> from pkgplan.print import print_pkgplan
    >>> print_pkgplan("python", iter(["libc", "python"]))
    Installation plan for python:
    <BLANKLINE>
    1. libc
    2. python
    <BLANKLINE>
    Requires installing 2 packages.
    """
    installation_order = list(plan)
    print(f"Installation plan for {package}:\n")
    for index, dependency in enumerate(installation_order, 1):
        print(f"{index}. {dependency}")
    count = len(installation_order)
    noun = "package" if count == 1 else "packages"
    print(f"\nRequires installing {count} {noun}.")


def print_error(error: Exception | str) -> None:
    """Print an error to standard error.

    Prefix the error description with ``Error:`` and append a newline.

    Parameters
    ----------
    error : Exception or str
        Error description, converted to a string for display.

    See Also
    --------
    print_pkgplan : Write a successful installation plan to standard output.

    Examples
    --------
    >>> from contextlib import redirect_stderr
    >>> from io import StringIO
    >>> from pkgplan.print import print_error
    >>> stream = StringIO()
    >>> with redirect_stderr(stream):
    ...     print_error(ValueError("Unknown package 'app'."))
    >>> print(stream.getvalue(), end="")
    Error: Unknown package 'app'.
    """
    print(f"Error: {error}", file=sys.stderr)

Explanation

__main__.py coordinates the planner. It calls parse_args() from cli.py to parse the JSON file path and package name with argparse. The entry point opens the file as UTF-8 text, and loader.py validates the catalog and returns a dictionary mapping package names to dependency lists.

dependencies.py uses an explicit stack to collect the requested package’s dependencies, checking for missing references along the way. It passes this graph to graphlib.TopologicalSorter, which places dependencies before their dependents and includes each package once. Unknown packages, missing dependencies, and cycles raise ValueError; cycle messages include the conflicting path. Unrelated packages are excluded from the plan.

print.py writes the numbered plan and package count to standard output, or errors to standard error. Planning finishes before output begins, so failures produce no partial plan. Both pkgplan and python -m pkgplan call main(): success returns status 0, file or planning errors return 1, and invalid arguments exit with 2. __init__.py identifies the package without running the planner.

Tests

The test suite uses the standard library’s unittest module. Each test loads a catalog from tests/json and compares its result with a text file in tests/expected. From the code directory, run:

python -m unittest discover -s tests

PlannerTests has one test for each case: valid, circular, and broken dependencies. The valid test resolves the installation order, captures print_pkgplan() output, and compares it with packages.txt. The circular and broken tests check that resolve_dependencies() raises ValueError with the expected message. The tests call the loader, resolver, and printer directly.

"""Test valid, circular, and broken package dependencies."""

import unittest
from contextlib import redirect_stdout
from io import StringIO
from pathlib import Path

from pkgplan.dependencies import resolve_dependencies
from pkgplan.loader import load_packages
from pkgplan.print import print_pkgplan

TESTS_DIR = Path(__file__).resolve().parent


def load_catalog(name: str) -> dict[str, list[str]]:
    with (TESTS_DIR / "json" / f"{name}.json").open(encoding="utf-8") as file:
        return load_packages(file)


def expected_output(name: str) -> str:
    return (TESTS_DIR / "expected" / f"{name}.txt").read_text(encoding="utf-8")


class PlannerTests(unittest.TestCase):
    def test_valid_dependencies(self) -> None:
        packages = load_catalog("pacakges")

        plan = resolve_dependencies(packages, "webapp")

        output = StringIO()
        with redirect_stdout(output):
            print_pkgplan("webapp", plan)
        self.assertEqual(output.getvalue(), expected_output("packages"))

    def test_circular_dependencies(self) -> None:
        packages = load_catalog("circular")

        with self.assertRaises(ValueError) as error:
            resolve_dependencies(packages, "webapp")

        self.assertEqual(f"Error: {error.exception}\n", expected_output("circular"))

    def test_broken_dependencies(self) -> None:
        packages = load_catalog("broken")

        with self.assertRaises(ValueError) as error:
            resolve_dependencies(packages, "webapp")

        self.assertEqual(f"Error: {error.exception}\n", expected_output("broken"))


if __name__ == "__main__":
    unittest.main()