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 }
     

2. 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 }
     

3. 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.

4. 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.

5. 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).

6. 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.

7. 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.

Evaluate Variables in a Simple Arithmetic DSL

Hints

1. Parse expressions into signed terms and use DFS with visiting-state cycle detection.