Evaluate variables in simple arithmetic DSL

You are given a small DSL (domain-specific language) consisting of variable assignments, one per line. Each line has the form:

<identifier> = <expression>

• <identifier> is a variable name: [a-zA-Z_][a-zA-Z0-9_]*.
• <expression> is a sum or difference of integer literals and variable references.
• Operators supported are + and - only.
• There are no parentheses; evaluation is strictly left-to-right.
• Whitespace may appear anywhere (or not at all) and must be ignored: around =, around operators, before/after identifiers, etc.

All variables are of integer type. A variable may depend on other variables which might be defined before or after it in the input. The dependency graph may contain chains (e.g. a depends on b, which depends on c, …), and you must resolve all such dependencies.

Task

Implement a function with the following behavior (pseudo-signature):

evaluate(program: string) -> Map<string, int>

• program is a multi-line string; each non-empty line is one assignment.
• Return a mapping from variable name to its computed integer value for all variables that can be successfully evaluated.

Requirements & Edge Cases

1. Basic evaluation

• Example input:

foo = bar + 5
bar = 2

• Expected output (order not important):

{ "bar": 2, "foo": 7 }

1. Multi-level dependencies

• Variables can depend on other variables which themselves depend on more variables:

foo = bar + 1
bar = baz + 1
baz = 3

• Expected output:

{ "baz": 3, "bar": 4, "foo": 5 }

1. Whitespace robustness Your parser must handle arbitrary spacing, including no spaces at all:

• These should all be parsed equivalently:

foo=bar+5-baz
foo = bar + 5 - baz
foo = bar + 5 - baz

• Extra spaces around variable names in keys or expressions (e.g. "bar ") must be trimmed so that variable lookup works correctly.

1. Undefined variables

• If an expression references a variable that is never assigned anywhere in the program, then that referencing variable can never be evaluated.
• In this situation, your function should detect undefined variables and fail in a well-defined way (for example, by throwing an exception or returning an error structure). Clearly document your chosen behavior.

1. Cyclic dependencies

• If there is a cycle in the dependency graph:

foo = bar + 1
bar = foo + 1

• Neither foo nor bar can be meaningfully evaluated.
• Your function must detect cyclic dependencies (e.g., via graph-based cycle detection or equivalent) and fail in a well-defined way (e.g., report a cyclic dependency error).

1. Partial evaluability (clarify your choice)

• Some variables may be evaluable even if others are not. For example:

ok = 1
bad = missing + 1

• You may either:
• (a) fail the entire evaluation if any variable is invalid, or
• (b) return values for all variables that can be evaluated and separately report the ones that cannot.
• In your implementation, pick one behavior and document it clearly.

1. Constraints & complexity

• Assume up to N variables and up to M total tokens across all expressions, where N, M can be large.
• Design your algorithm to be efficient in terms of time and space (target around O(N + M) time if possible).

What you need to provide

• Code (in a language of your choice) that implements evaluate(program: string) according to the above rules.
• A brief explanation of:
• How you build and represent the dependency graph.
• How you evaluate variables in the correct order.
• How you detect and handle undefined variables and cyclic dependencies.
• The time and space complexity of your solution.