#!/usr/bin/env python

# The gale_shapley implementation is taken from
# https://johnlekberg.com/blog/2020-08-22-stable-matching.html

from collections import deque

# Track the number of total proposals per proposer for order O questions
number_of_proposals = dict()


def pref_to_rank(pref):
    return {a: {b: idx for idx, b in enumerate(a_pref)} for a, a_pref in pref.items()}


def gale_shapley(*, A, B, A_pref, B_pref):
    """Create a stable matching using the
    Gale-Shapley algorithm.

    A -- set[str].
    B -- set[str].
    A_pref -- dict[str, list[str]].
    B_pref -- dict[str, list[str]].

    Output: list of (a, b) pairs.
    """
    B_rank = pref_to_rank(B_pref)
    ask_list = {a: deque(bs) for a, bs in A_pref.items()}
    pair = {}

    remaining_A = set(A)
    while len(remaining_A) > 0:
        a = remaining_A.pop()
        b = ask_list[a].popleft()
        if b not in pair:
            pair[b] = a
            print(f"Matching {a} with {b} (a)")
            number_of_proposals[a] += 1
        else:
            a0 = pair[b]
            b_prefer_a0 = B_rank[b][a0] < B_rank[b][a]
            if b_prefer_a0:
                remaining_A.add(a)
                print(f"{a} is rejected by {b} because {a0} is more preffered (c)")
                number_of_proposals[a] += 1
            else:
                remaining_A.add(a0)
                print(f"Matching {a} with {b}, {a0} is now free (b)")
                number_of_proposals[a] += 1
                pair[b] = a

    return [(a, b) for b, a in pair.items()]


if __name__ == "__main__":

    women = list(range(1, 27))
    men = [chr(x + 65) for x in range(26)]

    n = int(input("n: "))

    men = men[:n]
    # because algorithms are 1 indexed, compromise
    women = ["0"] + women[:n]

    men_pref = dict()
    women_pref = dict()

    # For 1 to n-1, men's preference lists look like
    # Mk = Wk Wk+1 ... Wn-1 W1 W2 ... Wn

    for (cur, m) in enumerate(men, start=1):

        # last man n has the same preference list as n-1
        if cur == n:
            cur = cur - 1

        prefs = list()
        k = cur

        # Wk .. Wn-1
        while k < n:
            prefs.append(women[k])
            k += 1

        # W1 .. Wn-1
        k = 1
        while k < cur:
            prefs.append(women[k])
            k += 1

        # last woman n is always last at everyone's preference list
        prefs.append(women[n])
        men_pref[m] = prefs

    # women's preference list for 1-n-2 look like
    # Wk = Wk+1 Wk

    # n-1 looks like
    # Wn-1 = W1 Wn

    # last women's preference list doesn't matter

    for (cur, w) in enumerate(women, start=-1):

        prefs = list()

        # again, compromise between 1 indexed algorithms and nice code
        if cur == -1:
            continue

        # last woman
        if cur == n - 1:
            k = 0
            while k < n:
                prefs.append(men[k])
                k += 1
                women_pref[w] = prefs
            continue

        # n-1th woman
        if cur == n - 2:
            prefs.append(men[0])
            prefs.append(men[n - 1])

            k = 0

            while k < n:
                if k == n - 1:
                    k += 1
                    continue
                if k == 0:
                    k += 1
                    continue
                prefs.append(men[k])
                k += 1

            women_pref[w] = prefs
            continue

        # rest of the women obey the general rule
        prefs.append(men[cur + 1])
        prefs.append(men[cur])

        # we need n - k more men to fill, they don't matter
        k = 0

        while k < n:
            if k == cur:
                k += 1
                continue
            if k == cur + 1:
                k += 1
                continue
            prefs.append(men[k])
            k += 1

        women_pref[w] = prefs

    print("Men Preference Table")
    for (k,v) in men_pref.items():
        print(f'{k:2}| {" ".join([str(x) for x in v])}')

    print("----")

    print("Women Preference Table")
    for (k,v) in women_pref.items():
        print(f'{k:2}| {" ".join(v)}')

    print("----")

    number_of_proposals = {a: 0 for a in men}

    matchings= gale_shapley(A=men, B=women, A_pref=men_pref, B_pref=women_pref)

    print(f"Final pairings:")

    for (m,w) in matchings:
        print(f"{m} - {w}")

    print()

    total = 0
    for (men, times) in number_of_proposals.items():
        total += times
        print(f"{men} proposed {times} times")

    print(f"total of {total} times with n(n-1) + 1 = {n*(n-1) + 1}")