Tournament Matchups (#105)

Ruby
1

The three rules of Ruby Q.:

  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 Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

  1. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby T. 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.

2

I have some questions about this problem.

First http://www.crowsdarts.com/brackets/playoff-chart.html, 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

3

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

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

4

On 12/10/06, Daniel F. [email protected] wrote:

I have some questions about this problem.

First http://www.crowsdarts.com/brackets/playoff-chart.html, 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.

5

#!/usr/bin/env ruby

Solution to RubyQuiz 105: Tournament Matchups

Lou S. [email protected]

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

6

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

7

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-chart.html
produces.

Brock Lee

8

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

9

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

10

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

11

Hi,

I am new to the quizzes and also more or less new to ruby. I would
appreciate any comments on my “unrubyness”, and thanks in advance. I
prefer
1<<n to 2**n although I guess they are implemented similarly.

I am attaching my solution.
Let n be the number of participants and k be the power of 2 following n
(or
n if it is a power of 2). Let p=log2(k).
The tournament (in my code) is understood as a binary tree of
“expected”
matches starting with the final (expected to be [1,2] the best against
the
second-best). Assume we have computed all the matches up to level i-1
(i=2
are the semi-finals, i=3 quarter-finals…), which are r=2**(i-1)
matches:
m_1, …, m_r (notice I start counting at 1). Let us compute the i-level
matches, which are 2**i, call them n_1,…,n_2r . The algorithm is:
Let l= (l_1,…,l_2r) = (m_11, m_12, m_21, m_22, …, m_r2) the list of
players at level i-1 ordered as the matches say (i.e., in the
semi-finals:
(1,4,2,5)

Let INDEX = 2**(i)+1
Let j = 1
STEP:
Match n_j = [l_j, OP_j] where l_j + OP_j = INDEX
j++
GOTO STEP unless j > 2r
return (n_1,…,n2r)

Actually, one can do a better ordering (which puts 1 at the top and 2 at
the
bottom of every tree), which is what I have implemented.
In my code, the complete tournament is kept in memory as a list of
1 + 2 +… +2p
matches. Different levels (i) can be distinguished by starting to count
at
2(i-1)-1

As you will see, the code looks somewhat hackish because there are too
many
2** and off-by-one counts. However, I think this preserves the “natural”
structure of the data without using strong stuff like nested lists of
different lengths, etc… (And it is obviously more challenging to
program
this way
:slight_smile:

If you create a Tournament with a number, you get the numbers as the
labels.
If you create it with a list, it is understood as an ordered (according
to
rank) list of the participants. Labels (and emptpy spaces) are then
given
the maximum length of the names.

Example:
one|
|-----|
four| |
|-----
three| |
|-----|
two|

(notice the “nice” 1-at the top 2-at the bottom ordering).

12

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…2n-1],a[3n…4n-1] = a[3n…4n-1],a[n…2n-1]
end

swap the third quarter of an array with the last quarter

def swap(a)
n = a.size >> 2
a[2n…3n-1],a[3n…4n-1] = a[3n…4n-1],a[2n…3n-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)

13

Here is my solution without the tree display.

14

Well, unfortunately, I don’t have time to generate the chart, but it
was easy enough to generate the pairings… This could probably be
easily golfed, but I figured just leave it be.

The output is “stacked” array pairs… What I mean by that is that the
top array has two items: left and right. Each of those items is an
array of two items: left and right… etc until you get down to the
leaves. A pair like [1, 2] means “Team 1 vs Team 2”, while a pair
like [6, nil] means “Team 6 gets a bye.”

class Integer
def ceilPow2
n = self - 1
i = 1
until (n >> i).zero?
n |= (n >> i)
i *= 2
end
n += 1
end

def even?
(self % 2).zero?
end
end

class Array
def fold
raise ArgumentError unless size.even?
h = size / 2
self[0,h].zip(self[h,h].reverse)
end
end

def matchup(n)
raise ArgumentError unless n > 0

byes = n.ceilPow2 - n
mups = (1…n).to_a + [nil] * byes

until mups.size == 1
mups = mups.fold
end

mups[0]
end

def report(mups)

Here is where you could do tree output or similar… but I’ve no

time.
p mups
end

numTeams = (ARGV[0] || 23).to_i
if numTeams < 2
puts “C’mon, that’s not much of a competition…”
else
matchUps = matchup(numTeams)
report(matchUps)
end

15

Please find my solution hereafter, I somehow do not like it because it
is
unreadable, I wanted to show what ruby can do and that it can do it in
different ways, i liked the Quiz, save the output part, which was a
chellange but not really ruby specificly, well that is why my solution
is so
unreadable, a readable solution might not differ very much from
Smalltalk or
Java, structurally I mean :wink:
Thx for the Quiz.

665/167 > cat screen.rb

class Screen
def initialize size, &blk
@lines = Array.new( size ){ [] }
instance_eval &blk if blk
end
private
def at c, pos_line, pos_col
@lines[pos_line-1][pos_col-1] = c
end
def out stream=$stdout
stream.puts self
end
def str_at s, pos_line, pos_col
s.each_byte do
|c|
at c, pos_line, pos_col
pos_col += 1
end
end
def str_align s, align, pos_line, pos_col
str_at “%#{align}s” % s.to_s, pos_line, pos_col
end
def to_s
@lines.map{ |line| line.map{ |c| c.nil? ? " " :
c.chr}.join}.join("\n")
end
end

666/168 > cat sol.rb
require ‘screen’
class Tournament
def initialize n
@n = n.to_i
abort “illegal number #@n” unless @n > 0
@outputs = []
[0…(@n - 1).to_s(2).length].inject([0]){
|pairs,n|
@outputs.unshift pairs
pairs.map{|p| [p, ( 1 << n ) * 2 - 1 -
p]}.flatten
}
@outputs.map!{ |col| col.map!{|i| i < @n ? i + 1 : :bye}
}
end
def print
data = @outputs
Screen.new data.first.length * 2 do
data.each_with_index do
|output, col|
output.each_with_index do
|player, row|
main_row = 2**col +
row2**(col+1)
str_align player, 4, main_row,
6col+5
str_at "-"5 << “+”, main_row,
6col+9 unless
output.length == 1
if col > 1 then
(2**(col-1)-1).times do
|t|
at ?|, main_row
-1-t, 6col+8
at ?|, main_row
+1+t, 6*col+8
end
end

                            end

                    end
                    out
            end
    end

end

Tournament.new( ARGV.first || “14” ).print

Robert

–
“The real romance is out ahead and yet to come. The computer revolution
hasn’t started yet. Don’t be misled by the enormous flow of money into
bad
defacto standards for unsophisticated buyers using poor adaptations of
incomplete ideas.”

  • Alan Kay
16

Ruby Q. wrote:

Round 1
1 x 8
2 x 7
3 x 6
4 x 5

Inf = 999

def find_best x
Array( x ).flatten.min
end

class Array
def partition_teams
t = sort_by{|x| find_best( x ) }
[ t[0,t.size/2], t[t.size/2…-1].reverse ]
end
end

num_teams = ARGV.shift.to_i

n = 1
begin n *= 2 end until n >= num_teams
teams = (1…num_teams).to_a + [Inf] * (n - num_teams)

while teams.size > 2 do
teams = teams.partition_teams.transpose
end
f = nil
p teams.flatten.partition{f=!f}.transpose

17

Hi,

I have a tendency to over-engineer things, so I intentionally tried to
keep this simple. Given the quiz requirements, it seemed simplest to
represent the match-tree as a collection of nested arrays. The
presentation code is slightly clever in that it dynamically mixes a
particular renderer module into the tournament to be rendered.

  • Sample run

$ ruby tournament.rb 1 2 3 4 5
R1 R2 R3

1

—
bye 
   |---

4 | |
— | |

—
5 
       |---
2
—
—
bye 
   |---
3
—

bye

  • Code

#! /usr/bin/env ruby

require ‘facet/symbol/to_proc’

class << Math
def log2(n); log(n) / log(2); end
end

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

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

module Tournament::AsciiRenderer
protected
def render_tournament
render_header.concat(render_rounds).join("\n")
end

private
def render_header
[ (1…nrounds).collect { |r| “R#{r}”.ljust(width + 1) }.join,
(’=’ * (nrounds * (width + 1))) ]
end

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

if FILE == $0
puts Tournament.new(ARGV).render
end

-Marshall

18

On Dec 12, 2006, at 6:45 PM, William J. wrote:

Inf = 999

Inf = 1.0 / 0.0

?

James Edward G. II

19

James Edward G. II wrote:

On Dec 12, 2006, at 6:45 PM, William J. wrote:

Inf = 999

Inf = 1.0 / 0.0

?

I’ve always found this outcome annoying. I often wonder how many
programs
silently fail, that hide division by zero errors by way of this
assignment.

It has one advantage. Infinity isn’t a number, and this assignment
clearly
honors that fact:

inf = 1.0 / 0.0 # Infinity

q = inf / inf # NaN

20

William J. wrote:

round would be setup like this:
def find_best x
num_teams = ARGV.shift.to_i

n = 1
begin n *= 2 end until n >= num_teams
teams = (1…num_teams).to_a + [Inf] * (n - num_teams)

while teams.size > 2 do
teams = teams.partition_teams.transpose
end
f = nil
p teams.flatten.partition{f=!f}.transpose

Simpler:

num_teams = ARGV.shift.to_i

n = 1 ; begin n *= 2 end until n >= num_teams
teams = (1…num_teams).to_a + [“bye”] * (n - num_teams)

while (n = teams.size) > 2 do
teams = teams[0, n/2].zip( teams[n/2 … -1].reverse )
end
p teams.flatten.partition{n=!n}.reverse.transpose

"The most valuable of all talents is that of never using two words
when one will do. "
-Thomas Jefferson

"Programmers are always surrounded by complexity; we cannot avoid
it… If our basic tool, the language in which we design and code
our programs, is also complicated, the language itself becomes part
of the problem rather than part of its solution. "
-C. A. R. Hoare (1980 Turing Award Lecture)

“To attain knowledge, add things every day.
To attain wisdom, remove things every day.”
-Lao-tse

"Perfection is attained, not when there is nothing left to add, but
when there is nothing left to take away. "
-Antoine de Saint-Exupery