def resolve(requirements, package_index):
"""
初期の要件とパッケージインデックスが与えられたときに、パッケージのバージョンを解決します。

requirements: "A>=1.2.0" や "B" のような要件文字列のリスト
package_index: パッケージ -> { バージョン文字列: [依存関係の要件文字列] } の辞書

戻り値: パッケージ -> 解決されたバージョン文字列 をマッピングする辞書
競合が発生した場合は説明付きで ValueError を送出します。
"""
import copy
import re

OPS = ["==", "!=", ">=", "<=", ">", "<"]

def parse_version(v):
    # セマンティックバージョンを整数のタプルに解析します（major, minor, patch, ...）
    parts = tuple(int(p) for p in v.split('.'))
    return parts

def version_cmp_key(v):
    return parse_version(v)

def parse_requirement(req):
    req = req.strip()
    # 演算子が存在するか探す
    for op in OPS:
        if op in req:
            name, ver = req.split(op, 1)
            name = name.strip()
            ver = ver.strip()
            return name, op, ver
    # 演算子がない場合は任意のバージョンを意味します
    name = req
    return name.strip(), None, None

def satisfies_one(ver_str, op, ver_req_str):
    if op is None:
        return True
    left = parse_version(ver_str)
    right = parse_version(ver_req_str)
    if op == '==':
        return left == right
    if op == '!=':
        return left != right
    if op == '>=':
        return left >= right
    if op == '<=':
        return left <= right
    if op == '>':
        return left > right
    if op == '<':
        return left < right
    return False

def satisfies_all(ver_str, constraints):
    # constraints: op が None である可能性がある (op, ver_str) のリスト
    return all(satisfies_one(ver_str, op, vreq) for (op, vreq) in constraints)

# 初期制約辞書を構築: パッケージ -> (op, ver) のリスト
constraints = {}

def add_constraint(constraints_map, pkg, op, ver):
    if pkg not in constraints_map:
        constraints_map[pkg] = []
    # 同一の重複する制約を避ける
    if (op, ver) not in constraints_map[pkg]:
        constraints_map[pkg].append((op, ver))

# トップレベルの要件から初期化
for req in requirements:
    name, op, ver = parse_requirement(req)
    if name not in package_index:
        raise ValueError(f"パッケージ '{name}' が必要ですが、パッケージインデックスに見つかりません")
    add_constraint(constraints, name, op, ver)

# あるパッケージの制約の下で許容されるバージョンの一覧を計算するヘルパー
def allowed_versions(pkg, constraints_map):
    if pkg not in package_index:
        raise ValueError(f"パッケージ '{pkg}' がパッケージインデックスに見つかりません")
    cons = constraints_map.get(pkg, [])
    versions = list(package_index[pkg].keys())
    # フィルタリング
    filtered = [v for v in versions if satisfies_all(v, cons)]
    # バージョンで降順にソート（最新を先頭）
    filtered.sort(key=version_cmp_key, reverse=True)
    return filtered

# バックトラック探索
def search(resolved, constraints_map):
    # 制約のあるすべてのパッケージが解決済みなら、終了
    to_resolve = [p for p in constraints_map.keys() if p not in resolved]
    if not to_resolve:
        return resolved

    # 分岐を最小化するため、候補数の最も少ないパッケージを選択
    candidate_info = []  # (pkg, candidates) のリスト
    for pkg in to_resolve:
        try:
            cand = allowed_versions(pkg, constraints_map)
        except ValueError as e:
            # パッケージが存在しない場合
            raise
        if not cand:
            # 競合: このパッケージの制約を満たすバージョンがない
            # 読みやすい制約文字列を構築
            cons = constraints_map.get(pkg, [])
            cons_str = ", ".join([(op + v) if op else "any" for (op, v) in cons])
            raise ValueError(f"パッケージ '{pkg}' のいかなるバージョンも次の制約を満たしません: {cons_str}")
        candidate_info.append((pkg, cand))

    # 候補数で昇順にソート
    candidate_info.sort(key=lambda x: len(x[1]))
    pkg, candidates = candidate_info[0]

    # 各候補を試す（既に最新順）
    for ver in candidates:
        new_resolved = dict(resolved)
        new_resolved[pkg] = ver

        # 次のレベルのために制約をクローン
        new_constraints = copy.deepcopy(constraints_map)

        # pkg=ver を設定したとき、pkg に対する既存の制約が満たされていることを確認する必要がある
        if not satisfies_all(ver, new_constraints.get(pkg, [])):
            # 候補はフィルタ済みなので起こらないはずだが、念のためチェック
            continue

        # その依存関係を制約に追加
        deps = package_index[pkg].get(ver, [])
        conflict = False
        conflict_msg = None
        for dep_req in deps:
            dep_name, dep_op, dep_ver = parse_requirement(dep_req)
            if dep_name not in package_index:
                conflict = True
                conflict_msg = f"'{pkg}=={ver}' は存在しないパッケージ '{dep_name}' を必要とします"
                break
            add_constraint(new_constraints, dep_name, dep_op, dep_ver)
            # もし dep が既に解決済みなら、一貫性を確認
            if dep_name in new_resolved:
                assigned = new_resolved[dep_name]
                if not satisfies_all(assigned, new_constraints.get(dep_name, [])):
                    conflict = True
                    conflict_msg = (f"競合: {pkg}=={ver} は {dep_req} を必要としますが、既に解決された {dep_name}=={assigned} と互換性がありません")
                    break
        if conflict:
            # 次の候補を試す
            continue

        # また、これらの制約を追加することで未解決の他のパッケージが候補ゼロになる可能性がある
        # それは再帰呼び出しで allowed_versions を計算する際に検出され、例外が発生します。
        try:
            result = search(new_resolved, new_constraints)
            return result
        except ValueError as e:
            # 次の候補を試す
            last_err = e
            continue

    # すべての候補が失敗した場合は競合を送出します。情報的なメッセージを提供するようにする。
    # pkg に対する制約の説明を作る
    cons = constraints_map.get(pkg, [])
    cons_str = ", ".join([(op + v) if op else "any" for (op, v) in cons])
    raise ValueError(f"制約 {cons_str} の下でパッケージ '{pkg}' を解決できません")

# 探索を開始
resolved = {}
result = search(resolved, constraints)
return result

Example usage (uncomment to run quick test):

if name == 'main':

index = {

"A": {

"1.0.0": ["B<2.0.0"],

"1.1.0": ["B<3.0.0"],

"1.2.0": ["C==1.0.0"]

},

"B": {

"1.5.0": [],

"2.5.0": []

},

"C": {

"1.0.0": ["B>=2.0.0"],

"1.1.0": []

}

}

print(resolve(["A>=1.1.0"], index))

import re
from functools import cmp_to_key

def parse_requirement(req_str):
"""
Parse a requirement string like 'A>=1.2.0', 'B', 'C==1.0.0'
Returns (name, operator, version) where operator and version may be None.
"""
req_str = req_str.strip()
match = re.match(r'^([A-Za-z0-9_-.]+)\s*(==|!=|>=|<=|>|<)\s*([0-9][A-Za-z0-9.-]*)$', req_str)
if match:
return match.group(1), match.group(2), match.group(3)
# No specifier
match2 = re.match(r'^([A-Za-z0-9_-.]+)$', req_str)
if match2:
return match2.group(1), None, None
raise ValueError(f"Cannot parse requirement: {req_str!r}")

def parse_version(version_str):
"""Parse a version string into a tuple of integers for comparison."""
parts = []
for part in version_str.split('.'):
try:
parts.append(int(part))
except ValueError:
parts.append(part)
return tuple(parts)

def version_satisfies(version_str, operator, constraint_version_str):
"""Check if version_str satisfies the constraint operator+constraint_version_str."""
if operator is None:
return True
v = parse_version(version_str)
c = parse_version(constraint_version_str)
if operator == '==':
return v == c
elif operator == '!=':
return v != c
elif operator == '>=':
return v >= c
elif operator == '<=':
return v <= c
elif operator == '>':
return v > c
elif operator == '<':
return v < c
return False

def get_sorted_versions(package_name, package_index):
"""Return versions of a package sorted from latest to oldest."""
if package_name not in package_index:
return []
versions = list(package_index[package_name].keys())
versions.sort(key=lambda v: parse_version(v), reverse=True)
return versions

def resolve(requirements, package_index):
"""
Resolve package dependencies.

Args:
    requirements: List of requirement strings (e.g., ["A>=1.2.0", "B"])
    package_index: Dict mapping package names to dicts of version->dependencies

Returns:
    Dict mapping package names to resolved version strings.

Raises:
    ValueError: If no valid resolution exists.
"""

# We'll use a backtracking approach.
# State: a dict of {package_name: resolved_version}
# We maintain a queue of requirements to process.

def backtrack(resolved, pending_requirements, visited_states=None):
    """
    resolved: dict of {pkg_name: version_str} - already resolved packages
    pending_requirements: list of (name, operator, version) tuples to satisfy
    
    Returns resolved dict or raises ValueError.
    """
    if visited_states is None:
        visited_states = set()
    
    # Deduplicate and check pending requirements
    if not pending_requirements:
        return resolved
    
    # Take the first pending requirement
    name, op, ver = pending_requirements[0]
    rest = pending_requirements[1:]
    
    # Check if already resolved
    if name in resolved:
        # Verify the resolved version satisfies this constraint
        if version_satisfies(resolved[name], op, ver):
            return backtrack(resolved, rest, visited_states)
        else:
            # Conflict with already resolved version
            raise ValueError(
                f"Conflict: {name}=={resolved[name]} does not satisfy {name}{op or ''}{ver or ''}"
            )
    
    # Package not yet resolved - try versions from latest to oldest
    if name not in package_index:
        raise ValueError(f"Package {name!r} not found in package index")
    
    sorted_versions = get_sorted_versions(name, package_index)
    
    # Filter versions that satisfy the current constraint
    candidate_versions = [
        v for v in sorted_versions
        if version_satisfies(v, op, ver)
    ]
    
    if not candidate_versions:
        raise ValueError(
            f"No version of {name} satisfies constraint {name}{op or ''}{ver or ''}"
        )
    
    # Also filter against all other pending requirements for the same package
    # Collect all constraints for this package from pending_requirements
    same_pkg_constraints = [(n2, o2, v2) for n2, o2, v2 in rest if n2 == name]
    
    # Filter candidates against all known constraints for this package
    filtered_candidates = []
    for v in candidate_versions:
        if all(version_satisfies(v, o2, v2) for n2, o2, v2 in same_pkg_constraints):
            filtered_candidates.append(v)
    
    if not filtered_candidates:
        raise ValueError(
            f"No version of {name} satisfies all constraints: "
            f"{[(name + (o2 or '') + (v2 or '')) for _, o2, v2 in same_pkg_constraints + [(name, op, ver)]]}"
        )
    
    # Remove same-package constraints from rest since we'll handle them now
    rest_without_same = [(n2, o2, v2) for n2, o2, v2 in rest if n2 != name]
    
    last_error = None
    for candidate in filtered_candidates:
        # Try this candidate version
        new_resolved = dict(resolved)
        new_resolved[name] = candidate
        
        # Get dependencies of this version
        deps = package_index[name][candidate]
        new_pending = []
        for dep_str in deps:
            dep_name, dep_op, dep_ver = parse_requirement(dep_str)
            new_pending.append((dep_name, dep_op, dep_ver))
        
        # Add remaining requirements
        new_pending.extend(rest_without_same)
        
        try:
            result = backtrack(new_resolved, new_pending, visited_states)
            return result
        except ValueError as e:
            last_error = e
            continue
    
    if last_error:
        raise ValueError(
            f"Could not resolve {name}: tried all candidates. Last error: {last_error}"
        )
    raise ValueError(f"Could not resolve {name}: no candidates available")

# Parse initial requirements
parsed_reqs = []
for req_str in requirements:
    name, op, ver = parse_requirement(req_str)
    parsed_reqs.append((name, op, ver))

return backtrack({}, parsed_reqs)

Example usage and testing

if name == 'main':
package_index = {
"A": {
"1.0.0": ["B<2.0.0"],
"1.1.0": ["B<3.0.0"],
"1.2.0": ["C==1.0.0"]
},
"B": {
"1.5.0": [],
"2.5.0": []
},
"C": {
"1.0.0": ["B>=2.0.0"],
"1.1.0": []
}
}

# Test 1: A>=1.1.0 should resolve to A=1.2.0, C=1.0.0, B=2.5.0
result = resolve(["A>=1.1.0"], package_index)
print("Test 1:", result)
assert result == {'A': '1.2.0', 'C': '1.0.0', 'B': '2.5.0'}, f"Expected A=1.2.0, C=1.0.0, B=2.5.0, got {result}"

# Test 2: A==1.1.0 should resolve to A=1.1.0, B=2.5.0 (latest B < 3.0.0)
result2 = resolve(["A==1.1.0"], package_index)
print("Test 2:", result2)
assert result2 == {'A': '1.1.0', 'B': '2.5.0'}, f"Expected A=1.1.0, B=2.5.0, got {result2}"

# Test 3: Conflict - A==1.2.0 needs C==1.0.0 which needs B>=2.0.0, but also B<2.0.0
try:
    result3 = resolve(["A==1.2.0", "B<2.0.0"], package_index)
    print("Test 3 (should have failed):", result3)
except ValueError as e:
    print("Test 3 (expected conflict):", e)

print("All tests passed!")