Bowling league lane assignment problem

Projects Programming
1

I can't wrap my head around this problem: My son-in-law is in a bowling league with 36 (2-man) teams. They have reserved 18 lanes, grouped into 9 sets of 2 lanes each. The goal is to have each team bowl every other team at least once during their 11-week season. The first night looks like:

Lanes 1-2 ------ Lanes 3-4 ------ Lanes 5-6 ------ Lanes 7-8 ------ (etc) ------ Lanes 17-18
1-2-3-4 -----------5-6-7-8 ---------9-10-11-12 ------13-14-15-16 ------------------33-34-35-36

After the first night, team 1 is considered to have bowled against teams 2, 3, and 4 and they should not face those teams again until they have bowled against all of the remaining 32 teams. Likewise, team 2 should not face teams 1, 3, or 4 again until they have bowled against the other 32 teams.

Initially, I thought this would reduce to a simple permutations/combinations problem, but if it does, I'm not seeing it. There's probably one of you who shows the solution and everyone slams the heel of their hand into the forehead muttering "I should have seen it!". But...so far, no epiphany.

2

Assign each team a 32 bit int. Each bit position can represent a team, a 0 means not played and a 1 means played.

Team1:
00000000000000000000000000000 <<< has not played a team

Team1:
00000000000000000000000001011 <<< means they played team 1 and 2 and 4.

3

Never thought of that approach. Let me see if I can figure out the logic sequence...

Thanks!

4

It looks as though there are three games each week. Over eleven weeks, that's only thirty three teams played. Are there two extras slotted in somewhere to account for the unplayed teams?

5

Evidently, it's okay if all teams don't play each other. They just don't want any one team to play a team multiple times.

@Idahowalker: Given there are 36 teams, it seems a long long int is required, right?

6

A unit64_t would give a some of extensibility. A ESP32 or some other 32-bit microcontroller can handle uint64_t's.

7

Not a problem as I'm using a Teensy 4.1. Again...thanks!

1 Like
8

Is there a need for it to run on an Arduino?

9

No. He would be happy if I just copied the schedule from the Serial object's output and sent it to him.

10

If Arduino is what you're used to, that works. I would just use a compiler on the PC you're using to program the Teensy instead - better debugging tools.

Does it matter which lane a team gets? Is there one that people would be annoyed to have every week? You know, the one next to the noisy drunken firefighters :wink:

Should next year's schedule be different to this year?

11

I think the section "Round Robin scheduling: Even number of teams." is what you are looking for.

12

Teams do not care which lane(s) they bowl on. I have a feeling most of the bowlers are drunk anyway.

He told me that, if we can do a schedule for one year, they would re-use it the next.

13

I just did a quick look and it looks promising. I'm going to dig into it further...thanks!!

14

If I implemented it correctly, this should be a schedule for 36 teams playing 18 matches at the same time.

Round 0: [(0, 35), (1, 34), (2, 33), (3, 32), (4, 31), (5, 30), (6, 29), (7, 28), (8, 27), (9, 26), (10, 25), (11, 24), (12, 23), (13, 22), (14, 21), (15, 20), (16, 19), (17, 18)]
Round 1: [(1, 35), (2, 0), (3, 34), (4, 33), (5, 32), (6, 31), (7, 30), (8, 29), (9, 28), (10, 27), (11, 26), (12, 25), (13, 24), (14, 23), (15, 22), (16, 21), (17, 20), (18, 19)]
Round 2: [(2, 35), (3, 1), (4, 0), (5, 34), (6, 33), (7, 32), (8, 31), (9, 30), (10, 29), (11, 28), (12, 27), (13, 26), (14, 25), (15, 24), (16, 23), (17, 22), (18, 21), (19, 20)]
Round 3: [(3, 35), (4, 2), (5, 1), (6, 0), (7, 34), (8, 33), (9, 32), (10, 31), (11, 30), (12, 29), (13, 28), (14, 27), (15, 26), (16, 25), (17, 24), (18, 23), (19, 22), (20, 21)]
Round 4: [(4, 35), (5, 3), (6, 2), (7, 1), (8, 0), (9, 34), (10, 33), (11, 32), (12, 31), (13, 30), (14, 29), (15, 28), (16, 27), (17, 26), (18, 25), (19, 24), (20, 23), (21, 22)]
Round 5: [(5, 35), (6, 4), (7, 3), (8, 2), (9, 1), (10, 0), (11, 34), (12, 33), (13, 32), (14, 31), (15, 30), (16, 29), (17, 28), (18, 27), (19, 26), (20, 25), (21, 24), (22, 23)]
Round 6: [(6, 35), (7, 5), (8, 4), (9, 3), (10, 2), (11, 1), (12, 0), (13, 34), (14, 33), (15, 32), (16, 31), (17, 30), (18, 29), (19, 28), (20, 27), (21, 26), (22, 25), (23, 24)]
Round 7: [(7, 35), (8, 6), (9, 5), (10, 4), (11, 3), (12, 2), (13, 1), (14, 0), (15, 34), (16, 33), (17, 32), (18, 31), (19, 30), (20, 29), (21, 28), (22, 27), (23, 26), (24, 25)]
Round 8: [(8, 35), (9, 7), (10, 6), (11, 5), (12, 4), (13, 3), (14, 2), (15, 1), (16, 0), (17, 34), (18, 33), (19, 32), (20, 31), (21, 30), (22, 29), (23, 28), (24, 27), (25, 26)]
Round 9: [(9, 35), (10, 8), (11, 7), (12, 6), (13, 5), (14, 4), (15, 3), (16, 2), (17, 1), (18, 0), (19, 34), (20, 33), (21, 32), (22, 31), (23, 30), (24, 29), (25, 28), (26, 27)]
Round 10: [(10, 35), (11, 9), (12, 8), (13, 7), (14, 6), (15, 5), (16, 4), (17, 3), (18, 2), (19, 1), (20, 0), (21, 34), (22, 33), (23, 32), (24, 31), (25, 30), (26, 29), (27, 28)]
Round 11: [(11, 35), (12, 10), (13, 9), (14, 8), (15, 7), (16, 6), (17, 5), (18, 4), (19, 3), (20, 2), (21, 1), (22, 0), (23, 34), (24, 33), (25, 32), (26, 31), (27, 30), (28, 29)]
Round 12: [(12, 35), (13, 11), (14, 10), (15, 9), (16, 8), (17, 7), (18, 6), (19, 5), (20, 4), (21, 3), (22, 2), (23, 1), (24, 0), (25, 34), (26, 33), (27, 32), (28, 31), (29, 30)]
Round 13: [(13, 35), (14, 12), (15, 11), (16, 10), (17, 9), (18, 8), (19, 7), (20, 6), (21, 5), (22, 4), (23, 3), (24, 2), (25, 1), (26, 0), (27, 34), (28, 33), (29, 32), (30, 31)]
Round 14: [(14, 35), (15, 13), (16, 12), (17, 11), (18, 10), (19, 9), (20, 8), (21, 7), (22, 6), (23, 5), (24, 4), (25, 3), (26, 2), (27, 1), (28, 0), (29, 34), (30, 33), (31, 32)]
Round 15: [(15, 35), (16, 14), (17, 13), (18, 12), (19, 11), (20, 10), (21, 9), (22, 8), (23, 7), (24, 6), (25, 5), (26, 4), (27, 3), (28, 2), (29, 1), (30, 0), (31, 34), (32, 33)]
Round 16: [(16, 35), (17, 15), (18, 14), (19, 13), (20, 12), (21, 11), (22, 10), (23, 9), (24, 8), (25, 7), (26, 6), (27, 5), (28, 4), (29, 3), (30, 2), (31, 1), (32, 0), (33, 34)]
Round 17: [(17, 35), (18, 16), (19, 15), (20, 14), (21, 13), (22, 12), (23, 11), (24, 10), (25, 9), (26, 8), (27, 7), (28, 6), (29, 5), (30, 4), (31, 3), (32, 2), (33, 1), (34, 0)]
Round 18: [(18, 35), (19, 17), (20, 16), (21, 15), (22, 14), (23, 13), (24, 12), (25, 11), (26, 10), (27, 9), (28, 8), (29, 7), (30, 6), (31, 5), (32, 4), (33, 3), (34, 2), (0, 1)]
Round 19: [(19, 35), (20, 18), (21, 17), (22, 16), (23, 15), (24, 14), (25, 13), (26, 12), (27, 11), (28, 10), (29, 9), (30, 8), (31, 7), (32, 6), (33, 5), (34, 4), (0, 3), (1, 2)]
Round 20: [(20, 35), (21, 19), (22, 18), (23, 17), (24, 16), (25, 15), (26, 14), (27, 13), (28, 12), (29, 11), (30, 10), (31, 9), (32, 8), (33, 7), (34, 6), (0, 5), (1, 4), (2, 3)]
Round 21: [(21, 35), (22, 20), (23, 19), (24, 18), (25, 17), (26, 16), (27, 15), (28, 14), (29, 13), (30, 12), (31, 11), (32, 10), (33, 9), (34, 8), (0, 7), (1, 6), (2, 5), (3, 4)]
Round 22: [(22, 35), (23, 21), (24, 20), (25, 19), (26, 18), (27, 17), (28, 16), (29, 15), (30, 14), (31, 13), (32, 12), (33, 11), (34, 10), (0, 9), (1, 8), (2, 7), (3, 6), (4, 5)]
Round 23: [(23, 35), (24, 22), (25, 21), (26, 20), (27, 19), (28, 18), (29, 17), (30, 16), (31, 15), (32, 14), (33, 13), (34, 12), (0, 11), (1, 10), (2, 9), (3, 8), (4, 7), (5, 6)]
Round 24: [(24, 35), (25, 23), (26, 22), (27, 21), (28, 20), (29, 19), (30, 18), (31, 17), (32, 16), (33, 15), (34, 14), (0, 13), (1, 12), (2, 11), (3, 10), (4, 9), (5, 8), (6, 7)]
Round 25: [(25, 35), (26, 24), (27, 23), (28, 22), (29, 21), (30, 20), (31, 19), (32, 18), (33, 17), (34, 16), (0, 15), (1, 14), (2, 13), (3, 12), (4, 11), (5, 10), (6, 9), (7, 8)]
Round 26: [(26, 35), (27, 25), (28, 24), (29, 23), (30, 22), (31, 21), (32, 20), (33, 19), (34, 18), (0, 17), (1, 16), (2, 15), (3, 14), (4, 13), (5, 12), (6, 11), (7, 10), (8, 9)]
Round 27: [(27, 35), (28, 26), (29, 25), (30, 24), (31, 23), (32, 22), (33, 21), (34, 20), (0, 19), (1, 18), (2, 17), (3, 16), (4, 15), (5, 14), (6, 13), (7, 12), (8, 11), (9, 10)]
Round 28: [(28, 35), (29, 27), (30, 26), (31, 25), (32, 24), (33, 23), (34, 22), (0, 21), (1, 20), (2, 19), (3, 18), (4, 17), (5, 16), (6, 15), (7, 14), (8, 13), (9, 12), (10, 11)]
Round 29: [(29, 35), (30, 28), (31, 27), (32, 26), (33, 25), (34, 24), (0, 23), (1, 22), (2, 21), (3, 20), (4, 19), (5, 18), (6, 17), (7, 16), (8, 15), (9, 14), (10, 13), (11, 12)]
Round 30: [(30, 35), (31, 29), (32, 28), (33, 27), (34, 26), (0, 25), (1, 24), (2, 23), (3, 22), (4, 21), (5, 20), (6, 19), (7, 18), (8, 17), (9, 16), (10, 15), (11, 14), (12, 13)]
Round 31: [(31, 35), (32, 30), (33, 29), (34, 28), (0, 27), (1, 26), (2, 25), (3, 24), (4, 23), (5, 22), (6, 21), (7, 20), (8, 19), (9, 18), (10, 17), (11, 16), (12, 15), (13, 14)]
Round 32: [(32, 35), (33, 31), (34, 30), (0, 29), (1, 28), (2, 27), (3, 26), (4, 25), (5, 24), (6, 23), (7, 22), (8, 21), (9, 20), (10, 19), (11, 18), (12, 17), (13, 16), (14, 15)]
Round 33: [(33, 35), (34, 32), (0, 31), (1, 30), (2, 29), (3, 28), (4, 27), (5, 26), (6, 25), (7, 24), (8, 23), (9, 22), (10, 21), (11, 20), (12, 19), (13, 18), (14, 17), (15, 16)]
Round 34: [(34, 35), (0, 33), (1, 32), (2, 31), (3, 30), (4, 29), (5, 28), (6, 27), (7, 26), (8, 25), (9, 24), (10, 23), (11, 22), (12, 21), (13, 20), (14, 19), (15, 18), (16, 17)]

[edit] And this is the pseudo (Python) code I used.

def round_robin_even(teams):
    cycle = teams - 1

    rounds = []
    for r in range(cycle):
        pairs = [(r, cycle)]
        for i in range(1, teams // 2):
            pairs.append(((r + i) % cycle, (r - i) % cycle))
        rounds.append(pairs)

    return rounds

    
for i, r in enumerate(round_robin_even(36)):
    print(f'Round {i}: {r}')
15

I don't know Python, but I'm pretty sure I can figure out your implementation. Thank you for this...I am sincerely grateful (and humbled!).

16

I can port it to C++ (or perhaps something else) for you if you want, but I figured that you only needed the answer.

17

I will try to recode it in C or C++, as I'm comfortable with those. However, perhaps I can find a Python tutorial that would give me enough to do the port to C.

18

Sure, have fun. Let me know if you need any help.

19

All:
jFjlaros has provided a link to his solution here

20

This topic was automatically closed 180 days after the last reply. New replies are no longer allowed.