Shorten object ids the way Git does, without making them ambiguous.
What to build
A program that finds the shortest unique abbreviation of every object id in a list.
Requirements
- An abbreviation is a prefix of at least 4 characters that no other id in the list starts with.
- Print
ID ABBREVIATIONfor each id, in the order given.
Input
Line 1: n. Then n distinct hexadecimal ids of the same length.
Output
n lines.
Constraints
n ≤ 500; ids of 8 to 40 characters.
Example
Input:
3
a1b2c3d4
a1b2ffff
b0000000
Output:
a1b2c3d4 a1b2c
a1b2ffff a1b2f
b0000000 b000
Why it works
An abbreviation identifies an object only if no other object shares it, so the shortest safe length depends on the ids that are present.
Examples
Example 1 · Input
3 a1b2c3d4 a1b2ffff b0000000
Expected output
a1b2c3d4 a1b2c a1b2ffff a1b2f b0000000 b000
Example 2 · Input
1 deadbeef0000
Expected output
deadbeef0000 dead
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
For each id, try prefixes of length 4, 5, 6, … until no other id starts with the prefix.
Hint 2
Comparing with every other id is fine for a few hundred ids.
Solution
Show one correct solution (try it yourself first)
ids = [input().strip() for _ in range(int(input()))]
for oid in ids:
length = 4
while any(other != oid and other.startswith(oid[:length]) for other in ids):
length += 1
print(oid, oid[:length])