Compute the live range of every value in straight-line code.
What to build
A program that prints the live range of each variable.
Requirements
- Instructions are
x = a,x = a op bandprint a, numbered from 1; operands are names or numbers. Each variable is written at most once, and never after it has been read. - A variable's range starts at the line that writes it (0 for an input) and ends at the last line that reads it (its start if it is never read). Print
NAME: START-ENDfor each variable, sorted by start and then by name.
Input
Line 1: n. Then n instructions.
Output
One line per variable.
Constraints
n ≤ 100.
Example
Input:
4
a = x + 1
b = a * a
c = b - x
print c
Output:
x: 0-3
a: 1-2
b: 2-3
c: 3-4
Why it works
A value occupies storage from the moment it is written until it is read for the last time; outside that range, its register is free.
Examples
Example 1 · Input
4 a = x + 1 b = a * a c = b - x print c
Expected output
x: 0-3 a: 1-2 b: 2-3 c: 3-4
Example 2 · Input
2 t = 5 u = t
Expected output
t: 1-2 u: 2-2
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
An operand that has not been written yet is an input and starts at line 0.
Hint 2
Update a variable's end every time it is read; a variable that is never read ends where it starts.
Solution
Show one correct solution (try it yourself first)
start, end = {}, {}
for k in range(1, int(input()) + 1):
words = input().split()
dest, read = (None, words[1:]) if words[0] == "print" else (words[0], words[2:])
for word in read:
if word.isidentifier():
start.setdefault(word, 0)
end[word] = k
if dest:
start[dest] = k
end.setdefault(dest, k)
for name in sorted(start, key=lambda n: (start[n], n)):
print(f"{name}: {start[name]}-{end[name]}")