# -*- coding: utf-8-unix -*-

def match_marriage(rank_from_b, rank_from_g):
    """Match boys and girls in stable manner"""
    match = {}

    # 女性が指定しなかった男性に与える（最下位の）ランキング値
    rank_end = len(rank_from_g) + 1000

    girls = list(rank_from_g.keys())
    boys  = list(rank_from_b.keys())

    while boys:
        bid = boys.pop(0)

        # 求婚したい先
        favs = rank_from_b[bid]

        # その他の候補も加えたリスト
        favs_and_rest = favs + list(set(girls) - set(favs))

        # 求婚したい順に申し込んでみる
        for gid in favs_and_rest:
            # 現在の仮婚約者（いれば）
            cur = match.get(gid)

            # 未婚約なら仮婚約成立。次の男性のターンへ
            if cur is None:
                match[gid] = bid
                break

            # 仮婚約済なので、女性視点でどちらがいいか比較する
            else:
                # 女性側から見た、現在の仮婚約者と新規求婚者のランク（ランク外の場合は外れ値を使う）
                ranking = rank_from_g[gid]
                rank_cur = ranking.index(cur) if cur in ranking else rank_end
                rank_new = ranking.index(bid) if bid in ranking else rank_end

                # 求婚者のランクが上から、そちらに乗り換える。乗り換えられた男性はやり直しへ
                if rank_new < rank_cur:
                    match[gid] = bid
                    boys.append(cur)
                    break

    return match

def match_hospital(rank_from_r, rank_from_h, nmax_at_h={}):
    """Match residents and hospitals in stable manner"""

    # 各病院の枠を初期化する
    match = dict([(hid, []) for hid in rank_from_h.keys()])

    # 病院から認知されていないレジデントに与える最下位のランキング値
    rank_end = len(rank_from_r) + 1000

    hospitals = list(rank_from_h.keys())
    residents = list(rank_from_r.keys())

    while residents:
        rid = residents.pop(0)

        # 働きたい先
        favs = rank_from_r[rid]

        # その他の候補も加えたリスト
        favs_and_rest = favs + list(set(hospitals) - set(favs))

        # 働きたい順に申し込んでみる
        for hid in favs_and_rest:
            # 現在の空き状況
            status = match[hid]
            ranking = rank_from_h[hid]

            # 応募者を加え、病院側から見た候補者ランキング順にならべ直す
            wanted = sorted(status + [rid], key=lambda rid: ranking.index(rid) if rid in ranking else rank_end)

            # この病院の受け入れ可能人数（デフォルト2名）
            nmax = nmax_at_h.get(hid) or 2

            # 枠が空いていたなら仮編入。次の人のターンへ
            if len(wanted) <= nmax:
                match[hid] = wanted
                break
            # 枠以上に応募があるので、誰かを落とす
            else:
                match[hid] = wanted[0:nmax]

                # 応募者が入れたなら、落ちた人を列に並べ直して次の人のターンへ
                if rid in match[hid]:
                    residents.append(wanted[nmax])
                    break

    return match