# Tournament Matchups (#105)

**URL:** <https://www.ruby-forum.com/t/tournament-matchups-105/79355>\
**Category:** Ruby\
**Created:** [December 14, 2006, 3:17pm UTC](https://www.ruby-forum.com/t/tournament-matchups-105/79355 "2006-12-14T15:17:44Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [December 14, 2006, 3:17pm UTC](https://www.ruby-forum.com/t/tournament-matchups-105/79355/1 "2006-12-14T15:17:44Z")

</div>

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 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:

```
  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…