I've been working on devising a tournament pairing system modeled after the updated UEFA Champion League structure. The league phase involves 36 teams, categorized into 4 different pots. Each team is scheduled to play a total of 8 matches against 2 opponents from each pot, resulting in a grand total of 144 matches. While attempting to implement this logic, I encountered challenges with developing a function incorporating effective backtracking. Here's the code I've attempted, but unfortunately failed to execute successfully:
https://jsfiddle.net/4cgm1Lo8/5/
const pots = [
["A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "A9"],
["B1", "B2", "B3", "B4", "B5", "B6", "B7", "B8","B9"],
["C1", "C2", "C3", "C4", "C5", "C6", "C7", "C8","C9"],
["D1", "D2", "D3", "D4", "D5", "D6", "D7", "D8","D9"],
];
const MATCH_COUNT = 144;
const MAX_ROUNDS = 8
function run() {
const teamIds = _.flatten(pots)
return teamIds.reduce((matches,thisTeamId) => {
for (let round = 0; round < MAX_ROUNDS; round++) {
const thisTeamMatches = matches.filter(match => match.includes(thisTeamId))
if (thisTeamMatches.length >= MAX_ROUNDS) {
break;
}
const pool = teamIds.filter(poolTeamId => {
const encounteredBefore = thisTeamMatches.find(match => match.includes(poolTeamId))
const potEncounterCount = thisTeamMatches.filter(match => {
const opponentId = match.find(m => m != thisTeamId)
return getTeamPot(opponentId, pots) === getTeamPot(poolTeamId, pots)
})
const poolTeamIdMatches = matches.filter(match => match.includes(poolTeamId))
return poolTeamId != thisTeamId && !encounteredBefore && potEncounterCount.length < 2 && poolTeamIdMatches.length < MAX_ROUNDS
})
matches.push([thisTeamId, _.sample(pool)])
}
return matches
}, [] as string[][])
}
function getTeamPot(teamId: string, pots: string[][]) {
return pots.findIndex((pot) =>
pot.find((potTeamId) => potTeamId === teamId),
);
}
function getOpponent(yourTeamId: string, match: string[][]){
return match.find(m => m != thisTeamId)
}
console.log(run())
The current function falls short of creating all 144 matches required. Some matchups generated have undefined opponents due to certain limitations within the code. It struggles to handle scenarios where a suitable opponent cannot be found for a particular team.
What approach would you suggest implementing a robust backtracking method capable of filling in the missing matchups with undefined opponents?