import math

teams = [
    "RNG",
    "EDG",
    "FPX",
    "WE",
    "RA",
    "TES",
    "JDG",
    "SN",
    "IG",
    "LNG",
    "BLG",
    "V5",
    "LGD",
    "TT",
    "OMG",
    "ES",
    "RW"
]

"""
We first list a number of game histories
"""
matches = [
    ("TES", "SN", 0, 2),
    ("OMG", "EDG", 1, 2),
    ("WE", "RW", 2, 0),
    ("JDG", "IG", 0, 2),

    ("BLG", "ES", 2, 1),
    ("TT", "RNG", 0, 2),
    ("OMG", "FPX", 0, 2),
    ("RW", "TES", 2, 1),
    ("WE", "V5", 2, 1),
    ("LNG", "IG", 2, 0),
    ("JDG", "BLG", 2, 0),
    ("RNG", "SN", 2, 1),
    ("RW", "ES", 0, 2),
    ("TES", "RA", 2, 0),
    ("V5", "LGD", 2, 1),
    ("EDG", "FPX", 2, 1),
    ("LNG", "TT", 2, 1),
    ("WE", "IG", 2, 1),

    ("OMG", "ES", 1, 2),
    ("BLG", "V5", 1, 2),
    ("RW", "FPX", 0, 2),
    ("EDG", "LGD", 2, 0),
    ("IG", "ES", 2, 0),
    ("SN", "RA", 0, 2),
    ("TT", "WE", 0, 2),
    ("OMG", "RNG", 0, 2),
    ("RA", "BLG", 0, 2),
    ("EDG", "JDG", 2, 0),
    ("TES", "LGD", 2, 0),
    ("FPX", "SN", 2, 0),
    ("RW", "V5", 0, 2),
    ("LNG", "WE", 0, 2),

    ("EDG", "TT", 2, 0),
    ("JDG", "RA", 2, 0),
    ("RNG", "V5", 2, 1),
    ("LNG", "BLG", 2, 1),
    ("ES", "FPX", 0, 2),
    ("IG", "RW", 2, 0),
    ("LGD", "BLG", 0, 2),
    ("OMG", "SN", 0, 2),
    ("ES", "LNG", 0, 2),
    ("WE", "RNG", 0, 2),
    ("TT", "V5", 2, 0),
    ("IG", "FPX", 0, 2),
    ("RA", "RW", 2, 0),
    ("TES", "JDG", 2, 0),

    ("SN", "LGD", 2, 0),
    ("BLG", "RNG", 2, 1),
    ("RA", "WE", 2, 0),
    ("V5", "EDG", 0, 2),
    ("ES", "TT", 1, 2),
    ("JDG", "RW", 2, 0),
    ("IG", "OMG", 2, 0),
    ("FPX", "LNG", 2, 0),
    ("LGD", "TT", 2, 0),
    ("EDG", "SN", 2, 0),
    ("BLG", "OMG", 1, 2),
    ("JDG", "WE", 2, 0),
    ("FPX", "TES", 2, 0),
    ("LNG", "RA", 0, 2),
    ("V5", "ES", 2, 1),
    ("IG", "RNG", 1, 2),

    ("SN", "JDG", 0, 2),
    ("FPX", "WE", 0, 2),
    ("BLG", "EDG", 0, 2),
    ("TES", "LNG", 2, 0),
    ("TT", "RA", 1, 2),
    ("WE", "ES", 2, 0),
    ("OMG", "V5", 0, 2),
    ("RW", "RNG", 0, 2),
    ("JDG", "TT", 2, 1),
    ("IG", "EDG", 2, 0),
    ("LGD", "RW", 2, 1),
    ("ES", "TES", 0, 2),
    ("RNG", "FPX", 2, 0),
    ("V5", "LNG", 0, 2),
    ("RA", "OMG", 2, 1),
    ("SN", "IG", 2, 0),

    ("RW", "EDG", 0, 2),
    ("FPX", "JDG", 2, 0),
    ("SN", "TT", 2, 0),
    ("BLG", "IG", 0, 2),
    ("ES", "RA", 0, 2),
    ("LGD", "WE", 0, 2),
    ("RNG", "LNG", 2, 0),
    ("OMG", "TES", 0, 2),
    ("ES", "JDG", 0, 2),
    ("V5", "SN", 0, 2),
    ("LNG", "LGD", 2, 1),
    ("FPX", "RA", 1, 2),
    ("RNG", "EDG", 2, 1),
    ("RW", "OMG", 0, 2),
    ("TT", "BLG", 0, 2),
    ("IG", "TES", 1, 2),

    ("V5", "JDG", 0, 2),
    ("RNG", "ES", 2, 0),
    ("FPX", "LGD", 2, 0),
    ("TES", "BLG", 2, 0),
    ("RA", "V5", 2, 0),
    ("SN", "RW", 2, 0),
    ("WE", "OMG", 2, 1),
    ("EDG", "LNG", 2, 0),
    ("ES", "LGD", 0, 2),
    ("FPX", "TT", 2, 1),
]

team_dict = {}
match_matrix = []
for idx, name in enumerate(teams):
    team_dict[name] = idx
    match_matrix.append([])

team_fac = [0] * len(teams)
team_cnt = [0] * len(teams)


def smooth_naive(team, weight):
    return weight


def smooth_exp(team, weight):
    N = 5
    return math.exp(-team_cnt[team]/N) * weight


def smooth_normal(team, weight):
    N = 5
    return math.exp(-((team_cnt[team]/N)**2)) * weight


def smooth_shock(team, weight):
    N = 5
    if team_cnt[team] < N:
        return weight
    else:
        return 0


def score_naive(a, b):
    return a


def score_fivefive(a, b):
    return 1 if a > 0 else 0


def score_avg(a, b):
    total = a + b
    return a / total


def score_takeall(a, b):
    return 1 if a > b else 0


# choose a smoothing function (naive, exp, normal, shock)
smooth_func = smooth_naive

# choose a score function (naive, fivefive, avgscore, takeall)
score_func = score_naive

for match in reversed(matches):
    l = team_dict[match[0]]
    r = team_dict[match[1]]

    # Normalize each match
    w = smooth_func(r, score_func(match[2], match[3]))
    team_fac[r] += w
    match_matrix[l].append([r, w])

    w = smooth_func(l, score_func(match[3], match[2]))
    team_fac[l] += w
    match_matrix[r].append([l, w])
    team_cnt[l] += 1
    team_cnt[r] += 1

total = 0
for fac in team_fac:
    total += fac

total = total/len(teams)

for matches in match_matrix:
    for m in matches:
        m[1] /= team_fac[m[0]]

# page rank damping factor
d = 0.85

rank = [1] * len(teams)

# iterations
for it in range(100):
    new_rank = [1 - d] * len(teams)
    for (idx, matches) in enumerate(match_matrix):
        for m in matches:
            new_rank[idx] = new_rank[idx] + d * rank[m[0]] * m[1]
    rank = new_rank

team_rank = []
for idx, name in enumerate(teams):
    team_rank.append((name, rank[idx]))

team_rank.sort(key=lambda x: x[1], reverse=True)

# Tier list using K-means
K = 4
rank_name = ["S", "A", "B", "C", "D", "E", "F"]
means = [0] * K
for i in range(K):
    means[i] = team_rank[i * len(teams)//K][1]

for i in range(1000):
    # calculate distance
    cnt = [0] * K
    tot = [0] * K
    for rank in team_rank:
        bidx = 0
        dist = 10000
        for idx, m in enumerate(means):
            if abs(m - rank[1]) < dist:
                bidx = idx
                dist = abs(m - rank[1])
        cnt[bidx] += 1
        tot[bidx] += rank[1]
    for k in range(K):
        means[k] = tot[k] / cnt[k]

print("Result of team ranking using", smooth_func.__name__, score_func.__name__)
for idx, m in enumerate(means):
    print("\t", rank_name[idx], m)

for rank in team_rank:
    bidx = 0
    dist = 10000
    for idx, m in enumerate(means):
        if abs(m - rank[1]) < dist:
            bidx = idx
            dist = abs(m - rank[1])
    print(rank_name[bidx], rank)