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:
#! /usr/bin/env ruby
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:
class Symbol
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:
words.map { |word| word.downcase }
to:
words.map(&:downcase)
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:
>> class << Math
>> 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:
>> 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
=> 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:
>> def test_bytes(rounds, players)
>> 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:
def seed; @seed ||= players + Array.new(nbyes, :bye); end
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:
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
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:
(0…3).inject([1, 2, 3, 4, 5, 6, :bye, :bye]) do |memo, unused|
?> p memomemo.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 matchupsmatchups = 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]]]
=> 3matchups
=> [[[[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:
attr_reader :matches
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…