How to determine a perfect Settlers of Catan "bracket"
pondo0105
217
Interview

This is an interesting one, because I didn't get in on an interview. Rather my roommate asked me to do this, so - real world consequences!

My roommate wanted to set up a balanced set of Settlers of Catan matches. If you don't know about Catan, all that matters is that its a board game that can be played with 3 or 4 people per game. Here's the breakdown of what he asked:

  1. There would be seven players, and seven matches played
  2. Each player should play in a 4-player game 4 times, and in a 3-player game 3 times.
  3. Each player should face each other player the same number of times

I was able to determine that this should be possible, and even come up with a solution. Unfortunately, I had to brute force it, though I was able to include some optimizations.

My question is, is it there a deterministic algorithm that could solve this problem? What about the general case?

In case you're interested, here's the code that I used. It's a greedy approach that tries to pack the pairs with the least matches played against each other first into the 4-player match, then the 3-player match. I use some RNG weights to break ties, otherwise the outcome will end up unbalanced (I've included the no RNG code as comments, if you want to comment that out and see for yourself). A successful run will yield a set of rounds where every player does play 4 4-player matches and 3 3-player matches, and faces off against each other 3 times.

from itertools import combinations
import heapq
import random

random.seed(1)

def simulate():

    player_ids = [1, 2, 3, 4, 5, 6, 7]

    combos = combinations(player_ids, 2)
    q = []
    new_q = []

    for combo in combos:
        heapq.heappush(q, (0, random.random(), combo))
        # heapq.heappush(q, (0, combo))

    for game_round in range(7):
        print(f'round {game_round + 1}')

        player_4_set = set()
        player_3_set = set()

        while q:
            count, _, combo = heapq.heappop(q)
            # count, combo = heapq.heappop(q)
            combo_set = set(combo)

            union_4 = player_4_set.union(combo_set)

            if len(union_4) <= 4:
                player_4_set = union_4
                heapq.heappush(new_q, (count + 1, random.random(), combo))
                # heapq.heappush(new_q, (count + 1, combo))
                continue
            
            union_3 = player_3_set.union(combo_set)
            inter = player_4_set.intersection(combo_set)

            if len(union_3) <= 3 and len(inter) == 0:
                player_3_set = union_3
                heapq.heappush(new_q, (count + 1, random.random(), combo))
                # heapq.heappush(new_q, (count + 1, combo))
                continue

            heapq.heappush(new_q, (count, random.random(), combo))
            # heapq.heappush(new_q, (count, combo))

        print(player_4_set)
        print(player_3_set)
        # print(new_q)
        q = new_q
        new_q = []

    result = [item[0] for item in q]
    return result

counter = 1
while True:
    result = simulate()
    print(result)
    if min(result) == max(result):
        print(f'result reached in {counter} iterations')
        break
    counter += 1
Comments (0)