## Resolve Dependent Addition Equations ### Problem Implement `resolveEquations(equations) -> output`. Each input string defines one variable as a sum of nonnegative integer literals and other variables. Definitions may appear in any order, and dependencies may span several equations. An equation has this grammar: ```text identifier = term + term + ... + term ``` An `identifier` begins with an ASCII letter or underscore and then contains only ASCII letters, digits, or underscores. A `term` is either an identifier or a base-10 integer in `[0, 1,000,000,000]`. Whitespace may appear around `=` and `+`. `output` is a homogeneous JSON array of strings. On success, `output[0]` is exactly `"OK"`. For each input equation at index `i`, `output[i + 1]` is `identifier=value`, where `identifier` is that equation's left-hand side and `value` is its resolved nonnegative integer written in canonical base-10 form with no leading zeros except for `0`. This preserves input assignment order and is unambiguous because identifiers cannot contain `=`. If any right-hand-side identifier has no definition, return the one-element array `["Unresolvable equations"]`. If the defined variables contain a dependency cycle, return the one-element array `["Cyclic Dependency"]`. Test inputs will not contain both an undefined reference and a cycle, so these errors do not need a precedence rule. ### Function Contract - `equations` is a JSON array of strings, and `output` is a JSON array of strings. - Every left-hand-side identifier is unique. - A successful output contains exactly `equations.length + 1` strings; an error output contains exactly one string. - Do not mutate the input array. The four language signatures use only a homogeneous string sequence: - Python: `def resolveEquations(equations: list[str]) -> list[str]` - JavaScript: `function resolveEquations(equations)` accepts and returns arrays of strings. - Java: `List<String> resolveEquations(List<String> equations)` - C++: `vector<string> resolveEquations(const vector<string>& equations)` ### Constraints - `1 <= equations.length <= 1,500`. - Let `B` be the byte length of the entire `equations` array serialized as compact UTF-8 JSON: no whitespace outside strings, with brackets, commas, quotes, and required JSON escapes all counted. Equation strings use only the ASCII grammar above. Inputs satisfy `B <= 96,000`. - Every equation has at least one term and follows the stated grammar. - Every successful intermediate and final sum is at most `9,007,199,254,740,991`, so it is exact in signed 64-bit arithmetic and JavaScript integer arithmetic. - Let `R` be the compact UTF-8 JSON byte length of the returned string array under the same counting rule. Inputs guarantee `R <= 96,000`; error outputs are far smaller. Thus the fully serialized input plus result is at most `192,000` bytes. - Target `O(B + R)` time and `O(B + R)` space, including parsing and deterministic output construction. ### Examples ```text equations = ["foo = bar + 5", "bar = 2", "abc = 3"] output = ["OK", "foo=7", "bar=2", "abc=3"] ``` ```text equations = ["g = abc + foo", "foo = bar + 5", "bar = 2", "abc = 3"] output = ["OK", "g=10", "foo=7", "bar=2", "abc=3"] ``` ```text equations = ["foo = bar + 3", "bar = abc + pqr + 2"] output = ["Unresolvable equations"] ``` Neither `abc` nor `pqr` has a definition. ```text equations = ["foo = bar + 3", "bar = foo + 2"] output = ["Cyclic Dependency"] ``` ```hint Separate validation from resolution A name absent from all left-hand definitions is different from a defined variable whose dependencies have not been processed yet. ``` ### Discussion Requirements 1. Explain why evaluating equations only from left to right fails when definitions appear after their uses. 2. Show how undefined references differ from variables that are defined but not yet evaluated. 3. Explain how memoization prevents a shared dependency from being recomputed. 4. State how an iterative traversal can avoid call-stack overflow on a long dependency chain.