Git: Sort version tags

Put release tags in the right order.

What to build

A program that sorts semantic version tags from oldest to newest.

Requirements

  • Tags look like vMAJOR.MINOR.PATCH with an optional -PRERELEASE (dot-separated parts). Compare MAJOR, MINOR and PATCH numerically. A pre-release comes before the same version without one. Pre-release parts are compared in order: numbers numerically, words alphabetically, a number before a word, and a shorter list before a longer one when all its parts are equal.
  • Print the tags, oldest first, one per line.

Input

Line 1: n. Then n distinct tags.

Output

n lines.

Constraints

n ≤ 200.

Example

Input:

4
v1.10.0
v1.2.0
v1.9.3
v1.2.1

Output:

v1.2.0
v1.2.1
v1.9.3
v1.10.0

Why it works

Version numbers are counts, not text, so each part must be compared as a number, and a pre-release is a step on the way to its final version.

Examples

Example 1 · Input
4
v1.10.0
v1.2.0
v1.9.3
v1.2.1
Expected output
v1.2.0
v1.2.1
v1.9.3
v1.10.0
Example 2 · Input
3
v2.0.0
v2.0.0-rc.1
v1.9.0
Expected output
v1.9.0
v2.0.0-rc.1
v2.0.0

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Split off the leading v, then split the core at dots and compare the numbers as integers.

Hint 2

A version without a pre-release is greater than the same version with one; compare pre-release parts one by one.

Solution

Show one correct solution (try it yourself first)
def key(tag):
    core, _, pre = tag.lstrip("v").partition("-")
    numbers = tuple(int(x) for x in core.split("."))
    if not pre:
        return numbers + (1, ())
    parts = tuple((0, int(p), "") if p.isdigit() else (1, 0, p) for p in pre.split("."))
    return numbers + (0, parts)


tags = [input().strip() for _ in range(int(input()))]
for tag in sorted(tags, key=key):
    print(tag)

Lesson: Stashing work and tagging releases →