Picking fair football teams twice: one algorithm in TypeScript and Swift, same answer every time

Every group that plays football every week argues about the same thing before kick-off: the teams. Someone picks, one side wins 9–2, and next week the argument starts again.

I'm building Squadcard, an app for football groups that play every week. After each game the players rate each other out of 10, those ratings become each player's card, and the app uses them to pick next week's teams. The team picker turned out to be the most interesting bit of engineering in it, so this post is about that.

The problem

You have 10 to 22 players who said they're in. Each has a rating (an integer 1–99). Split them into two teams so that:

• the teams are the same size (or one apart),
• the keepers are split,
• the rating totals are as close as possible,
• defenders, midfielders and forwards are spread out,
• and the organiser's rules hold: "keep these two apart" (brothers who always argue) and "keep these two together" (the pair who share a lift).

The first two and the organiser's rules are hard rules; the rest you only want as good as possible.

The approach: a cost, random starts and local search

There's no clever exact answer worth the trouble here, and with ~20 players you don't need one. Everything becomes a single integer cost:

cost = 10000 × (hard rules broken)
     + |ratingsA − ratingsB|
     + 2 × (|defA − defB| + |midA − midB| + |fwdA − fwdB|)

The 10,000 means one broken hard rule always costs more than any rating gap could.

Then:

1. Merge the "keep together" pairs into units with union-find, so they always move as one.
2. Ten random starts. Shuffle the units (Fisher–Yates) and deal them out, each to whichever team is smaller.
3. 100 tries per start. Pick two units at random. If they're on different teams, swap them; if they're on the same team, move one across. Keep the change only if the cost goes strictly down.
4. Keep the best start, and flip the teams so the first player is always on team A. That way the same split always looks the same.

That's 1,000 evaluations, which is nothing even on an old phone. "Reshuffle" in the app is the same players with a new random seed.

The catch: it has to run in two languages

The website (TypeScript, on the server) and the iPhone app (Swift, on the phone) both pick teams. If they ever disagreed, an organiser could see one set of teams in the app and their players a different set on the web. So the two implementations have to give exactly the same teams for the same input and seed. Not "about the same": the same.

Three things made that work.

1. My own random number generator. Math.random() and Swift's generators can't be seeded to match, so both sides use mulberry32: four lines, unsigned 32-bit arithmetic that wraps around.

TypeScript:

export function mulberry32(seed: number): () => number {
  let a = seed >>> 0;
  return () => {
    a = (a + 0x6d2b79f5) >>> 0;
    let t = Math.imul(a ^ (a >>> 15), 1 | a);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return (t ^ (t >>> 14)) >>> 0;
  };
}

Swift:

public mutating func next() -> UInt32 {
    state = state &+ 0x6D2B_79F5
    var t = (state ^ (state >> 15)) &* (1 | state)
    t = (t &+ ((t ^ (t >> 7)) &* (61 | t))) ^ t
    return t ^ (t >> 14)
}

The traps are all in the details: in JavaScript, Math.imul instead of * (a normal multiply goes through floating point and loses the low bits), and >>> 0 to bring the result back to unsigned. In Swift, the wrapping operators &+ and &*, which would otherwise crash on overflow.

2. Integer maths only. Ratings are whole numbers and the cost is a sum of whole numbers, so there's no floating point anywhere in the search. Two languages can round a float differently. They can't disagree about integer addition.

3. One spec, one set of test cases, two implementations. The algorithm is written down step by step in a README, including the boring bits that cause drift: the order of the random calls (i first, then j), that a tie between starts keeps the earlier one, that a unit's root is its lowest input index. "Anything not written here is a bug in one side."

Next to it, a JSON file holds the first five numbers mulberry32 produces for four seeds (0, 1, 42 and 2³²−1), plus 16 full cases: players, organiser rules, seed and the exact expected teams. Both test suites load the same file. The rule for changing anything: change the test cases first, then both implementations.

The ratings side, briefly

The ratings that go in come from the players. After each game everyone rates everyone else out of 10. Nobody ever sees who voted what, not even the organiser: only totals. Once six or more people have voted for someone, their highest and lowest votes are dropped before averaging, so rating your mate a 1 as a joke barely moves anything.

Try it

The same picker runs in your browser at squadcard.app/team-generator: no sign-up, type the names, say roughly how good each one is, tick the keepers, get two fair sides. If you play in a weekly game, I'd love to hear how your group picks teams today, and what would make you trust an app to do it.