Produce the name git describe gives a commit.
What to build
A program that describes commits relative to the nearest reachable tag.
Requirements
- A tag is a candidate for commit X if its commit is reachable from X. Its distance is the number of commits reachable from X but not from the tag's commit. Choose the smallest distance; on a tie, the highest version (semantic versioning as in the earlier exercise).
- Print
TAGif the distance is 0, elseTAG-N-gIDwith the first 7 characters of X's id; printfatal: No names found, cannot describe Xif no tag is reachable.
Input
Line 1: c. Then c lines ID PARENT…. Then t and t lines TAG ID. Then q and q commit ids.
Output
q lines.
Constraints
c ≤ 1,000; t ≤ 50.
Example
Input:
4
a1a1a1a1a1
b2b2b2b2b2 a1a1a1a1a1
c3c3c3c3c3 b2b2b2b2b2
d4d4d4d4d4 c3c3c3c3c3
1
v1.0.0 b2b2b2b2b2
3
d4d4d4d4d4
b2b2b2b2b2
a1a1a1a1a1
Output:
v1.0.0-2-gd4d4d4d
v1.0.0
fatal: No names found, cannot describe a1a1a1a1a1
Why it works
The distance counts the commits made since a tag that are part of X's history, so the nearest tag plus that count and the id pinpoints X in human terms.
Examples
Example 1 · Input
4 a1a1a1a1a1 b2b2b2b2b2 a1a1a1a1a1 c3c3c3c3c3 b2b2b2b2b2 d4d4d4d4d4 c3c3c3c3c3 1 v1.0.0 b2b2b2b2b2 3 d4d4d4d4d4 b2b2b2b2b2 a1a1a1a1a1
Expected output
v1.0.0-2-gd4d4d4d v1.0.0 fatal: No names found, cannot describe a1a1a1a1a1
Example 2 · Input
3 aaaaaaaaaa bbbbbbbbbb aaaaaaaaaa cccccccccc bbbbbbbbbb 2 v1.0.0 aaaaaaaaaa v1.1.0 bbbbbbbbbb 1 cccccccccc
Expected output
v1.1.0-1-gccccccc
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
For each tag, count the commits reachable from the target but not from the tagged commit.
Hint 2
Only tags whose commit is reachable from the target count; choose the smallest count, then the newest tag by version.
Solution
Show one correct solution (try it yourself first)
parents = {}
for _ in range(int(input())):
oid, *ps = input().split()
parents[oid] = ps
tags = [input().split() for _ in range(int(input()))]
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
def version(tag):
core, _, pre = tag.lstrip("v").partition("-")
numbers = tuple(int(x) for x in core.split("."))
parts = tuple((0, int(p), "") if p.isdigit() else (1, 0, p) for p in pre.split(".")) if pre else ()
return numbers + ((0, parts) if pre else (1, ()))
for _ in range(int(input())):
x = input().strip()
history = reachable(x)
candidates = [(len(history - reachable(oid)), tag) for tag, oid in tags if oid in history]
if not candidates:
print(f"fatal: No names found, cannot describe {x}")
continue
distance = min(d for d, _ in candidates)
best = max((t for d, t in candidates if d == distance), key=version)
print(best if distance == 0 else f"{best}-{distance}-g{x[:7]}")