Evaluate a Variable from Chained Assignments with +/- Expressions and Cycle Detection

Given a set of assignments and a target variable, return the value of the target. For example, with the target `T1` and the assignments ```text T1 = T2 T2 = 5 ``` the answer is `5`. The problem is then extended twice. ### Clarifying Questions - What is the input format: a list of strings such as `T1 = T2`? Is whitespace around `=` and operators optional? - Are all values integers, and can a literal be negative? - Can a variable be assigned more than once, and if so, which assignment wins? - What should happen when the target, or a variable it depends on, is never assigned? ### Part 1 — Follow a chain of assignments Each right-hand side is either an integer literal or a single variable name. Return the value of the target. ```hint Follow the references Each variable points at a number or at exactly one other variable. Think about the lookup structure, and about what resolving the same variable a second time should cost. ``` #### What This Part Should Cover - Parsing the assignments into a lookup structure. - Resolving a chain of references down to a value, with memoization for repeated lookups. - Behavior for a variable that is never assigned. ### Part 2 — Expressions with + and - A right-hand side can now be an expression that combines variables and integers with `+` and `-`, for example: ```text T1 = T2 + 3 - T3 T2 = 5 T3 = T2 - 1 ``` Here `T1` evaluates to `4`. ```hint Tokens before arithmetic Split each right-hand side into operands and signs before evaluating anything; the value of a variable is then built from the values of its operands. ``` #### Clarifying Questions for this Part - Can an expression start with a sign, as in `T1 = -T2`, or contain two operators in a row? - Can expressions contain parentheses or other operators? #### What This Part Should Cover - A tokenizer that tolerates missing whitespace (`T2+3`) and rejects malformed expressions (`T2 3`, `T2 +`). - Evaluating a variable as a signed sum of its operands, without recomputing shared dependencies. - Complexity in terms of the number of variables and the total length of the expressions. ### Part 3 — Cycles The assignments may now contain a cycle, for example: ```text A = B + 1 B = C C = A - 2 ``` Detect cycles instead of looping forever. ```hint Visited is not enough A variable can legitimately be reached twice through different paths. What extra state tells a shared dependency apart from a loop back to a variable that is still being resolved? ``` #### Clarifying Questions for this Part - When a cycle exists, should the evaluation fail only if the target depends on the cycle, or should the whole input be rejected? - Should the error name the variables that form the cycle? #### What This Part Should Cover - Distinguishing a real cycle from a variable reached twice through different paths. - The scope of the check (only what the target depends on, or the whole input) and a useful error report. - Stack depth on very long chains of assignments. ### What a Strong Answer Covers - A parser with clear errors for malformed assignments and expressions, duplicate assignments and undefined variables. - Memoized resolution so each variable is evaluated at most once, with running time linear in the size of the input. - Cycle detection that never flags a shared dependency, and that reports the variables on the cycle. - Awareness of recursion limits and of an iterative or topological-order alternative. - Tests for each Part: chains, shared dependencies, unary signs, self-reference, and cycles that the target does or does not reach. ### Follow-up Questions - If assignments change one at a time and the target is queried after each change, how would you avoid re-evaluating everything? - How would you add multiplication and parentheses? - How would you evaluate every variable at once and list all variables that are on, or depend on, a cycle? - How would you handle values that overflow a 64-bit integer in a language without arbitrary-precision integers?