by Demetrius Nunes
In a single-elimination tournament, there is usually a previously established ranking for the participating players or teams, such as that the best players or teams are matched against the worst ones. This is done this way so there is a higher chance for the top players/teams to meet in the final.
For example, in a small 8-player tournament, there would be 3 rounds. This first round would be setup like this:
Round 1
1 x 8
2 x 7
3 x 6
4 x 5
This is easy enough. The tough part is arranging the pairing for the following rounds respecting the best vs worst rule, so, imagining that all the favorites won their games, we would have 1x4 and 2x3 in round 2 and then finally 1x2 in the final. For this to happen, the tournament would have to be arranged this way:
R1 R2 R3
============
1
---
|---
--- |
8 |
|---
4 | |
--- | |
|--- |
--- |
5 |
|----
2 |
--- |
|--- |
--- | |
7 | |
|---
3 |
--- |
|---
---
6
If the numbers of players/teams is not a potency of 2, then the top players would have a "bye" in the first round, so, a 6-player draw would go like this:
R1 R2 R3
============
1
---
|---
--- |
bye |
|---
4 | |
--- | |
|--- |
--- |
5 |
|----
2 |
--- |
|--- |
--- | |
bye | |
|---
3 |
--- |
|---
---
6
So, this quiz is about writing a single-elimination tournament generator for any number of players/teams obeying the best vs worst rule in all rounds.
For a quick look at correct answers see this "got-the-job-done" javascript/html implementation at:
We are looking for correct data modeling and calculation, not for correct presentation output of the tournament draw, but it would be nice to implement a #to_s output like the ones seen above (or even better: how about a beautiful RMagick generated image?!). In all cases, keep the model and presentation cleanly separated.
Quiz Summary
Quite a few people took a stab at this problem with some mighty clever code. I'll confess that I spent a fair amount of time in IRb just to understand some of the entries. Perhaps that is instructive in and of itself though, so let me share an exploration of code with you.
I want to take a look at Marshall T. Vandegrift's solution here. It's some clever code that taught me fun new tricks, but I had to play with it a bit to understand all of it. It begins with a simple require:
require 'facet/symbol/to_proc'
# ...
If your not familiar with it, the Facets library is a collection of extensions to Ruby. As we see here, you can hand pick the extensions you will need for your program. Marshall asked for the popular Railsism Symbol#to_proc. The method goes something like:
def to_proc
lambda { |arg| arg.send(self) }
end
end
The version in the Facets library is a bit more powerful than that, but this is all Marshall really needed. The trick here is that Ruby translates a trailing &whatever in a method call to whatever.to_proc(). Thus the above hack allows us to shorthand common iterations like:
to:
Let's get back to Marshall's code now:
class << Math
def log2(n); log(n) / log(2); end
end
# ...
Now I'm sure all you math geeks just looked at that and nodded, but I said, "What's that for?" To find out I decided to play with it in IRb a little:
>> def log2(n); log(n) / log(2); end
>> end
=> nil
>> (1..10).map { |i| Math.log2(i) }
=> [0.0, 1.0, 1.58496250072116, 2.0, 2.32192809488736, 2.58496250072116,
2.8073549220576, 3.0, 3.16992500144231, 3.32192809488736]
>> (1..10).map { |i| Math.log2(i).ceil }
=> [0, 1, 2, 2, 3, 3, 3, 3, 4, 4]
>> puts (1..10).map { |i| "#{i}: #{Math.log2(i).ceil}" }
1: 0
2: 1
3: 2
4: 2
5: 3
6: 3
7: 3
8: 3
9: 4
10: 4
=> nil
Let me talk you through my thought process a bit there. I thought, well that looks like a mathematical function that expects a numerical argument. Let's feed it a handful of numbers and see if I can make sense of the output. Egad, fractions! OK, this doesn't seem like a problem to involve fractions, so we probably need to round up or down. I'll try up. That set of numbers look promising. Let's match them up with the inputs and see if they mean anything to me.
There are only a few numbers in this problem: number of players, number of byes, and number of rounds were all I could think of. Ah yes, number of rounds. Two players need only one game. The quiz listed three rounds for both eight and six player sets. Looks like this is a handy way to calculate the needed number of rounds.
Like I said, I'm sure most of you got to skip my little journey to enlightenment there, but the rest of us have to use the tools we can.
Back to Marshall's code:
class Array
def half_size; size >> 1; end
def top_half; self[0, half_size]; end
def bottom_half; self[half_size, half_size]; end
end
# ...
This time I was pretty sure I knew what the code did, just from the method names if nothing else. I still had questions though. "How does that work with odd sizes?" I asked IRb:
>> def half_size; size >> 1; end
>> def top_half; self[0, half_size]; end
>> def bottom_half; self[half_size, half_size]; end
>> end
=> nil
>> a = (1..5).to_a
=> [1, 2, 3, 4, 5]
>> a.half_size
=> 2
>> a.size / 2
=> 2
>> a.top_half
=> [1, 2]
>> a.bottom_half
=> [3, 4]
>> a.pop
=> 5
>> a
=> [1, 2, 3, 4]
>> a.half_size
=> 2
>> a.top_half
=> [1, 2]
>> a.bottom_half
=> [3, 4]
Answer: It doesn't. Good to know.
To figure out why this doesn't matter, we need the next bit of code:
class Tournament
def initialize(players)
raise "Tournament requires 2 or more players" if players.size < 2
@players = players
@matches = (0...nrounds).inject(seed) do |(memo,)|
memo.top_half.zip(memo.bottom_half.reverse)
end
end
attr_reader :players
attr_reader :matches
def render(renderer = AsciiRenderer)
extend renderer
render_tournament
end
protected
def seed; @seed ||= players + Array.new(nbyes, :bye); end
def nplayers; players.size; end
def nrounds; Math.log2(nplayers).ceil; end
def nbyes; (1 << nrounds) - nplayers; end
end
# ...
My first reaction was, "Hey look at that nrounds() method. I was right!" The second one was, "Ick. Look at the nbyes() method. Marshall knows more math than James." Back to IRb we go:
>> pow_of_2 = 1 << rounds
>> byes = pow_of_2 - players
>> puts "Byes #{byes} (pow_of_2 = #{pow_of_2})"
>> end
=> nil
>> test_bytes(3, 6)
Byes 2 (pow_of_2 = 8)
=> nil
>> test_bytes(3, 8)
Byes 0 (pow_of_2 = 8)
=> nil
>> test_bytes(1, 2)
Byes 0 (pow_of_2 = 2)
=> nil
Bit shifting rounds places to the left appears to give us the power of two equal to the number of players or just above. Handy that. With it we can just pull off the number of players and we have a count of how many byes are needed. Now have another look at how this was put to use:
The seed() turns out to be an Array of players (on top) and byes (at the bottom). Given that, we know that seed().size() will be a power of two which is an even number. That tells us why the Array dividers didn't need to work with odd counts.
It's all coming together. Have one last peek at how the matchups are made:
raise "Tournament requires 2 or more players" if players.size < 2
@players = players
@matches = (0...nrounds).inject(seed) do |(memo,)|
memo.top_half.zip(memo.bottom_half.reverse)
end
end
The entire tournament is arranged there with what gets my vote for the scariest use of inject() I have ever seen. The icky (memo,) construct is used to discard the unused second value, which means inject() is pretty much a times() call here, save that it updates the mutated Array at each step. Here's a study of what exactly is being constructed and a more verbose but hopefully easier to understand way to write it:
?> p memo
>> memo.top_half.zip(memo.bottom_half.reverse)
>> end
[1, 2, 3, 4, 5, 6, :bye, :bye]
[[1, :bye], [2, :bye], [3, 6], [4, 5]]
[[[1, :bye], [4, 5]], [[2, :bye], [3, 6]]]
=> [[[[1, :bye], [4, 5]], [[2, :bye], [3, 6]]]]
>> matchups = [1, 2, 3, 4, 5, 6, :bye, :bye]
=> [1, 2, 3, 4, 5, 6, :bye, :bye]
>> 3.times do
?> p matchups
>> matchups = matchups.top_half.zip(matchups.bottom_half.reverse)
>> end
[1, 2, 3, 4, 5, 6, :bye, :bye]
[[1, :bye], [2, :bye], [3, 6], [4, 5]]
[[[1, :bye], [4, 5]], [[2, :bye], [3, 6]]]
=> 3
>> matchups
=> [[[[1, :bye], [4, 5]], [[2, :bye], [3, 6]]]]
This shows the fascinating Array structure that gets built, nesting each round's matchups. I also tried to break down the operation into a more normal Ruby construct.
At this point, we have the entire tournament planned out. Now it's time to do some drawing.
I'll stop clowning around with IRb at this point and just cover the code normally. I do think it's important to realize what a powerful tool of exploration this can be though. It's great to be able to segment out the elements of code you don't understand and explore what it does by making a few method calls.
How Marshall triggers the rendering code is more cleverness, but with Ruby this time instead of math. Let me refresh your memory:
def render(renderer = AsciiRenderer)
extend renderer
render_tournament
end
The matches() accessor and other utility methods provides all we need to render results. Marshall decides to use those as the methods supporting a rendering mixin. A call to render() then mixes the desired rendering Module into this object and triggers the process. This allows each tournament to use a different renderer.
Here's the renderer included with the code for drawing ASCII charts:
module Tournament::AsciiRenderer
protected
def render_tournament
render_header.concat(render_rounds).join("\n")
end
# ...
The end result, we can see, is just the headers plus each round. Let's dip into those rendering methods:
private
def render_header
[ (1..nrounds).collect { |r| "R#{r}".ljust(width + 1) }.join,
('=' * (nrounds * (width + 1))) ]
end
# ...
The overall rendering process builds an Array of lines, which are join()ed as we saw in render_tournament(). The lines here start the process off with a row of round numbers and a row of equals signs to set them off from the content.
Then we get to round rendering, which is a little more involved:
def render_rounds
render_match(matches.first)
end
def render_match(match)
unless match.kind_of? Array
draw = [ render_player(match), slot1 ]
(@flip = !@flip) ? draw : draw.reverse
else
draw = match.collect do |match_|
render_match(match_)
end.inject do |memo, draw_|
(memo << (' ' * memo.first.size)).concat(draw_)
end
fh = (draw.size - 3) / 4
sh = [ (draw.size + 1) / 4, 2 ].max
draw_ = [ [space]*sh, [flow]*fh, slot, [flow]*fh, [space]*sh ]
draw.zip(draw_.flatten).collect(&:join)
end
end
def render_player(player)
player.to_s.ljust(width)
end
def slot; '|' << ('-' * width); end
def slot1; ('-' * width); end
def flow; '|' << (' ' * width); end
def space; ' ' << (' ' * width); end
def width
@width ||= seed.collect { |x| x.to_s.size }.max;
end
end
# ...
The process begins in render_rounds() which strips an extra layer of nesting off of matches() and makes a hand-off to render_match().
In render_match() the flow is split by a slightly confusing unless/else construct. Arrays (or rounds) are handled in the else clause, which recursively renders each match and then joins the results together with enough slots()s, flow()s, and space()s. Strings and Symbols (or players) are handled in the unless clause. This is mainly just a delegation to render_player() and slot1(), but the line order has to be reversed every other time to make even player names list under the chart bar.
The width() is the helper we have seen used all through the rendering process to determine field width which is just the longest player's name. Note how the value is cached here with the ||= operator, so it only has to be calculated the first time.
All that remains is the code to start us off:
if __FILE__ == $0
puts Tournament.new(ARGV).render
end
ARGV is assumed to be a list of player names in rank order and thus passed to Tournament.new() to build the matches. A call to render() generates the chart which is dumped by puts().
Many of the solutions involved clever code in their own right, so don't forget to look through them. My thanks to all for giving us the fun code to play with and to Marshall for teaching me some math.
Tomorrow we will tackle board setup for a Bobby Fischer created chess variant...
