Merge two whole snapshots against their merge base, file by file.
What to build
A program that performs a file-level three-way merge and reports conflicts the way Git does.
Requirements
- For each path (sorted): if ours equals theirs, use it; else if ours equals base, take theirs; else if theirs equals base, keep ours; otherwise it is a conflict:
CONFLICT (modify/delete): PATH deleted in ours and modified in theirs(ordeleted in theirs and modified in ours),CONFLICT (add/add): Merge conflict in PATHif it is not in the base, orCONFLICT (content): Merge conflict in PATH. A missing version counts as different from any content. - Print the conflict lines (sorted by path), then
merged:and the merged files aspath=contentseparated by spaces (ormerged: (empty)), thenAutomatic merge failed; fix conflicts and then commit the result.if there were conflicts, elseMerge made by the 'ort' strategy.
Input
Three blocks for base, ours and theirs: a line with k, then k lines path content.
Output
The conflict lines, the merged line and the result line.
Constraints
At most 200 paths; no spaces in paths or contents.
Example
Input:
2
app.py v1
README.md v1
2
app.py v2
README.md v1
2
app.py v1
README.md v2
Output:
merged: README.md=v2 app.py=v2
Merge made by the 'ort' strategy.
Why it works
Comparing each side with the base shows which side made a change, so independent changes combine automatically, and only changes both sides made to the same file need a person.
Examples
2 app.py v1 README.md v1 2 app.py v2 README.md v1 2 app.py v1 README.md v2
merged: README.md=v2 app.py=v2 Merge made by the 'ort' strategy.
1 a v1 1 a v2 1 a v3
CONFLICT (content): Merge conflict in a merged: (empty) Automatic merge failed; fix conflicts and then commit the result.
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
For each path take its versions in base, ours and theirs (missing means deleted or never added).
Hint 2
Same on both sides → use it; only one side changed → take that side; otherwise decide which kind of conflict it is.
Solution
Show one correct solution (try it yourself first)
base = dict(input().split() for _ in range(int(input())))
ours = dict(input().split() for _ in range(int(input())))
theirs = dict(input().split() for _ in range(int(input())))
merged, conflicts = {}, []
for path in sorted(set(base) | set(ours) | set(theirs)):
b, o, t = base.get(path), ours.get(path), theirs.get(path)
if o == t:
chosen = o
elif o == b:
chosen = t
elif t == b:
chosen = o
else:
if o is None:
conflicts.append(f"CONFLICT (modify/delete): {path} deleted in ours and modified in theirs")
elif t is None:
conflicts.append(f"CONFLICT (modify/delete): {path} deleted in theirs and modified in ours")
elif b is None:
conflicts.append(f"CONFLICT (add/add): Merge conflict in {path}")
else:
conflicts.append(f"CONFLICT (content): Merge conflict in {path}")
continue
if chosen is not None:
merged[path] = chosen
for line in conflicts:
print(line)
print("merged: " + (" ".join(f"{p}={c}" for p, c in sorted(merged.items())) or "(empty)"))
print("Automatic merge failed; fix conflicts and then commit the result." if conflicts else "Merge made by the 'ort' strategy.")