Find which version last changed each line, as git blame does.
What to build
A program that blames every line of the last version of a file on the version that introduced it.
Requirements
- Diff consecutive versions with the line diff of the previous exercise (the same table and walk). Kept lines keep their blame; added lines get the number of the version that added them. Versions are numbered from 1.
- Print each line of the last version as
V: line.
Input
Line 1: k. Then k versions, each a line with n followed by n lines.
Output
One line per line of the last version.
Constraints
k ≤ 20; at most 200 lines per version.
Example
Input:
3
2
a
b
3
a
b
c
3
a
x
c
Output:
1: a
3: x
2: c
Why it works
Running the diff along the history carries each surviving line's origin forward, so a line's blame is the version where it was last added or changed.
Examples
3 2 a b 3 a b c 3 a x c
1: a 3: x 2: c
1 1 hello
1: hello
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Start with every line of version 1 blamed on 1; for each next version, diff the previous version with it.
Hint 2
A kept line takes the blame of the old line it matched; an added line is blamed on the new version.
Solution
Show one correct solution (try it yourself first)
def walk(old, new):
n, m = len(old), len(new)
L = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
for j in range(m - 1, -1, -1):
L[i][j] = L[i + 1][j + 1] + 1 if old[i] == new[j] else max(L[i + 1][j], L[i][j + 1])
matches, i, j = {}, 0, 0
while i < n or j < m:
if i < n and j < m and old[i] == new[j]:
matches[j] = i
i, j = i + 1, j + 1
elif j == m or (i < n and L[i + 1][j] >= L[i][j + 1]):
i += 1
else:
j += 1
return matches
versions = []
for _ in range(int(input())):
versions.append([input() for _ in range(int(input()))])
blame = [1] * len(versions[0])
for number in range(2, len(versions) + 1):
old, new = versions[number - 2], versions[number - 1]
matches = walk(old, new)
blame = [blame[matches[j]] if j in matches else number for j in range(len(new))]
for owner, line in zip(blame, versions[-1]):
print(f"{owner}: {line}")