Asp Forum - [QUIZ] Tournament Matchups (#105

James Gray

12/8/2006 2:14:00 PM

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

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

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.

17 Answers

Daniel Finnie

12/10/2006 6:04:00 PM

I have some questions about this problem.

First http://www.crowsdarts.com/brackets/playoff-..., for 5
teams, is the output correct? It gives the following match-ups for the
1st round:
1 vs. bye
4 vs. 5
2 vs. 3

Wouldn't the correct answer be:
1 vs. bye
5 vs. 2
4 vs. 3

Also, are there allowed to be any "byes" in the 2nd or greater rounds?

Thanks,
Dan

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

James Gray

12/10/2006 6:17:00 PM

On Dec 10, 2006, at 12:03 PM, Daniel Finnie wrote:

> I have some questions about this problem.
>
> First http://www.crowsdarts.com/brackets/playoff-..., for 5
> teams, is the output correct? It gives the following match-ups for
> the 1st round:
> 1 vs. bye
> 4 vs. 5
> 2 vs. 3
>
> Wouldn't the correct answer be:
> 1 vs. bye
> 5 vs. 2
> 4 vs. 3

Your way seems more correct to me, yes.

> Also, are there allowed to be any "byes" in the 2nd or greater rounds?

I haven't tried the problem myself yet, but I'm pretty sure you only
need them in the first round, if you work out the ordering
correctly. Someone correct me if I'm wrong on that though...

James Edward Gray II

Louis J Scoras

12/10/2006 7:30:00 PM

#!/usr/bin/env ruby
#
# Solution to RubyQuiz 105: Tournament Matchups
# Lou Scoras <louis.j.scoras@gmail.com>
#
# This is a pretty simple solution using a binary tree to represent the
# brackets. Binary trees are a natural way to represent them since two
# teams play one another per in each game. We just need to make sure that
# we keep the trees balanced -- in this case, not because of performance but
# for correctness: i.e. teams shouldn't get more than one 'bye'.

##
# The Bracket class is where all the action takes place. We'll just keep
# adding teams into the Bracket in order of their ranking. By swapping the
# left and right branches after inserts, we can assure that the next team is
# always inserted into the correct position.

class Bracket

##
# The Bracket constructor is trivial in most cases. Since we won't be
# defining a separate Leaf class, we preform a little trickery until there
# are at least two teams added.

def initialize(left=nil,right=nil)
@left = left
@right = right

##
# Count the non-nil entries, if both are non-nil we just set the count
# using the regular method of adding the sub children counts.
# Otherwise, we use the total of non-nil arguments:

c = [@left,@right].inject(0) {|c,i| i.nil?? 0 : 1}

if c < 2
@count = c + 1
else
@count = left.count + right.count + 1
end
end

##
# Insert a team into the bracket. Again this method has special case
# handling for when we don't yet have two teams entered.
#
# Assuming there are two children nodes, we start off by comparing the
# number of elements in each. The non-equal cases are standard fare,
# except that we swap the left and right trees afterward. The reason for
# that being that in the equal case, we favor the right tree. The
# swapping makes sure that new team gets entered into the tree with more
# talent. Since the best teams are generally paired up with the worst, it
# also ensures that lower ranked teams get extra games while the upper
# teams retain the byes.

def insert(team)
@left = leafify(team) and return if @left.nil?
@right = leafify(team) and return if @right.nil?

case @left.count <=> @right.count
when 1
do_insert(:@right, team)
swap!
when -1
do_insert(:@left, team)
swap!
when 0
do_insert(:@right, team)
end
@count += 1
end

##
# Just a helper to switch the two sub-trees.

def swap!
@left, @right = @right, @left
end

##
# do_insert is a helper for performing the inserts on the subtrees. The
# only reason it's needed is because there isn't an explicit leaf class.
# We'll check to see if it's a leaf and if it is, create a new node
# combining the new team with the single leaf node. Notice how the right
# subtree is still favored.

def do_insert(thing, team)
target = instance_variable_get(thing)
if target.leaf?
instance_variable_set(thing,
self.class.new(target, leafify(team))
)
else
target.insert(team)
end
end

##
# We need some way to view the matchups.

def to_s
"[#@left vs. #@right]"
end

private :do_insert
attr_reader :count

##
# None of our class should be a leaf. We'll handle the polymorphism by
# mucking around with the team parameters passed in.

def leaf?; false end

##
# To get a leaf node, we just mixin two trivial functions for whatever
# class is chosen to represent the teams. This is probably just sloppy OO
# design, but it sure is convienient.

def leafify(n)
n.extend(Leaf)
end
end

##
# These are the functions mixed into the team class.

module Leaf
def count; 1 end
def leaf?; true end
end

##
# Just for some flavor we'll add some team names. They aren't really in any
# particular order -- except for Ruby =) And maybe Haskell...

Teams = %w{ Rubies Haskells Lisps Perls
Schemes Korns OCamls Pythons
Javas Cs Basics PHPs JavaScripts
SASes Bashes Erlangs SQLs Logos
Fortrans Awks Luas Smalltalks }

def team(i)
str = Teams[i-1] ? (" " + Teams[i-1]) : ""
end

##
# The main program is boring. Just get the number of teams from the command
# line and build the bracket. Notice how we're using a string to represent
# the teams. This is fine and the bracket just mixes in the sential
# functions. One drawback to this is that you can't use a class that is
# represented by an intermediate value. Try it with a Fixnum and you'll see
# what I mean.

bracket = Bracket.new
(1..Integer(ARGV[0])).each do |i|
bracket.insert(i.to_s + team(i)) # Can't extend Fixnum
end

##
# Print the bracket using the to_s incredibly simple to_s method above.

puts bracket

Louis J Scoras

12/10/2006 7:36:00 PM

On 12/10/06, Daniel Finnie <danfinnie@optonline.net> wrote:
> I have some questions about this problem.
>
> First http://www.crowsdarts.com/brackets/playoff-..., for 5
> teams, is the output correct? It gives the following match-ups for the
> 1st round:
> 1 vs. bye
> 4 vs. 5
> 2 vs. 3

I think you're misreading this. It says that all teams have a 'bye'
in the first round excepting teams 4 and 5. You could argue that the
correct answer would have the least amount of 'bye's in it, but the
quiz I don't think mentions that.

--
Lou.

Daniel Finnie

12/10/2006 7:45:00 PM

I assumed the extended bracket for 2 and 3 was done on purpose by the
program to have the output look nicer.

1 vs. bye
4 vs. 5
2 vs. 3
This has 4 games, a power of 2.

1 vs. bye
2 vs. bye
3 vs. bye
4 vs. 5
This has 2 games, a power of 2, but doing it this way seems stupid,
especially when for other problems it seems to give solutions with the
least amount of byes, or the highest power of 2 possible games.

Basically, either way you interpret the online version, I think
something's wrong.

Dan

Louis J Scoras wrote:
> On 12/10/06, Daniel Finnie <danfinnie@optonline.net> wrote:
>> I have some questions about this problem.
>>
>> First http://www.crowsdarts.com/brackets/playoff-..., for 5
>> teams, is the output correct? It gives the following match-ups for the
>> 1st round:
>> 1 vs. bye
>> 4 vs. 5
>> 2 vs. 3
>
> I think you're misreading this. It says that all teams have a 'bye'
> in the first round excepting teams 4 and 5. You could argue that the
> correct answer would have the least amount of 'bye's in it, but the
> quiz I don't think mentions that.
>
>

Brock Lee

12/10/2006 9:14:00 PM

The goal is not to minimize the number of byes. The goal is to
maximize fairness and competetiveness.

In the last round, when it's down to two teams, the greater the
discrepency in the number of games those two teams have played in the
tournment the less fair it is and the less competetive it is.
Therefore those final two teams should have either played the same
number of games or differ by at most one game played.

If byes can occur after the first round, then that stipulation will not
necessarily be true.

Therefore, byes can only occur in the first round. By the time it gets
to the second round, the number of teams who are still alive in the
tournament should be a power of two.

Thus this interpretation is correct:
* 1 vs. bye
* 2 vs. bye
* 3 vs. bye
* 4 vs. 5

And that's what http://www.crowsdarts.com/brackets/playoff-...
produces.

Brock Lee

Daniel Finnie wrote:
> I assumed the extended bracket for 2 and 3 was done on purpose by the
> program to have the output look nicer.
>
> 1 vs. bye
> 4 vs. 5
> 2 vs. 3
> This has 4 games, a power of 2.
>
> 1 vs. bye
> 2 vs. bye
> 3 vs. bye
> 4 vs. 5
> This has 2 games, a power of 2, but doing it this way seems stupid,
> especially when for other problems it seems to give solutions with the
> least amount of byes, or the highest power of 2 possible games.
>
> Basically, either way you interpret the online version, I think
> something's wrong.
>
> Dan

Fred Wulff

12/10/2006 11:13:00 PM

I wanted to see how simply I could do it from a code perspective, so I
just used nested arrays to represent the tree structure. I think it
actually turned out pretty well. Turning it into an actual tree
results in pretty similar code, removing the niceness of zip, but
making the recursive functions a little OOPier.

-Fred

# Generate a single elimination tournament for N teams, numbered 1..N
def generate_tournament_bracket(num_teams)
# Number of byes = 2**n - num_teams where n is the smallest value
such the number is positive
num_byes = 2**((Math.log(num_teams)/Math.log(2)).ceil) - num_teams

# Generate bye first round "matching"s
byes = (1..num_byes).map{|i| [i]}

# Generate all the other matchings
current_round = ((num_byes + 1)..num_teams).to_a

# Keep going until we have a winner
while current_round.size > 1
# Generate the next round matchings by taking all byes, if any,
from the byes array.
# Then we exploit the fact that our array is always sorted by seed
of winner to find the next
# pairings
current_round = byes.slice!(0..-1) +
current_round[0...current_round.size/2].zip(current_round[current_round.size/2..-1].reverse)
end
return current_round[0]
end

# Outputs any matches in the subtree of current_matching using
match_num as the first
# available match_number
# Returns the match number of current_matching
def output_bracket(current_matching, match_num = 1)
# Since we never go until we get current_matching.kind_of?(Fixnum),
we must have a bye
# which means we're first round
if current_matching.size == 1
puts "Match #{match_num}: #{current_matching[0]} vs Bye"
return match_num

# First round detection
elsif current_matching[0].kind_of?(Fixnum)
puts "Match #{match_num}: #{current_matching[0]} vs #{current_matching[1]}"
return match_num

# Some other round, so we need to recurse down
else
left_match = output_bracket(current_matching[0], match_num)
right_match = output_bracket(current_matching[1], left_match + 1)
match_num = right_match + 1

puts "Match #{match_num}: Winner of Match #{left_match} vs Winner
of Match #{right_match}"

return match_num
end
end

output_bracket(generate_tournament_bracket(5))

Dema

12/11/2006 12:19:00 AM

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

Eric I.

12/11/2006 2:38:00 AM

Below you'll find my solution. The code to create the binary tree is
pretty small. The code to produce the text version of the tournament
tree is not so small, however. Oh well...

Eric

SAMPLE OTUPUT

$ ruby tournament.rb 5
R1 R2 R3
============
1
---+
+---+
---+ |
bye |
+---+
4 | |
---+ | |
+---+ |
---+ |
5 |
+---
2 |
---+ |
+---+ |
---+ | |
bye | |
+---+
3 |
---+ |
+---+
---+
bye

SOLUTION

# Solution for Ruby Quiz #105
# Author: Eric I.
# December 10, 2006
# www.learnruby.com

class Numeric
# A monkey-patched convenience method to compute the maximum of two
# numbers.
def max(other)
if self >= other : self
else other
end
end
end

class Integer
# A monkey-patched method to compute the gray code of an integer.
The
# gray code has properties that make it helpful to the tournament
problem.
def gray_code
self ^ (self >> 1)
end
end

# A tournament is really a node in a binary tree. The value in each
# node contains the ranking of the best ranking team contained in the
# tournament tree below.
class Tournament
attr_reader :ranking

def initialize(ranking)
@ranking = ranking
end

# Creates a tournament with the given number of teams.
def self.create(teams)
# create the initial node
head_node = Tournament.new(1)

# insert additional nodes for each further team
for ranking in 2..teams
head_node.add_team(ranking)
end

head_node
end

# Adds a team with the given ranking to the tournament. It turns out
# that the gray code of the ranking-1 has a bit pattern that
conveniently
# helps us descend the binary tree to the appropriate place at which
to
# put the team.
def add_team(ranking)
add_team_help(ranking, (ranking - 1).gray_code)
end

# Returns the number of rounds in the tournament. This is determined
by
# taking the max of the depths of the two sub-trees and adding one.
def rounds
unless @left : 0
else 1 + (@left.rounds.max(@right.rounds))
end
end

# Returns the pairs playing at a given round. A round number of 1 is
# the first round played and therefore the bottom-most layer of the
tree.
def round(level)
round_help(rounds - level)
end

# Converts the tournament tree into a String representation.
def to_s
lines = [] # store the result as an array of lines initially

# create the lowest layer of the tree representing the first round
round(1).each do |game|
lines << game[0].to_s.rjust(3)
lines << "---"
lines << " "
lines << "---"
lines << game[1].to_s.rjust(3)
lines << " "
end
lines.pop # last line, which just contains blanks, is not needed

# the rest of the text tree is made through textual operations
# by connecting teams playing with veritcal lines, then branching
# horizontally to the next level, and then extending those branches
begin
count = to_s_connect(lines)
to_s_branch(lines)
3.times { to_s_extend(lines) }
end until count == 1

header_string + lines.join("\n")
end

protected

# Recursively descends the tree to place a team with a new ranking.
# Ultimately it will create two new nodes and insert them into the
# tree representing itself and the team to be played. When
# descending the three, the bits in the gray code of the ranking
# from least-significant to most-significant indicate which branch
# to take.
def add_team_help(ranking, gray_code)
if @left == nil
# bottomed out; create two new nodes
@left = Tournament.new(@ranking)
@right = Tournament.new(ranking)
elsif gray_code % 2 == 0
# bit in gray code indicates the left branch
@left.add_team_help(ranking, gray_code >> 1)
else
# bit in gray code indicates the right branch
@right.add_team_help(ranking, gray_code >> 1)
end
end

# Returns the teams playing at the given round level. The parameter
# is actually the desired round subtracted from the number of
# rounds. That way we know we're at the right level when it reaches
# zero. It can be the case where a given branch does not have
# enough levels; that indicates a "bye" for a good-ranking team.
def round_help(reverse_level)
if @left == nil : [[@ranking, "bye"]]
elsif reverse_level == 0 : [[@left.ranking, @right.ranking]]
else @left.round_help(reverse_level - 1) +
@right.round_help(reverse_level - 1)
end
end

# Creates a simple pair of lines showing the round numbers; this
helps
# in the interpretation of the text-tree below.
def header_string
result = (1..rounds).to_a.inject("") do |collect, round|
collect + "R#{round}".center(4)
end
result + "\n" + "=" * result.length + "\n"
end

# Creates vertical lines used to indicate a game and that connect
# the horizontal lines that refer to teams. The teams referred to
# are either from the first round or that have won the previous
# round.
def to_s_connect(lines)
count = 0
connect = false
lines.each do |line|
if line[-1, 1] == "-"
line << "+"
connect = !connect
count += 1 if connect
elsif connect
line << "|"
else
line << " "
end
end
count
end

# From the vertical lines used to represent a game, this places a
# horizontal line in the *middle* of it which indicates the winning
# team. Except for the final round, these horizontal lines will be
# used to create a game at the next round.
def to_s_branch(lines)
range_began = false
lines.each_index do |i|
if lines[i][-1, 1] == "|"
range_began = i unless range_began
elsif range_began
lines[(i + range_began - 1)/2][-1] = "+"
range_began = false
end
#lines[i] << " "
end
end

# Extends the horizontal lines by one character.
def to_s_extend(lines)
lines.each do |line|
if line =~ /(-| \+)$/
line << "-"
else
line << " "
end
end
end
end

if ARGV.length != 1
$stderr.puts "Usage: #{$0} team-count"
exit 1
end

tournament = Tournament.create(ARGV[0].to_i)

puts tournament

Max Muermann

12/11/2006 3:13:00 AM

Here's my solution. It assumes that the teams are ranked by skill. I
wanted to see whether this could be done in-place and am doing some
recursive swapping to arrive at the correct solution.

There's an additional pass through the array at the end to remove
cases where two teams have received byes for the first round and are
scheduled to play each other in the second round.
No pretty printing - sorry. Byes are nil in the resulting array of pairings.

Here are some results:

"8 players:"
[[1, 8], [4, 5], [2, 7], [3, 6]]

"6 players:"
[[1, nil], [4, 5], [2, nil], [3, 6]]

"16 players:"
[[1, 16], [8, 9], [4, 13], [5, 12], [2, 15], [7, 10], [3, 14], [6, 11]]

"11 players:"
[[1, nil], [8, 9], [4, 5], [2, nil], [7, 10], [3, nil], [6, 11]]

"32 players:"
[[1, 32], [16, 17], [8, 25], [9, 24], [4, 29], [13, 20], [5, 28], [12,
21], [2, 31], [15, 18], [7, 26], [10, 23], [3, 30], [14, 19], [6, 27],
[11, 22]]

Cheers,
Max

require 'enumerator'

# swap the second quarter of an array with the last quarter
def swap_interleaved(a)
n = a.size >> 2
a[n..2*n-1],a[3*n..4*n-1] = a[3*n..4*n-1],a[n..2*n-1]
end

# swap the third quarter of an array with the last quarter
def swap(a)
n = a.size >> 2
a[2*n..3*n-1],a[3*n..4*n-1] = a[3*n..4*n-1],a[2*n..3*n-1]
end

# for the given array, swap_interleaved, then swap
# if level is not reached, split array in half and recurse for both halves
def rec(a, level)
swap_interleaved a
swap(a)
if (level>0)
a[0..a.size/2-1] = rec(a[0..a.size/2-1], level-1)
a[a.size/2..-1] = rec(a[a.size/2..-1], level-1)
end
a
end

def match_up(num_players)
# match up first-round pairings
n = (Math.log(num_players-1)/Math.log(2)).to_i+1

# new array (2**n in size)
a = Array.new(2**n)

# add players
a[0..num_players-1] = (1..num_players).to_a

# make first-round pairings
a = a[0..a.size/2-1].zip(a[a.size/2..-1].reverse)

# recurse
(n-3).downto(0) do |l|
rec(a,l)
end

# remove double byes
result = []
a.each_slice(2) do |a,b|
if a[1] || b[1]
result << a << b
else
result << [a[0],b[0]]
end
end
result
end

p "8 players:"
p match_up(8)

p "6 players:"
p match_up(6)

p "16 players:"
p match_up(16)

p "11 players:"
p match_up(11)

p "32 players:"
p match_up(32)

comp.lang.ruby

[QUIZ] Tournament Matchups (#105

James Gray

Daniel Finnie

James Gray

Louis J Scoras

Louis J Scoras

Daniel Finnie

Brock Lee

Fred Wulff

Dema

Eric I.

Max Muermann

x Login to ForumsZone