Last active
January 12, 2024 07:52
-
-
Save Shiina18/14c1b3e46d0e81f14c8a63c6ee0ded54 to your computer and use it in GitHub Desktop.
Swiss system round calculator. Assume no draw, win prob 50%. List all possible results.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import collections | |
import itertools | |
Distribution = dict[tuple[int, int], int] # {(#wins, #loss): #players} | |
State = tuple[float, Distribution] # (prob, dist) | |
def sum_counter(counters): | |
s = collections.Counter() | |
for c in counters: | |
s += c | |
return s | |
def generate_dist(state: State, num_rounds_left: int) -> list[State]: | |
prob, dist = state | |
if num_rounds_left == 0: | |
return [(prob, {k: v for k, v in dist.items() if k[1] < 3})] | |
buckets = sorted( | |
([record, num] for record, num in dist.items()), | |
key=lambda x: x[0][0], reverse=True, | |
) # order by #wins desc | |
matches_in_buckets = [] | |
matches_between_buckets = [] | |
for i, bucket in enumerate(buckets): | |
record, num = bucket | |
if num % 2 == 0: | |
matches_in_buckets.append(bucket) | |
else: | |
matches_in_buckets.append([record, num - 1]) | |
matches_between_buckets.append([record, buckets[i + 1][0]]) | |
buckets[i + 1][1] -= 1 | |
base_counter = collections.Counter() | |
for bucket in matches_in_buckets: | |
(win, loss), num = bucket | |
base_counter += collections.Counter( | |
{ | |
(win + 1, loss): num // 2, | |
(win, loss + 1): num // 2, | |
} | |
) | |
candidates = [ | |
[ | |
collections.Counter({(win_a + 1, loss_a): 1}) | |
+ collections.Counter({(win_b, loss_b + 1): 1}), | |
collections.Counter({(win_a, loss_a + 1): 1}) | |
+ collections.Counter({(win_b + 1, loss_b): 1}), | |
] | |
for (win_a, loss_a), (win_b, loss_b) in matches_between_buckets | |
] | |
combinations = list(itertools.product(*candidates)) | |
additional_counters = [sum_counter(counters) for counters in combinations] | |
final_dists = [] | |
for additional_counter in additional_counters: | |
final_dists += generate_dist( | |
(prob / len(additional_counters), dict(base_counter + additional_counter)), | |
num_rounds_left - 1, | |
) | |
return final_dists | |
def sort_in_dict(dist): | |
return dict(sorted(dist.items(), key=lambda item: item[0][0], reverse=True)) | |
def f(num_players, num_rounds): | |
if num_players % 2: | |
num_players += 1 | |
dist = {(0, 0): num_players} | |
num_rounds = num_rounds | |
states = generate_dist((1, dist), num_rounds) | |
states = [(p, sort_in_dict(d)) for p, d in states] | |
states = sorted(states, key=lambda s: tuple(s[1].values()), reverse=True) | |
counter = collections.Counter() | |
for p, d in states: | |
counter += collections.Counter( | |
{sum(num for (win, loss), num in d.items() if loss <= 1): p} | |
) | |
print(sorted(counter.items(), key=lambda x: x[0])) | |
count_dict = {} | |
for p, item in states: | |
key = tuple(item.items()) | |
count_dict[key] = count_dict.get(key, 0) + p | |
for key, prob in count_dict.items(): | |
print(f"{prob}\t{dict(key)}") | |
# print twice | |
print(sorted(counter.items(), key=lambda x: x[0])) | |
f(num_players=41, num_rounds=5) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment