Git: The shortest unique abbreviation

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 ABBREVIATION for 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])

Lesson: Inside Git: objects and hashes →