Resolve package versions with a specified backtracking procedure (caret and OR constraints, yanked versions, numeric ordering)

# Resolve package versions with backtracking Our offline package mirror needs to pick one version of every package a project needs. `resolve.py` is a greedy draft that picks the newest version of everything and ignores constraints. Rewrite `resolve(index, root)` (Python 3 stdlib only) to follow this spec exactly. Example data: `index.json`, `root.json`; for them the answer is `{"esc": "0.3.1", "http": "2.6.0", "tls": "1.9.0", "tmpl": "1.5.0", "web": "2.0.0"}`. ## Data - `index`: `{package: {version_string: info}}`, `info` is `null`/`{}` or has optional `"deps": {package: constraint}` and `"yanked": true|false`. - `root`: `{package: constraint}`. - Versions are 1-3 dot-separated non-negative integers; missing parts are 0 (`1.2` = `1.2.0`) and comparison is numeric (`1.10.0 > 1.9.0`). Returned versions use the exact strings from the index. (No index has two keys of the same package with equal numeric value.) ## Constraints 1. A constraint is one or more alternatives separated by `||`; it is satisfied if **any** alternative is. An alternative is terms separated by `,`; it is satisfied if **all** terms are. Spaces around terms and between an operator and its version are allowed. 2. Terms: `==V`, `!=V`, `>=V`, `<=V`, `>V`, `<V`, `^V`, and `*` (or an empty term), which matches everything. `^V` means `>=V` and `<` the next version that increases the first non-zero part of V: `^1.4` -> `<2.0.0`, `^0.3.1` -> `<0.4.0`, `^0.0.5` -> `<0.0.6`, `^0` / `^0.0.0` -> `<0.0.1`. 3. Anything else is invalid and raises `ValueError`. Root constraints are checked before any resolving starts. ## Algorithm (the result must equal what this procedure returns) 4. State: a set of **decisions** (package -> version) and, for every package, the list of constraints currently imposed on it (from `root` and from the deps of decided versions). 5. Step: among packages that have at least one constraint and no decision, take the **alphabetically smallest**. If there is none, the decisions are the answer. If that package is not in the index, this step fails. 6. Candidates are its versions from **highest to lowest** that satisfy **every** constraint on it. A **yanked** version is skipped unless one of the constraints on that package contains a term `==V` with V numerically equal to that version (in any alternative). 7. Trying a candidate: impose its deps' constraints. The candidate fails immediately if a dep package is not in the index, or if a dep's constraint is not satisfied by an existing decision for that dep. Otherwise record the decision and continue with step 5. If everything below fails, undo this candidate (its decision and the constraints it added) and try the next candidate. 8. If all candidates fail, this step fails and the previous decision is undone (backtracking). If the very first step fails, raise `ResolutionError` (keep that class in the module). 9. Return a dict of decisions with keys in sorted order (packages never constrained are not included). 10. **Speed:** each hidden index (up to 60 packages x 12 versions, needing up to a few thousand candidate tries) must resolve within 10 seconds on our shared box. ## Scoring Hidden check groups (partial credit = fraction passed; all must pass): `operators_numeric` (1-2, numeric comparison), `caret_and_or` (1-2), `invalid_constraints` (3), `yanked_rules` (6), `backtracking` (7-8), `missing_and_unsat` (5, 7, 8), `order_determinism` (5-6), `fixture_answer`, `randomized_agreement` (300 random small indexes: same result or both `ResolutionError`), `deep_backtracking` (10).