javascriptarrayssports-league-scheduling-problem

Breaking Season Schedule into Weeks Without Repeating Teams Playing


I am working through generating a league schedule and I'm stuck on the part where, for any given week, a team should only play once.

So far I have made sure that the correct number of games are played, and that each team plays their conference rivals 4 times, and their cross-conference opponents 2 times. This is the code I have for this:

let easternConfTeams = [a, b, c, d, e, f];
let westernConfTeams = [g, h, i, j, k, l];

const teamPool = [...easternConfTeams, ...westernConfTeams];

let schedule = teamPool.reduce((a, v, i) => {
  for (let j = i + 1; j < teamPool.length; j++) {
    if (i < 6) {
      if (j < 6) {
        a.push(`${v} : ${teamPool[j]}`);
        a.push(`${v} : ${teamPool[j]}`);
        a.push(`${v} : ${teamPool[j]}`);
        a.push(`${v} : ${teamPool[j]}`);
      } else {
        a.push(`${v} : ${teamPool[j]}`);
        a.push(`${v} : ${teamPool[j]}`);
      }
    } else {
      if (j < 6) {
        a.push(`${v} : ${teamPool[j]}`);
        a.push(`${v} : ${teamPool[j]}`);
      } else {
        a.push(`${v} : ${teamPool[j]}`);
        a.push(`${v} : ${teamPool[j]}`);
        a.push(`${v} : ${teamPool[j]}`);
        a.push(`${v} : ${teamPool[j]}`);
      }
    }
  }
  return a;
}, []);

And then I run this through a shuffle function:

shuffle = (schedule) => {
  let currentIndex = schedule.length,
    temporaryValue, randomIndex;

  // While there remain elements to shuffle...
  while (0 !== currentIndex) {

    // Pick a remaining element...
    randomIndex = Math.floor(Math.random() * currentIndex);
    currentIndex -= 1;

    // And swap it with the current element.
    temporaryValue = schedule[currentIndex];
    schedule[currentIndex] = schedule[randomIndex];
    schedule[randomIndex] = temporaryValue;
  }

  return schedule;
};

However, I'm stuck on the final piece, which is to turn this schedule of games into separate weeks. Since there are 12 teams, each week of the season should have 6 games -- and of those six games, no team should appear twice. In other words, each team should play for each week, but only once.

There are 192 games in total, which need to be divided into 32 weeks of 6 games each.

How could I ensure this?


Solution

  • Here is an alternate approach based on a round robin tournament scheduling algorithm.

    The round robin algorithm will generate an array of rounds of matches where each team is matched against every other team once in each round without repeating matches in any round. Then, there is a step that repeats those rounds as needed and alternates the matches (simulating home / away alternation). The rounds for matches between all teams are generated and repeated twice. Then the rounds for in-conference matches are generated, combined, and repeated twice more (since the in-conference teams already have 2 matches from the previous step).

    The result is 32 rounds (weeks) of 6 matches each where each team plays non-conference opponents twice and in-conference opponents 4 times once all rounds have been completed.

    const zip = (a, b) => a.map((e, i) => [e, b[i]]);
    const combine = (a, b) => zip(a, b).map((e) => [...e[0], ...e[1]]);
    const alternate = (rounds, repeats) => {
      const alt = [];
      for (let i = 0; i < repeats; i++) {
        const next = i % 2 ? rounds.map((r) => r.map((m) => [m[1], m[0]])) : rounds;
        alt.push(...next);
      }
      
      return alt;
    };
    
    const roundrobin = (teams) => {
      const rounds = [];
      const mid = teams.length / 2;
      for (let i = 0; i < teams.length - 1; i++) {
        const t = i ? [teams[0], ...teams.slice(-i), ...teams.slice(1, -i)] : teams;
        const t1 = t.slice(0, mid);
        const t2 = t.slice(mid).reverse();
        rounds.push(zip(t1, t2));
      }
      
      return rounds;
    };
    
    const east = ['a','b','c','d','e','f'];
    const west = ['g','h','i','j','k','l'];
    const schedule = [
      ...alternate(roundrobin([...east, ...west]), 2),
      ...alternate(combine(roundrobin(east), roundrobin(west)), 2)
    ];
    
    console.log(schedule);