Match Scheduling Algorithm Competition

[JesseK]

Originally Posted by Ether

If they want a good algorithm... why not put the challenge out there, offer a cash prize or a free pass to champs for your team, and give everybody 3 MONTHS (instead of 12 hours) to work on it

I wouldn't take a single coder 3 months, and a team of 4-6 could easily do a rough draft in 12 hours. I'd say that we should give them the same length as the build season: 45 days. There are 2 basic approaches I've tried in the past:

1. A combinatorial approach that uses all 500,000-some unique match pairings of a 84-team event (worst case example) and begins to brute-force build a schedule based upon rules. Conceivably this would be a fine approach until the end, where the rules would be harder to meet given the dwindling pool of match pairings that meet the rules.
2. An approach that calculates the 'buckets' of teams, assuming even spacing. For example, if 24 teams play 6 matches each, then one can create a long list of teams that is a simple stitching of 6 shorter lists {{1...24}{1...24}...{1...24}}. For minimum match spacing, the edges of the stitches should be checked for duplicate teams (easily done if one uses Collections.disjoint() in Java). After that, the list could be broken up into alliance pairings (multiple of N teams per alliance) and then match pairings (M alliances per match). Then an algorithm could check for duplicate alliance pairings, duplicate opponent pairings, etc. If the algorithm finds them (very likely if the stitched lists are randomly-generated) it's up to the coder to figure out what to do next -- live with them, regenerate new stitched lists to find a better pairing with less duplicates, etc.

I dug into match scheduling some, with various modifications to the approaches for efficiency. It's not easy to get it perfect, but it IS easy to get it started and is a great way to teach object-oriented programming to students who already have the basics of programming under their belt.

Really they should have 2 competitions: 1 that creates the algorithm, and 1 that creates an intuitive User-Interface for it. Both are equally difficult, IMO, and the latter would teach very fundamental concepts of software product design.