Resolve Dependent Addition Equations

Problem Statement

You are building a configuration and calculation engine for an autonomous vehicle simulation pipeline. The engine configures vehicle parameters using a list of dependency-based assignment equations.

Each equation defines a target variable as a sum of one or more terms separated by +. Each term is either:

• A 64-bit integer literal (e.g., 5, -12).
• A variable name (alphanumeric identifier).

Write a function that parses and evaluates all equations, returning a dictionary mapping each variable name to its resolved integer value.

If any invalid condition is detected, the function must raise an appropriate custom exception:

• UndefinedVariableError: Raised when an equation references a variable that is never defined on the left-hand side of any equation.
• CycleError: Raised when there is a circular dependency (e.g., A = B + 1 and B = A).
• DuplicateDefinitionError: Raised if a variable is defined on the left-hand side more than once.

Function Signature

class UndefinedVariableError(Exception):
    pass

class CycleError(Exception):
    pass

class DuplicateDefinitionError(Exception):
    pass

def evaluate_equations(equations: list[str]) -> dict[str, int]:
    pass

Input Format

• equations: A list of strings, each in the form " = + + ... + ".
• Tokens are separated by whitespace. Variable names consist of letters, digits, and underscores, and are case-sensitive.

Constraints

• 1 <= len(equations) <= 20,000
• Total number of terms across all equations <= 100,000
• Integer literals fit within a signed 64-bit integer (-2^63 <= val <= 2^63 - 1).
• The algorithm must run in O(V + E) time, where V is the number of unique variables and E is the number of variable references.

Examples

Example 1

equations = [
    "speed = base_speed + offset",
    "base_speed = 30",
    "offset = 5 + 3",
    "max_speed = speed + 10"
]
# Output: {"speed": 38, "base_speed": 30, "offset": 8, "max_speed": 48}

Explanation: offset evaluates to 8, base_speed evaluates to 30, speed resolves to 30 + 8 = 38, and max_speed resolves to 38 + 10 = 48.

Example 2

equations = [
    "x = y + 2",
    "y = z + 1",
    "z = x + 4"
]
# Raises: CycleError

Explanation: x -> y -> z -> x forms a directed cycle.

Example 3

equations = [
    "foo = bar + 10"
]
# Raises: UndefinedVariableError

Explanation: bar is never defined.