readme.md

build a schedule graph

In this article I'll try to show the audience how to build a simple tournament schedule graph and also describe the thought process that allowed me to improve my initial implementation.

1. problem definition

Every now and then I like to conduct office tournaments in different disciplines - FIFA and table tennis in particular. And, as we all know, everyone loves a good old tournament board with rankings and schedule that you can view in your browser and show to your mates.

To get a better idea of who is going to face who we need to create a tournament schedule. So, let's define our inputs. We'll start by pretending that we have a list of people retrieved from a database of some sort

interface IParticipant {
  id: number;
  name: string;
}

type Participants = IParticipant[];

const participants: Participants = [
  { id: 0, name: "A" },
  { id: 1, name: "B" },
  { id: 2, name: "C" },
  { id: 3, name: "D" },
  { id: 4, name: "E" },
  { id: 5, name: "F" },
  { id: 6, name: "G" },
  { id: 7, name: "H" }
];

What we need to do is to create a schedule in which each player plays against every other player exactly 1 time per tournament.

2. building a plain regular tournament schedule

As some of you may already know, there are many types of tournaments, but we are going to take UEFA Champions League as an example, because it has both of most common types - the championship and the knockout round. In this chapter I'll keep the team list of 4 teams to avoid extra long console outputs.

How would we approach such a task?

The basic idea is that each team needs to play exactly one match with every other team during the tournament. Later in the article we'll also develop a way to create legs where each team plays exactly 1 game per leg.

So, well need to iterate through the list of teams and form pairs while keeping track of each team's already processed encounters. Let's take look at a piece of code that tries to solve this:

function main(participants: Participants) {
  /**
  * A well-known way to avoid duplicates while maintainig high 
  * access speed is a hash map, so we create one by converting
  * the original teams list to an object of type:
  * { '0': {}, '1': {}, '2': {}, '3': {} }
  * We plan on the following:
  * 1. If we encounter a team that has not yet been paired with 
  * the current team -> create a pair.
  * 2. If we encounter a pair that already exists - do nothing.
  */
  const p = participants.reduce((a, c) => ({ ...a, [c.id]: {} }), {});
  for (let pId in p) { // iterate through every team in the map
    for (let cpId in p) { // iterate on
      if (cpId === pId || p[pId][cpId] || p[cpId][pId]) {
        continue;
      }
      p[pId][cpId] = true;
    }
  }
  return p; 
}

$ npx ts-node graph-builder.ts
{
  '0': { '1': true, '2': true, '3': true },
  '1': { '2': true, '3': true },
  '2': { '3': true },
  '3': {}
}

Right now we have a graph that represents each paired fixture in the tournament. We can dress it up as we like in the Chapter 4, but for now let's focus on something else.

Do you see how our graph is shaped? It resembles a triangle. If we increase the number of teams 8 the similarity is going to become even more obvious.

$ npx ts-node graph-builder.ts
{
  '0': {
    '1': true,
    '2': true,
    '3': true,
    '4': true,
    '5': true,
    '6': true,
    '7': true
  },
  '1': { '2': true, '3': true, '4': true, '5': true, '6': true, '7': true },
  '2': { '3': true, '4': true, '5': true, '6': true, '7': true },
  '3': { '4': true, '5': true, '6': true, '7': true },
  '4': { '5': true, '6': true, '7': true },
  '5': { '6': true, '7': true },
  '6': { '7': true },
  '7': {}
}

Sometimes, in order to determine a pattern, it's best to look at the data at different scales.

While I was observing the output for the first time I came up with this solution, I noticed that increasing the index linearly affects the size of fixture list for each team. It was like the task has started to give me clues on how to solve it even more efficiently.

Clearly, we can see that as we iterate through the list we need less and less fixtures for each next team, since on previous stages it has been matched with another team. And, besides, iteration is not cool anymore, so let's utilize some higher order functions to come up with much cleaner solution based on our new observations:

const build = (p: Participants) =>
  p.reduce((a, c, i) => ({ ...a, [c.name]: p.slice(i + 1) }), {});

If you run this piece of code you'll see that each team's ID has a corresponding list of opponents. No additional reduces or mappings, just the idea that on each iteration the size of opponent's list is going to shrink by 1 item.

{
  A: [
    { id: 1, name: "B" },
    { id: 2, name: "C" },
    { id: 3, name: "D" }
  ],
  B: [
    { id: 2, name: "C" },
    { id: 3, name: "D" }
  ],
  C: [{ id: 3, name: "D" }],
  D: []
};

Now, let's take this approach and make it return more consumer-friendly result by getting rid of hash map and transforming the algorithm to produce the plain list instead:

const build = (p: Participants) =>
  p.reduce(
    (a, c, i) => [
      ...a,
      ...p.slice(i + 1).map(o => ({ host: c.name, visitor: o.name }))
    ],
    []
  );

Executing this gives us a nice plain list of all matches for a current schedule:

$ npx ts-node graph-builder.ts
[
  { host: 'A', visitor: 'B' },
  { host: 'A', visitor: 'C' },
  { host: 'A', visitor: 'D' },
  { host: 'B', visitor: 'C' },
  { host: 'B', visitor: 'D' },
  { host: 'C', visitor: 'D' }
]

You can also check the correctness of any tournament schedule by knowing the following:

number_of_legs = number_of_teams - 1;
number_of_matches = number_of_teams * 2 - number_of_teams / 2; TBD FFS

3. building a knockout round grid

In order to create a knockout (KO) round we need to understand the rules of creating such a structure.

Traditionally, KO pairs are formed randomly, based on the outcome of the group stage. But there are also cases where tournament does not require a championship or a group stage and exists as a sequence of KO rounds.

Required number of teams for KO should be even, during each stage half of teams is eliminated.

Now, let's read the case description once again and pay attention to words sequence, each and half. Sounds like a recursive algorithm to me.

const shuffleTeams = (teams: Participants) =>
  teams.sort(() => Math.random() - 0.5);

function koBuilder(teams: Participants) {
  if (teams.length % 2 !== 0) { // do not allow odd sized lists
    throw new Error("number of teams should be even");
  }
  if (teams.length === 0) {
    return []; // return empty list to signal that recursion is over
  }
  // list can be shuffled once or during each execution, insignificant for small lists
  const shuffledTeams = shuffleTeams(teams);
  // during each call take 2 first teams and allow recursive calls to fill
  // the rest of the list  
  return [shuffledTeams.slice(0, 2), ...koBuilder(shuffledTeams.slice(2))];
}

$ npx ts-node graph-builder.ts
[
  [ { id: 3, name: 'D' }, { id: 0, name: 'A' } ],
  [ { id: 7, name: 'H' }, { id: 2, name: 'C' } ],
  [ { id: 6, name: 'G' }, { id: 5, name: 'F' } ],
  [ { id: 1, name: 'B' }, { id: 4, name: 'E' } ]
]

4. adding legs & away matches

Majority of serious championships in football require teams to play against each opponent 2 times - at home and away. It's also common to form separate matchday legs, during which each team plays it's match against it's next opponent. Let's use our existing graph builder in order to create tournaments that utilize those concepts.

We'll start by adding legs to our schedule. After that we can just take the first part of the season and mirror it onto the second one only this time each fixture's home and away team are going to switch places.

4.1 legs

participants.ts

interface IParticipant {
  name: string;
}

interface IMatch {
  host: string;
  visitor: string;
}

type Participants = IParticipant[];
type MatchList = IMatch[];
type Schedule = IMatch[][];

interface ILeggerRecord {
  matches: MatchList;
  participants: Map<string, boolean>;
}

const participants: Participants = [
  { name: "A" },
  { name: "B" },
  { name: "C" },
  { name: "D" },
  { name: "E" },
  { name: "F" },
  { name: "G" },
  { name: "H" }
];

const singleFixtureComposer = (partiticpants: Participants): MatchList =>
  partiticpants.reduce(
    (acc, currentParticipant, index) => [
      ...acc,
      ...partiticpants.slice(index + 1).map(remainingOpponent => ({
        host: currentParticipant.name,
        visitor: remainingOpponent.name
      }))
    ],
    []
  );

const compose = (...fns) => value =>
  fns.reduce((acc, curr) => curr(acc), value);

const shuffle = (list: any[]) => list.sort(() => Math.random() - 0.5);

const coinToss = (): boolean => Math.floor(Math.random() * 1e3) % 2 === 0;

const hostMapper = (match: IMatch): IMatch =>
  coinToss() ? match : { host: match.visitor, visitor: match.host };

const withHostVariator = (schedule: MatchList): MatchList =>
  schedule.map(hostMapper);

function withMatchdays(schedule: MatchList): Schedule {
  const l = participants.length - 1;
  const mapper = new Map<number, ILeggerRecord>();
  for (let i = 0; i < l; i++) {
    mapper.set(i, { matches: [], participants: new Map() });
  }

  for (let match of schedule) {
    for (let [_, leg] of mapper) {
      const { host, visitor } = match;
      const { matches, participants } = leg;
      if (!participants[host] && !participants[visitor]) {
        participants[host] = true;
        participants[visitor] = true;
        matches.push(match);
        break;
      }
    }
  }
  return Array.from(mapper.values()).map(leg => leg.matches);
}

const secondRoundMatchMapper = ({ host, visitor }: IMatch): IMatch => ({
  host: visitor,
  visitor: host
});

const secondRoundScheduleMapper = (round: MatchList): MatchList =>
  round.map(secondRoundMatchMapper);

const withSecondRound = (schedule: Schedule): Schedule =>
  schedule.concat(schedule.map(secondRoundScheduleMapper));

const res = compose(
  singleFixtureComposer,
  withHostVariator,
  withMatchdays,
  withSecondRound
)(participants);

console.log(res);