Git: Walk the history

Produce the history that git log shows, from a commit graph.

What to build

A program that lists the commits reachable from HEAD, newest first, and summarizes the history.

Requirements

  • Each commit has an id, a timestamp, its parent ids and a message. List every commit reachable from HEAD through parent links, sorted by timestamp from newest to oldest (ties: smaller id first), as ID MESSAGE.
  • Then print N commits, M merges, where a merge is a commit with two or more parents, and first-parent line: ID ID … following only first parents from HEAD.

Input

Line 1: c. Then c lines ID TIMESTAMP PARENTS MESSAGE… where PARENTS is - or ids joined by commas. Last line: the HEAD id.

Output

The history lines, then the two summary lines.

Constraints

c ≤ 500.

Example

Input:

3
a1 100 - First
b2 200 a1 Second
c3 300 b2 Third
c3

Output:

c3 Third
b2 Second
a1 First
3 commits, 0 merges
first-parent line: c3 b2 a1

Why it works

History is a graph of parent links, so a search from HEAD finds every commit that led to it, and the first-parent links trace the main line through merges.

Examples

Example 1 · Input
3
a1 100 - First
b2 200 a1 Second
c3 300 b2 Third
c3
Expected output
c3 Third
b2 Second
a1 First
3 commits, 0 merges
first-parent line: c3 b2 a1
Example 2 · Input
5
a 10 - Start
b 20 a Main work
f 15 a Feature work
m 30 b,f Merge feature
x 40 a Other branch
m
Expected output
m Merge feature
b Main work
f Feature work
a Start
4 commits, 1 merges
first-parent line: m b a

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

Hints

Hint 1

Collect every commit reachable from HEAD by following parent links.

Hint 2

Sort them by timestamp, newest first, breaking ties by id; the first parent is the one listed first.

Solution

Show one correct solution (try it yourself first)
commits = {}
for _ in range(int(input())):
    oid, stamp, parents, message = input().split(maxsplit=3)
    commits[oid] = (int(stamp), [] if parents == "-" else parents.split(","), message)
head = input().strip()
seen, stack = set(), [head]
while stack:
    oid = stack.pop()
    if oid not in seen:
        seen.add(oid)
        stack.extend(commits[oid][1])
for oid in sorted(seen, key=lambda o: (-commits[o][0], o)):
    print(oid, commits[oid][2])
merges = sum(1 for o in seen if len(commits[o][1]) >= 2)
print(f"{len(seen)} commits, {merges} merges")
line, oid = [], head
while True:
    line.append(oid)
    if not commits[oid][1]:
        break
    oid = commits[oid][1][0]
print("first-parent line: " + " ".join(line))

Lesson: Inside Git: trees and commits →