Solve checksum and dependency debugging tasks

Problem Statement

You are building a configuration manager that verifies and deploys feature flags in a distributed system. Each feature is defined by a raw configuration string, and a user provides a list of requested features to activate.

Each configuration string in configs follows the format: "::,,..."

If a feature has no dependencies, the dependency section is empty (e.g., "core:12345:").

Step 1: Checksum Validation

For each feature name name, compute its checksum using the polynomial rolling hash: checksum = sum(ord(c) * (37 ** i) for i, c in enumerate(name)) % 1000003

If the computed checksum (represented as a decimal string) does not match ``, the configuration is considered corrupted and cannot be used.

Step 2: Dependency Resolution & Cycle Detection

A feature F is valid if and only if:

1. It has a valid, uncorrupted configuration.
2. All features in its transitive dependency chain exist and are uncorrupted.
3. There is no circular dependency anywhere in its reachable dependency graph.

Step 3: Deployment Plan

From the requested list, identify all valid features. Construct a final deployment list containing all valid requested features and all their transitive dependencies. The deployment list must satisfy the following conditions:

• Every dependency B of a feature A must appear before A.
• Every feature appears at most once.
• Among all features whose dependencies have already been deployed, select the one that is lexicographically smallest first.

If none of the requested features can be validly enabled, return an empty list.

Function Signature

def resolve_features(configs: list[str], requested: list[str]) -> list[str]:
    pass

Constraints

• 1 is a non-empty string of decimal digits.
• Feature names within configs are unique.
• Time complexity target: O(V + E log V) where V is the number of features and E is the number of dependency edges.

Examples

Example 1

configs = [
    "auth:97:core",
    "core:99:",
    "billing:123:auth"
]
requested = ["auth"]

Calculated checksums:

• "core": (ord('c')*37^0 + ord('o')*37^1 + ord('r')*37^2 + ord('e')*37^3) % 1000003 = 99 + 4107 + 156066 + 5110597 % 1000003 = 5270869 % 1000003 = 270854 (suppose matching the configured value).

Assuming all checksums in this example match their configured values: auth depends on core, and core has no dependencies.

Output:

["core", "auth"]

Example 2

configs = [
    "a:97:b",
    "b:98:a",
    "c:99:"
]
requested = ["a", "c"]

a and b form a circular dependency (a -> b -> a), making a invalid. c has no dependencies and is valid.

Output:

["c"]