| import math
|
| import random
|
| import time
|
|
|
| # make random results consistent between runs
|
| random.seed(42)
|
|
|
|
|
| def generate_players(n_players, min_rank, max_rank):
|
| ndigits = int(math.log10(n_players)) + 1
|
| return [(f"Player{N:0{ndigits}d}", random.randint(min_rank, max_rank)) for N in range(n_players)]
|
|
|
|
|
| def sort_players(player_list):
|
| # the `key` here means we will sort using the rank value
|
| # the result is a list of players from low to high ranks
|
| return sorted(player_list, key=lambda pair: pair[1])
|
|
|
|
|
| def rank_diffs(left, mid, right):
|
| right_diff = abs(right[1] - mid[1])
|
| if left:
|
| left_diff = abs(left[1] - mid[1])
|
| else:
|
| # there is no left player, which we can treat as an infinite distance
|
| left_diff = float('inf')
|
|
|
| return left_diff, right_diff
|
|
|
|
|
| def match_triplet(left, mid, right, max_rank_diff):
|
| left_diff, right_diff = rank_diffs(left, mid, right)
|
|
|
| #
|
| # |---| |---| |---|
|
| # | L | ----- | M | ----- | R |
|
| # |---| | |---| | |---|
|
| # | |
|
| # left_diff right_diff
|
|
|
| if left_diff < right_diff:
|
| lo = left
|
| hi = mid
|
| diff = left_diff
|
| else:
|
| # left_diff >= right_diff
|
| # right player wins the tie when left_diff == right_diff
|
| lo = mid
|
| hi = right
|
| diff = right_diff
|
|
|
| #
|
| # |----| |----|
|
| # | lo | ----- | hi |
|
| # |----| | |----|
|
| # |
|
| # diff
|
|
|
| if diff <= max_rank_diff:
|
| match = (lo, hi)
|
| else:
|
| match = None
|
|
|
| return match, right_diff
|
|
|
|
|
| def match_players(player_list, max_rank_diff=50):
|
| pool = player_list.copy()
|
| matches = []
|
|
|
| while len(pool) >= 2:
|
| right = pool.pop()
|
| mid = pool.pop()
|
|
|
| if pool:
|
| # if there are at least three players in the pool, we need to look
|
| # on either side of the 'middle' player
|
| left = pool.pop()
|
| else:
|
| # we're looking at the last two players in this pool
|
| left = None
|
|
|
| match, right_diff = match_triplet(left, mid, right, max_rank_diff=max_rank_diff)
|
|
|
| if match == (left, mid):
|
| if right_diff <= max_rank_diff:
|
| # right player still might match someone, put them back in the pool
|
| pool.append(right)
|
| else:
|
| matches.append((right, None))
|
| elif left and match == (mid, right) or match is None:
|
| print(f"returning to pool: {left}")
|
| pool.append(left)
|
| else:
|
| # sanity check: (left, right) match shouldn't be possible
|
| raise RuntimeError("Unexpected match")
|
|
|
|
|
| if match:
|
| matches.append(match)
|
| else:
|
| matches.extend([
|
| (mid, None),
|
| (right, None)
|
| ])
|
|
|
| # edge case: catch the case where there is one unmatched player remaining in the pool
|
| if pool:
|
| remainder = pool.pop()
|
| matches.append((remainder, None))
|
|
|
| return matches
|
|
|
|
|
| if __name__ == "__main__":
|
| # N_players = 25
|
| # print(f"generating {N_players} players")
|
| # unsorted_players = generate_players(N_players, min_rank=1000, max_rank=2000)
|
| unsorted_players = [('Player0', 1654), ('Player1', 1114), ('Player2', 1025), ('Player3', 1759), ('Player4', 1281), ('Player5', 1250), ('Player6', 1228), ('Player7', 1142)]
|
| print("unsorted players:")
|
| print(unsorted_players)
|
| print("---\n")
|
|
|
| print("sorting players")
|
| sort_start = time.monotonic()
|
| sorted_players = sort_players(unsorted_players)
|
| sort_stop = time.monotonic()
|
| print("sorted players:")
|
| print(sorted_players)
|
| print("---\n")
|
|
|
| print("creating match pairs")
|
| match_start = time.monotonic()
|
| matches = match_players(sorted_players)
|
| match_stop = time.monotonic()
|
|
|
|
|
| for left_player, right_player in matches:
|
| if right_player is None:
|
| print(f"{left_player!r} is unmatched")
|
| else:
|
| left_rank = left_player[1]
|
| right_rank = right_player[1]
|
| rank_diff = abs(left_rank - right_rank)
|
| print(f"{left_player!r} plays {right_player!r} (rank difference is {rank_diff})")
|
|
|
| print("Match-making time:")
|
| print(f" With sort: {match_stop - sort_start:.3e} sec")
|
| print(f"Without sort: {match_stop - match_start:.3e} sec")
|