As promised in a previous post, I worked on speeding up combination calculations of my app, goodMatches, finally to see it quickly returning results in a truly reasonable time for more people. The results are now contained in its new version including:
- we now support up to 20 people, with potentially up to 8 people resting
- it generally takes, at the start, up to 40 seconds for computation, instantly in most typical cases.
A baby step though it may seem, from the old 16 people 4 resting. But more will be supported in the planned global launch. Sorry for those people outside the U.K. and Japan, for whom the app is still not available, but it will come soon.
The key lies in a little bit unexpected place: fair turntaking. Here I mean turntaking of taking a rest, or sitting a match out. I guess this is not really happening in a very small group of people, as you try to gather just the right number of people. However, this does happen in a larger setting, like a social meeting of a small club. Five courts available. More than 20 people turn up. Very common, I suppose. Furthermore, in a country like Japan, where securing courts is far more difficult, you do invite more people than the courts’ capacity, making people take turn in resting. This is why I take this issue seriously, but I did not quite expect it to slow the speed down so much.
(Simple) Math of fair turntaking
This is actually a rather simple problem. No trade secret. As in the scenario just given, if 20+n people turn up for 5 courts, how many combinations of who sits out a match? This is an elementary math. More generally, if, when the capacity is c, and the surplus is s, there are C(c+s, s) ways. If 21 people turn up for the capacity of 20, you have 21 ways of picking a rester. Simple. And if 22? That will be 190 ways. 23? 3420 ways. I won’t continue, you see the gist: fair turntaking is an expensive business.
And not all these ways are as fair as each other in a series. If in the situation of two sitting out out of 22, you and Alice have been picked as resters, and then just when you think your turn has come, they pick you and Bob to sit the next one out, you’ll be pretty miffed I’m sure. They are different combinations from the eye of the math. You’re still miffed because it’s easy to pick two other than Alice and you, of course! But how far can you go without causing duplicates in the 190 combinations? Of course, you can go quite far, here 10 times. Not a problem for social tennis because you won’t play more than 10 matches. So you may think. But what about 23 people with 3 resting? Only 7 such disjoint rester sets guaranteed. For 27, only three. After three rounds, what should happen?
Let’s now come back to the Japanese situation where you might even have 7 people for one court (I’m not kidding). So between two games, three people wait aimlessly (you have a company at least). Now, who should be the next three people: easy, the ones who played. But then what should you do the third time round? Yes, one person play the first two games, so s/he should rest, and any other two. Easy enough. OK, so it continues. What about fourth round, fifth round? How many matches do you go through where this ‘cycle’ comes back to square one? Moving to a rather far-fetched scenario, what about 13 people gathered for a single court? First nine would be any nine, yes, and then who’s next?
Waiting for your turn is like packing biscuits into a box
I know I seem somewhat obsessed with the rare cases, but the more obsessed gave a name to this issue: Packing Problems. In a version of the problems you have different types of items, say different flavours of biscuits, and some box with some capacity, and small bags, again with a fixed capacity, that should contain a fixed number of distinct items each. Now you try to pack them in two layers: first in the small bags, n items each, and then put m bags into the box of capacity c (how suitably Japanese, double-packaging!) Now unfortunately, there is a surplus. Like 8 flavours, with bags of 3, where two flavour are left out in each bag. What’s the maximum number of series where you get different surplus items, or to put another way, get different combinations of small bags? You get our tennis turntaking problem!
And apparently, the problem is generally very hard. And dividing the combinations into equal sized sets is not always possible. So I did not even try to solve this general problem but focused on pragmatically giving fairest possible chances to everybody, and speeding up. Achieving both is a tricky business indeed, so this is a trade secret, but promise you, it’s not that something you’d like to know. All I would say is with 1.2.0, goodMatches is equipped with both.
And with this beta version proudly in my hand, I tried to use it in exactly in the scenario with some resters, and somebody said: I’m a bit weary today and would rather take more rests than other people. That’s a typical ‘oh man’ moment for a developer… oh man people are … well, people have their conditions and preferences. Fair enough.
More seriously, generally hard constraints don’t work. Likewise, not a ‘fair’ turntaking system either, where each time a different individual must or must not do something. Humans are … different, so flexibilities are the order in our business. So after all this time, I start thinking of replacing the current fair turntaking system. That’s a developer’s life. Well excited to further develop it, watch this space again for goodMatches’ evolution.
Keywords: Packing Problem, fair turntaking, social tennis