You are given a small DSL (domain-specific language) consisting of variable assignments, one per line. Each line has the form: ```text <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): ```text 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: ```text foo = bar + 5 bar = 2 ``` - Expected output (order not important): ```json { "bar": 2, "foo": 7 } ``` 2. **Multi-level dependencies** - Variables can depend on other variables which themselves depend on more variables: ```text foo = bar + 1 bar = baz + 1 baz = 3 ``` - Expected output: ```json { "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: ```text 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: ```text 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: ```text 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.