Predict what git merge will do before running it.
What to build
A program that decides whether merging a branch is already up to date, a fast-forward or a true merge.
Requirements
- For each query
OURS THEIRS(two commit ids), printAlready up to date.if THEIRS is reachable from OURS, elseFast-forwardif OURS is reachable from THEIRS, elseMerge made by the 'ort' strategy.
Input
Line 1: c. Then c lines ID PARENT…. Then q and q lines OURS THEIRS.
Output
q lines.
Constraints
c ≤ 1,000; q ≤ 100.
Example
Input:
4
a
b a
c b
f b
3
b c
c f
c b
Output:
Fast-forward
Merge made by the 'ort' strategy.
Already up to date.
Why it works
If the other side has nothing new, there is nothing to do; if our side has nothing new, our branch can jump to theirs; only when both have new work is a merge commit needed.
Examples
Example 1 · Input
4 a b a c b f b 3 b c c f c b
Expected output
Fast-forward Merge made by the 'ort' strategy. Already up to date.
Example 2 · Input
1 a 1 a a
Expected output
Already up to date.
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Compute the set of commits reachable from each tip.
Hint 2
Check "already up to date" first: the other tip is reachable from ours (including equal).
Solution
Show one correct solution (try it yourself first)
parents = {}
for _ in range(int(input())):
oid, *ps = input().split()
parents[oid] = ps
def reachable(tip):
seen, stack = set(), [tip]
while stack:
oid = stack.pop()
if oid not in seen:
seen.add(oid)
stack.extend(parents[oid])
return seen
for _ in range(int(input())):
ours, theirs = input().split()
if theirs in reachable(ours):
print("Already up to date.")
elif ours in reachable(theirs):
print("Fast-forward")
else:
print("Merge made by the 'ort' strategy.")