From: Dema <demetriusnunes@...>
Date: 2006-12-11T09:20:05+09:00
Subject: Re: Tournament Matchups (#105)

Here is my original solution and a sample run for 10 players.

I decided to follow this simple approach: for the first round, make a
normalized list of all players (by normalized I mean it must be a
potency of 2 - if not, the last slots should be filled with nils until
it is) and pair them picking from the head and the tail of the list.
After that, make a list from the matches (not the players) of the 1st
round and repeat until there are less than 2 matches.

# draw.rb
class Match

  # All matches have an Id, a top player/team and bottom player/team
  attr_reader :id, :top, :bottom

  def initialize(id, top, bottom)
    @id = id
    @top = top
    @bottom = bottom
  end
end

# a Draw is composed of rounds and matches
class Draw
  attr_reader :rounds
  attr_reader :matches

  # here is the generation of the match-ups
  def initialize(players)
    @matches = [] # the list of all matches
    @rounds = {} # the hash of matches for each round

    match = round = 1

    # normalize players count into square potency
    nsqrplayers = 2 ** Math.frexp(players.size - 1).last

    # derive candidates for 1st round, setting byes for top players
    candidates = (1..nsqrplayers).to_a.map { |c| c > players.size ? nil
: players[c-1] }

    while (ncandidates = candidates.size) >= 2
      while !candidates.empty?
        @rounds[round] ||= []

        # setup first x last matches from the candidates list
        @rounds[round] << @matches[match] = Match.new(match,
                                                      candidates.shift,

                                                      candidates.pop)
        match += 1
      end

      # derive candidates for remaining rounds, but now
      # the candidates will appear in the form of match Ids
      # so let's map the candidates from the winners of the previous
matches
      candidates =
(((@rounds[round].first.id)..(@rounds[round].last.id))).to_a.map do |m|

        # was it a bye?
        @matches[m].bottom.nil? ? "#{@matches[m].top}" : "W#{m}"
      end
      round += 1
    end
  end

  def to_s
    buf = ""
    for r in @rounds.keys.sort
      buf << "R#{r}\n"
      for m in @rounds[r]
        buf << "M#{m.id}: #{m.top} x #{m.bottom.nil? ? 'bye' :
m.bottom}\n"
      end
      buf << "\n"
    end
    buf
  end
end

players = (1..10).to_a
puts Draw.new(players).to_s

Here's the sample output:
R1
M1: 1 x bye
M2: 2 x bye
M3: 3 x bye
M4: 4 x bye
M5: 5 x bye
M6: 6 x bye
M7: 7 x 10
M8: 8 x 9

R2
M9: 1 x W8
M10: 2 x W7
M11: 3 x 6
M12: 4 x 5

R3
M13: W9 x W12
M14: W10 x W11

R4
M15: W13 x W14


Ruby Quiz wrote:
> The three rules of Ruby Quiz:
>
> 1.  Please do not post any solutions or spoiler discussion for this quiz until
> 48 hours have passed from the time on this message.
>
> 2.  Support Ruby Quiz by submitting ideas as often as you can:
>
> http://www.rubyquiz.com/
>
> 3.  Enjoy!
>
> Suggestion:  A [QUIZ] in the subject of emails about the problem helps everyone
> on Ruby Talk follow the discussion.  Please reply to the original quiz message,
> if you can.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>
> 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:
>
> 	http://www.crowsdarts.com/brackets/playoff-chart.html
>
> 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.