Round robin algorithm behaving strangely in Javascript

KristofferAndersson
November 20, 2023
234 views
1 vote
2 Answers

I’m making a program with the goal of generating a schedule for a tournament (tennis doubles). Here is how it’s supposed to work:

I provide the function roundData(see below) that contains the players and when matches are supposed to play
A team shall only play once a week
Each match shall be unique, meaning that Team A only go against Team B once.

This function successfully generates 66 matches but apart from that there are errors.. It does not assign courts correctly, and after the first 3 weeks, it starts making weeks with only 4 matches for some reason.

I am so thankful for ANY input on this as I am stuck. I can’t find any examples of this either. Thanks!

I was expecting to get a schedule of 11 sessions/weeks and total 66 matches. I get 66 matches, but 15 weeks since the function doesnt always put 6 matches in a week.

function generateRoundRobinSchedule(roundData) {
  let teams = roundData.teams;
  let scheduleInfo = roundData.schedule;
  let allMatches = [];

  // Create all unique matches
  for (let i = 0; i < teams.length; i++) {
    for (let j = i + 1; j < teams.length; j++) {
      allMatches.push({
        team1: i,
        team2: j
      });
    }
  }

  // Helper function to add days to a date
  function addDays(dateStr, days) {
    const date = new Date(dateStr);
    date.setDate(date.getDate() + days);
    return date.toISOString().split('T')[0];
  }

  // Initialize variables for scheduling
  let matchSchedule = [];
  let currentDate = scheduleInfo.start_date;
  const timeslots = scheduleInfo.timeslots;
  const matchesPerWeek = timeslots.reduce((acc, slot) => acc + slot.courts.length, 0);

  // Schedule matches
  while (allMatches.length > 0) {
    let weeklyMatches = [];
    let teamsPlayedThisWeek = new Set();

    for (let match of allMatches) {
      if (!teamsPlayedThisWeek.has(match.team1) && !teamsPlayedThisWeek.has(match.team2)) {
        weeklyMatches.push(match);
        teamsPlayedThisWeek.add(match.team1);
        teamsPlayedThisWeek.add(match.team2);
      }

      if (weeklyMatches.length === matchesPerWeek) {
        break;
      }
    }

    // Remove scheduled matches from allMatches
    allMatches = allMatches.filter(match => !weeklyMatches.includes(match));

    // Assign timeslots and courts to weekly matches
    let timeslotIndex = 0;
    for (let match of weeklyMatches) {
      const timeslot = timeslots[timeslotIndex % timeslots.length];
      const court = timeslot.courts[timeslotIndex / timeslots.length % timeslot.courts.length >> 0];

      matchSchedule.push({
        team1: teams[match.team1],
        team2: teams[match.team2],
        date: currentDate,
        time: timeslot.time,
        court: court,
        duration: scheduleInfo.match_length
      });

      timeslotIndex++;
    }

    // Prepare for next week
    currentDate = addDays(currentDate, 7);
  }

  console.log(matchSchedule)
  return matchSchedule;
}

generateRoundRobinSchedule(roundData);

<script>
const roundData = {
  "teams": [
      { "player1_email": "1", "player2_email": "2" },
      { "player1_email": "3", "player2_email": "4" },
      { "player1_email": "5", "player2_email": "6" },
      { "player1_email": "7", "player2_email": "8" },
      { "player1_email": "9", "player2_email": "10" },
      { "player1_email": "11", "player2_email": "12" },
      { "player1_email": "13", "player2_email": "14" },
      { "player1_email": "15", "player2_email": "16" },
      { "player1_email": "17", "player2_email": "18" },
      { "player1_email": "19", "player2_email": "20" },
      { "player1_email": "21", "player2_email": "22" },
      { "player1_email": "23", "player2_email": "24" }
  ],
  "schedule": {
      "start_date": "2023-11-20",
      "days": ["Monday"],
      "timeslots": [
          { "time": "18:30", "courts": ["Court 1", "Court 2"] },
          { "time": "19:00", "courts": ["Court 4"] },
          { "time": "20:00", "courts": ["Court 1", "Court 2"] },
          { "time": "20:30", "courts": ["Court 4"] }
      ],
      "match_length": 90
  }
}
</script>

Answers

Your loop that assigns to courts doesn’t assign to multiple courts in each timeslot. Each time through the loop you’re going to the next timeslot.

Use index variables for the timeslots and courts, which you increment separately. You increment the timeslot index when the court index reaches the length for that timeslot.

function generateRoundRobinSchedule(roundData) {
  let teams = roundData.teams;
  let scheduleInfo = roundData.schedule;
  let allMatches = [];

  // Create all unique matches
  for (let i = 0; i < teams.length; i++) {
    for (let j = i + 1; j < teams.length; j++) {
      allMatches.push({
        team1: i,
        team2: j
      });
    }
  }

  // Helper function to add days to a date
  function addDays(dateStr, days) {
    const date = new Date(dateStr);
    date.setDate(date.getDate() + days);
    return date.toISOString().split('T')[0];
  }

  // Initialize variables for scheduling
  let matchSchedule = [];
  let currentDate = scheduleInfo.start_date;
  const timeslots = scheduleInfo.timeslots;
  const matchesPerWeek = timeslots.reduce((acc, slot) => acc + slot.courts.length, 0);

  // Schedule matches
  while (allMatches.length > 0) {
    let weeklyMatches = [];
    let teamsPlayedThisWeek = new Set();

    for (let match of allMatches) {
      if (!teamsPlayedThisWeek.has(match.team1) && !teamsPlayedThisWeek.has(match.team2)) {
        weeklyMatches.push(match);
        teamsPlayedThisWeek.add(match.team1);
        teamsPlayedThisWeek.add(match.team2);
      }

      if (weeklyMatches.length === matchesPerWeek) {
        break;
      }
    }

    // Remove scheduled matches from allMatches
    allMatches = allMatches.filter(match => !weeklyMatches.includes(match));

    // Assign timeslots and courts to weekly matches
    let timeslotIndex = 0;
    let courtIndex = 0;
    for (let match of weeklyMatches) {
      const timeslot = timeslots[timeslotIndex];
      const court = timeslot.courts[courtIndex];

      matchSchedule.push({
        team1: teams[match.team1],
        team2: teams[match.team2],
        date: currentDate,
        time: timeslot.time,
        court: court,
        duration: scheduleInfo.match_length
      });

      courtIndex++;
      if (courtIndex >= timeslot.courts.length) {
        courtIndex = 0;
        timeslotIndex++;
        if (timeslotIndex >= timeslots.length) {
          timeslotIndex = 0;
        }
      }
    }

    // Prepare for next week
    currentDate = addDays(currentDate, 7);
  }

  console.log(matchSchedule)
  return matchSchedule;
}

generateRoundRobinSchedule(roundData);

<script>
const roundData = {
  "teams": [
      { "player1_email": "1", "player2_email": "2" },
      { "player1_email": "3", "player2_email": "4" },
      { "player1_email": "5", "player2_email": "6" },
      { "player1_email": "7", "player2_email": "8" },
      { "player1_email": "9", "player2_email": "10" },
      { "player1_email": "11", "player2_email": "12" },
      { "player1_email": "13", "player2_email": "14" },
      { "player1_email": "15", "player2_email": "16" },
      { "player1_email": "17", "player2_email": "18" },
      { "player1_email": "19", "player2_email": "20" },
      { "player1_email": "21", "player2_email": "22" },
      { "player1_email": "23", "player2_email": "24" }
  ],
  "schedule": {
      "start_date": "2023-11-20",
      "days": ["Monday"],
      "timeslots": [
          { "time": "18:30", "courts": ["Court 1", "Court 2"] },
          { "time": "19:00", "courts": ["Court 4"] },
          { "time": "20:00", "courts": ["Court 1", "Court 2"] },
          { "time": "20:30", "courts": ["Court 4"] }
      ],
      "match_length": 90
  }
}
</script>

- ScottSauyet
- November 20, 2023 at 4:55 pm
- 0 votes
0
I didn’t try to understand and fix your code. Sorry. Instead I tried to solve the problem on my own. Here’s my attempt.

A simple algorithm is described on Wikipedia, where we fix one player, and then rotate the rest through a ⌈n/2⌉x 2 grid (with a dummy player in the case of an odd number; players facing this dummy have a bye in the round.)

This code does that and also tries to spread the games around the various venue/timeslots as well as spreading out which player is listed first. (I don’t think that matters for tennis. In chess, it would determine who has the White pieces and hence goes first.)

The result is a an array of rounds. Each round has an array of venues. (Here that would also include timeslots.) And at each spot in the grid is an array of two competitors (doubles teams in your case.)
const rotate = (n, xs) => [ ...xs.slice(xs.length - (n % xs.length)), ...xs.slice(0, xs.length - (n % xs.length)) ] const BYE = Symbol() const roundRobin = (ts, all = ts .concat (ts .length % 2 == 0 ? [] : [BYE]), rest = all.slice(0, -1)) => rest .map ((_, i) => rotate (i + 1, fold([...rotate (i, rest), all.at(-1)]))) .map(b => b.filter(([a, b]) => a !== BYE && b !== BYE)) .map((b, i) => i % 2 == 0 ? b : b.map(([a, b]) => [b, a])) const fold = xs => xs.slice(0, Math.ceil(xs.length / 2)) .map ((x, i) => [x, xs[xs.length - i - 1]]) //---------------------------------------------------------------------- // (Disposable) code to log results to console const display = sched => ` \ Venue/Time \ ${sched[0].map((_, i) => String(i + 1).padStart(4, ' ')).join('')} Round +----------------------- ${sched.map((r, i) => String(i + 1).padStart(5, ' ') + ' | ' + r.map(([a, b]) => a + b).join(' ')).join('n')}` console.log(display(roundRobin([...'ABCDEFGHIJKL'])))

.as-console-wrapper {max-height: 100% !important; top: 0}
We use letters here to represent the teams; but you could simply use your team objects instead. We don’t try to map the venues here onto your location/timeslots. That should be easy enough to do.

The code
- rotate: is a simple reusable utility function that rotates an array n places to the right:
```
rotate (2, ['A', 'B', 'C', 'D', 'E', 'F', 'G']) ==> ['F', 'G', 'A', 'B', 'C', 'D', 'E']
```
  It will wrap, so n can be any positive integer
- BYE is just a dummy team to make the numbers work correctly. A team facing BYE in the initial list will have a bye in that round. Although I remove these matches here, we could equally well keep them and display a specific bye for each round.
- roundRobin is the main function. It implements the circle algorithm. It also makes an attempt to rotate the rounds to somewhat equalize the first- or second-listing and the appearances at each venue. It has mixed success at this, and we might revisit these two factors.
- fold is a helper function used to turn a list like ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'] into two columns, like this:
```
A  H
B  G
C  F
D  E
```
  It returns [['A', 'H'], ['B', 'G'], ['C', 'F'], ['D', 'E']]
- display is just a way to create a string version of the results to display to the console.
Login or Signup to reply.

Please signup or login to give your own answer.

Click here to cancel reply.

Round robin algorithm behaving strangely in Javascript

Answers

The code