Magnus Distance

magnus_dist.py

#!/usr/bin/env python3

# We read from stdin a list of lichess games of the format winner loser gameid.
# We calculate the "erdos number", but for people who have defeated magnus.
# We output number of people with a specific magnus number. Uses a BFS.

import fileinput
from collections import defaultdict, deque

# G is a graph. name -> { opponents won }
G = defaultdict(set)
for line in fileinput.input():
    winner, loser, game = line.split()
    G[loser].add(winner)

start = 'DrNykterstein'
counts = defaultdict(int)
seen = set()
q = deque([(start, 0)])
while q:
    name, d = q.popleft()
    counts[d] += 1
    for winner in G[name]:
        if winner not in seen:
            seen.add(winner)
            q.append((winner, d + 1))

for v, count in sorted(counts.items()):
    print(v, count)