Advancing a player in a draw
by Paulo Gonzalez
2020-09-21 | elixir tennis trees data-structures programming
2020 has been interesting (to say the least) for a number of reasons. One of them is the fact that Roland Garros (the only clay court Grand Slam in the season) was moved from June to September. A usual clay court season is comprised of multiple tournaments on clay so players can get rhythm and be at the top of their game when it comes to RG. RG is the last of the clay court tournaments (at least the highest level ones) in the season. So my favorite tennis season is happenning as we speak! This is excellent.
Racket sports have been a big part of my life. Competing in these sports has also played a big part in my life. I was never involved with managing tournaments, only played them. You basically followed orders: got a time, a court and went out to play your match.
Now that we were watching some tennis on tv, I wondered how things work under the hood. Lots of interesting questions and fairly complex problems come up when you are managing a tournament. Creating the draw, scheduling the matches, managing the results and many more non-trivial issues. The issue I want to discuss today is a fairly simple one: how to deal with the result of a match and advance the winner to the correct position in the next round.
Imagine the following 4 player tournament:
Semifinals |-----------------------| | Paulo | |-----------------------|--------- | Rafa Nadal | | Finals |-----------------------| |-----------------------| | ? | |-----------------------| | ? | |-----------------------| |-----------------------| | | Silvia | | |-----------------------|--------- | Roger Federer | |-----------------------|
You get the following results:
- - Paulo beats Rafa Nadal 6/7 7/6 7/6
- - Silvia beats Roger Federer 6/2 6/0
You then need to update the tournament draw to show the below:
Semifinals |-----------------------| | Paulo | |-----------------------|--------- | Rafa Nadal | | Finals |-----------------------| |-----------------------| | Paulo | |-----------------------| | Silvia | |-----------------------| |-----------------------| | | Silvia | | |-----------------------|--------- | Roger Federer | |-----------------------|
The approach below seems to work for our use case and is a great example of how important it is to frame a problem and play with the data.
As with every problem, it is imperative to try different approaches and how you frame the problem means a lot. I've seen that the solution (and how fast you can get to it) is directly correlated to how a problem is framed.
After talking to Kels and Kristen for a little bit, we arrived at the following:
- - A round will have different matches
- - A round also have positions, starting from the 1 going top to bottom
- - Each of the matches in the round should have a number, starting from 1 going top to bottom
- - A match will have two positions: top and bottom
# Data Structure A |-----------------------| | 1 A1P1 | A1 |-----------------------|--------- | 2 A1P2 | | B |-----------------------| |-----------------------| | 1 B1P1 | B1 |-----------------------| | 2 B1P2 | |-----------------------| |-----------------------| | | 3 A2P1 | | A2 |-----------------------|--------- | 4 A2P2 | |-----------------------| Legend: - A is a round - B is a round - A1 is a match in the A round - A2 is a match in the A round - A1P1 is the top position in the A2 match - And so on
In order to solve for "how to advance a player" we looked at an existing draw in a tournament that is about to start this week in Hamburg applied the structure above and jotted own a few scenarios, as seen below:
Name | Match No. | Position | Result Match No. | Result Position |
---|---|---|---|---|
rudd | 3 | 5 | 2 | 3 |
paire | 3 | 6 | 2 | 3 |
monfils | 12 | 24 | 6 | 12 |
hanfman | 12 | 23 | 6 | 12 |
fritz | 15 | 29 | 8 | 15 |
cuevas | 15 | 30 | 8 | 15 |
sandgren | 8 | 15 | 4 | 8 |
rublev | 8 | 16 | 4 | 8 |
Here is a screenshot of the draw:
It was a lot easier to reason about things when I had the table above to look at. To me, it was clear that the algorithm to advance a player to the correct position is as follows:
- - In order to get the next round's match number: If the match number is even, divide by 2. If odd, add 1 and divide by 2. The result is the match number in the next round.
- - In order to get the next round's position: this will be the same as the match number where the player came from.
If we look at Silvia's example above, she had position #3 and was playing match #2 in the round. So, (match #2 is even) -> 2 / 2 -> 1. So she is playing in next round's match #1. Since she came from match #2, her position in the next round's match #1 will be #2.
Thanks for Kels and Kristen who helped me solve this after dinner!
Thanks for reading!