Git: A line-by-line three-way merge

Produce a merged file with conflict markers, the way Git does when lines correspond.

What to build

A program that merges three versions of a file line by line and writes conflict markers where both sides changed a line differently.

Requirements

  • The three versions have the same number of lines, which correspond one to one. For each line: if ours equals theirs or theirs equals base, use ours; else if ours equals base, use theirs; otherwise the line conflicts. Consecutive conflicting lines form one block, written as <<<<<<< ours, the ours lines, =======, the theirs lines, >>>>>>> theirs.
  • Print the merged file, then conflicts: N.

Input

Line 1: n. Then n base lines, n ours lines and n theirs lines.

Output

The merged lines, then the count.

Constraints

n ≤ 1,000.

Example

Input:

3
a
b
c
a
B1
c
a
B2
c

Output:

a
<<<<<<< ours
B1
=======
B2
>>>>>>> theirs
c
conflicts: 1

Why it works

Comparing each line with the base shows who changed it, so only lines changed differently by both sides need markers, and grouping neighbours keeps related edits together.

Examples

Example 1 · Input
3
a
b
c
a
B1
c
a
B2
c
Expected output
a
<<<<<<< ours
B1
=======
B2
>>>>>>> theirs
c
conflicts: 1
Example 2 · Input
2
x
y
x2
y
x
y2
Expected output
x2
y2
conflicts: 0

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

For each line position compare base, ours and theirs: the same rules as for whole files.

Hint 2

Collect consecutive conflicting positions into one block, and close the block when a non-conflicting line arrives or the file ends.

Solution

Show one correct solution (try it yourself first)
n = int(input())
base = [input() for _ in range(n)]
ours = [input() for _ in range(n)]
theirs = [input() for _ in range(n)]
out, block, conflicts = [], None, 0


def close():
    global block, conflicts
    if block is not None:
        out.extend(["<<<<<<< ours", *block[0], "=======", *block[1], ">>>>>>> theirs"])
        conflicts += 1
        block = None


for b, o, t in zip(base, ours, theirs):
    if o == t or t == b:
        close()
        out.append(o)
    elif o == b:
        close()
        out.append(t)
    else:
        if block is None:
            block = ([], [])
        block[0].append(o)
        block[1].append(t)
close()
for line in out:
    print(line)
print("conflicts:", conflicts)

Lesson: Resolving merge conflicts →