From: Ruby Quiz <james@...>
Date: 2006-12-14T23:15:57+09:00
Subject: [SUMMARY] Tournament Matchups (#105)

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