Last week for a project my partner and I built a bracket simulator site in Rails that seeded fake players/teams using a gem called Faker- and then randomized their stats before seeding a bracket. This week I wanted to highlight some of that code- as well as some new tweaks I've made that allow brackets to be created recursively via a binary tree. Seeding a bracket turned out to be easy- but creating the actual appropriate matchups ended up being a bit of nightmare.
The ultimate goal in the project was to create an array of all teams- ordered by matchup in an actual bracket- remove the first two teams and have them "play" and enqueue the winner- so with that approach in mind I'm going to run through the difficulties in actually ordering a proper bracket- for reference, a properly seeded 8 team bracket in array form would look something like:
[1,8,4,5,3,6,2,7]
This order would result in the proper matchups being played in the first round- as well as their proper placement within a bracket to ensure later rounds would play out correctly.
Lets start with the original idea that flopped almost instantly- we created an array of all teams based on their "power score" ordered from highest to lowest- to get the proper matchups all we did was iterate through the array and pull the first available team and the last available team- and while this worked for creating the proper matchups- it failed miserably in actually creating a bracket- as the 1 and 2 seeds wound up meeting in the second round- as opposed to the finals. what this resulted in:
[1,8,2,7,3,6,4,5]
Correct matchups but in the wrong order- ie the winners of 1v8 and 2v7 would play in round 2 (as opposed to round 3/finals)
After many brackets were drawn some patterns were found:
-In the first round the two teams seeds always add up to the number of tourney entrants+1 (ie in an 8 team bracket the seeds at to 9)
-Going off of the above you can find an opposing matchup by doing
(entrants+1)-current seed
-The number of rounds played in any tournament = log2(entrants)
With the above in mind- expanding a bracket became possible
-To make a new round we would take a seed and find what it's matchup if the bracket size was doubled- so going from a 2 team to 4 team tourney- the 1 team would now play the 4 seed (calculated via #teams*2+1-seed (2*2+1-1 in this case) which comes to 4. The same math on a 2 seed results in them playing the 3 seed).
In our project we used this process to create an array of matchups- starting w/ a seeded 4 team array and expanding it however many times needed to meet the number of entrants:
def double_bracket(bracket)
doubled_size=bracket.length*2
doubled=[]
bracket.each do |seed|
doubled.push(seed)
doubled.push((doubled_size+1)-seed)
end
doubled
end
def bracket_order(entrants)
starting=[1,4,3,2]
if entrants==4
return starting
else
for i in 1..(Math.log2(entrants)-2)
starting=double_bracket(starting)
end
return starting
end
end
Then with a correctly ordered array of seeds (bracket_order) we could map our array of ordered team objects (ordered_teams) onto it- to get a final array containing team objects in proper order- that would then be used to simulate a tournament
def map_bracket (ordered_teams, bracket_order)
for i in 0..(bracket_order.length-1)
team=ordered_teams[(bracket_order[i]-1)]
bracket_order[i]=team
end
bracket_order
end
However we don't think about brackets like an array- we think like this (maybe turned 90 degrees)
[1, 2]---------------------2
/ \
[1,4] [2,3]----------------4
/ \ / \
[1,8] [4,5] [2,7] [3,6]------------8
-looks awfully similar to a binary tree...
Binary Trees and Recursion
I attempted to replicate the above in Ruby with binary trees- using an array of each matchup as the node data.
To start I created a BracketNode class and a BracketTree class
class BracketNode
attr_accessor :data, :left, :right
def initialize (data=nil, left=nil, right=nil)
@data=data
@left=left
@right=right
end
end
class BracketTree
attr_reader :root
def initialize (overall_root=nil)
@overall_root=overall_root
end
end
Then I initialized a node with the [1,2] matchup to be used as the root and expand recursively from there.
def build_bracket(node, entrants, curr_level)
if curr_level<=Math.log2(entrants)
node.left = BracketNode.new([node.data[0],((2**curr_level+1)-node.data[0])])
node.right = BracketNode.new([node.data[1],((2**curr_level+1)-node.data[1])])
build_bracket(node.left, entrants, curr_level+1)
build_bracket(node.right, entrants, curr_level+1)
end
nil
end
It looks a little ridiculous- but it's all the same patterns from above- taking seed of each matchup and subtracting it from log2(entrants)+1 to find their opposing seed- this time recursively building bracket nodes as opposed to pushing into an array until desired # of entrants is reached.
Then there were a few helper methods- one to count the height of the tree and another to print all nodes on a current level- by combining those the below function prints all the matchups with a line between each round
def print_all_levels (node)
h=self.height(node)
for i in 1..h
print_level(node, i, 1)
puts "----------------------"
end
end
The final code run to actually create a BracketTree and print it's matchups looks like this for a 64 team bracket
root=BracketNode.new([1,2])
bracket=BracketTree.new(root)
# #start on level "2" as level 1 is the [1,2] (aka the 'final')
bracket.build_bracket(root, 64, 2)
bracket.print_all_levels(root)
It was fun to try and use binary trees again as they are nowhere to be found in ruby- building the bracket tree recursively ultimately served as a great challenge and reminded me once again of the power of recursion. Please leave any feedback or room for improvement in the actual code if you see any!
Thanks for reading,
-Logan
Link to bracket simulator: https://github.com/loganwohlers/Mod2Final
Top comments (0)