Compute what git merge-base --all prints.
What to build
A program that finds the best common ancestors of two commits.
Requirements
- A common ancestor is reachable from both commits (a commit is reachable from itself). The best common ancestors are those that are not proper ancestors of any other common ancestor.
- For each query print the best common ancestors sorted and separated by spaces, or
noneif the histories are unrelated.
Input
Line 1: c. Then c lines ID PARENT…. Then q and q lines X Y.
Output
q lines.
Constraints
c ≤ 500; q ≤ 50.
Example
Input:
5
a
b a
c b
f b
g f
2
c g
g b
Output:
b
b
Why it works
The best common ancestor is the latest point both histories share, which is exactly what a three-way merge must compare both sides against.
Examples
Example 1 · Input
5 a b a c b f b g f 2 c g g b
Expected output
b b
Example 2 · Input
2 x y 1 x y
Expected output
none
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Find the common ancestors: commits reachable from both tips.
Hint 2
Keep only those that are not an ancestor of another common ancestor; there can be more than one.
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())):
x, y = input().split()
common = reachable(x) & reachable(y)
best = sorted(c for c in common if not any(c != o and c in reachable(o) for o in common))
print(" ".join(best) if best else "none")