javascriptalgorithmround-robintournament

Round robin algorithm behaving strangely in Javascript

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:

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>

Solution

  • 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