Today was pretty epic. I started it out with a 90 minute long video call with my brother. Let's go back in time to explain why.
This post contains diagrams that require a screen and a monospaced font to understand.
A couple of days ago a friend DM'd me asking if I could create a tournament bracket of 897 competitors. Turns out the competitors that he had in mind were songs from the epicord group on bandcamp, which I'm part of. He came up with the idea of ranking all 897 (!!) songs on the bandcamp in a tournament bracket, since what else are we going to do in quarantine, right?
Of course, it's not as simple as just stuffing them into a bracket.
I don't think there are any online tournament organisers that allow you to use 897 competitors. Even if there was a website that did that, it would end up being very unwieldy to look at.
So we're doing 13 sub-brackets of 69 (nice) songs in each, which happens to divide perfectly, which is extremely hilarious. After each bracket of 69 plays out, the winners of each will be combined into a final winner's showdown bracket of 13 to find the ULTIMATE WINNER.
All the songs also have an initial order of most plays to least plays, so we can actually seed them into a bracket. The idea with bracket seeding is that since only one competitor can advance from each matchup, you don't want to pit good players against each other too soon, because if you did, one of them would be eliminated from the rest of the competition forever and another competitor which might be worse could actually get farther in the bracket. So in the first round, the competitor with the best predicted outcome is set against the competitor with the worst predicted outcome, and the second best competitor goes against the second worst, and so on. After that first round, the best player then needs to go the worst player out of everyone remaining. This makes it quite complicated to arrange the people.
Many online bracket generaters, including Challonge, which we decided to use, will actually do this seeding algorithm for you, and you just have to provide the competitors in the correct order. However, the problem is when I want to run sub-brackets. How do I arrange the competitors so that the correct people participate in the sub-bracket?
My first idea was to take the first [0:69] slice from the list and make that the first sub-bracket. But of course this will compete the 69 best songs, which means that 68 of the top 69 won't make it to the final 13. Clearly this isn't acceptable.
My second idea was to run the seeding for 897, then run through the seeding and use that as the order in which to take slices from. I spent far too long doing this, and while it's certainly better than the previous idea, it's still not perfect. Higher seeded people can still be knocked out sooner than lower seeding people, which a perfect bracket would avoid.
I was stumped, so I went on a 90 minute long video call with my younger brother and he figured out what the perfect solution was, and I happened to figure it out at the same time by working backwards. We tested it on a fake bracket with 5 groups of 3, because that's a small enough number that I could draw it all on paper, and it actually turned out to be the right answer. I can't thank him enough for this.
Let's run through the algorithm together, assuming that there are 15 competitors which will go into 5 groups of 3. After each sub-bracket of 3 is done, the final bracket of 5 will take place with the winners.
The competitors: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15. Lower number is a higher seed. If the real competition progresses as the seeds would expect, #1 should win, #2 should come second, and #3 and #4 should be eliminated in the same stage before #2.
First, create the 5 sub-brackets to put competitors into: A B C D E
Now go from left to right adding competitors to each sub-bracket:
A B C D E --------------------- 1 2 3 4 5
5 competitors are now assigned to sub-brackets, one in each. This at least helps the top 5 make it to the final bracket. But we have 10 competitors left to assign.
Now continue adding to the sub-brackets, but this time from right to left:
A B C D E --------------------- 1 2 3 4 5 10 9 8 7 6
Each sub-bracket now has 2 competitors in it, with 5 competitors left to assign to brackets. If each sub-bracket was run now, #1 would be against #10, which is what we want, best vs worst. This pattern of best vs worst, which is exactly what we are trying to create, continues: #2 vs #9, #3 vs #8...
Add the third and final row from left to right:
A B C D E --------------------- 1 2 3 4 5 10 9 8 7 6 11 12 13 14 15
All competitors are sorted.
Now you might be thinking, surely this is isn't right! #1 is against #11, not #15. I thought this too at first. This thought is wrong.
You have to remember is that #1 is against #Infinity, because #1 actually gets a bye on the first round, because there are only 3 competitors and that's how brackets of 3 work:
1¯\__ X \__ 10¯\__/ 11_/
If you draw it all out, you'll find that after the first round is done, the competitors that are remaining (assuming matches go according to seeding) are 1 2 3 4 5 6 7 8 9 10. And #1 is against #10 in the next match. We've proceeded exactly according to plan.
We got sort of lucky with 3 people, but to be more specific, once we know which competitors will be in the sub-bracket, we have to actually seed them accordingly. For 3 people, you've already seen the seed. For 4 people, numbered 1 2 3 4, the seed order actually looks like this:
1-\__ 4-/ \__ 3-\__/ 2-/
This means that if after the back-and-forth process the competitors in group 1 were numbers 1 8 9 16 (you can accomplish this by grouping 16 people into 4 brackets), that sub-bracket would look like this:
1-\__ 16-/ \__ 9-\__/ 8-/
Once all the sub-brackets are complete, each of the winners are seeded again into the final bracket. Going back to the original example of 5 groups of 3, the final bracket would be a bracket of 5, which looks like this:
1-\__ X \__ 4-\__/ \ 5-/ \__ 2-\__ / X \__/ 3-\__/ X
When putting the winners of each sub-bracket into this, the groups should be arranged in the same way.
winner of A-\__ X \__ winner of D-\__/ \ winner of E-/ \__ winner of B-\__ / X \__/ winner of C-\__/ X
Pretty good and pretty easy huh?
If you wanted an algorithm to actually generate a single bracket, here's one I stole from Stack Overflow: (Python 3)
from math import log, ceil
def seed(n):
ol = [1]
for i in range( ceil( log(n) / log(2) ) ):
l = 2*len(ol) + 1
ol = [e if e <= n else 0 for s in [[el, l-el] for el in ol] for e in s]
return ol
No, I don't know how it works.
Today I also did some shenanigans with the Challonge API, which is a very good API actually, but I think I'll save talking about that for tomorrow, since I'm not quite finished with it yet.
— Cadence
