Git: Blame each line

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

Example 1 · Input
3
2
a
b
3
a
b
c
3
a
x
c
Expected output
1: a
3: x
2: c
Example 2 · Input
1
1
hello
Expected output
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}")

Lesson: Viewing changes: diff, log and blame →