Tournament::Bracket

Class representing a bracket in a tournament.

Constants

UNKNOWN_TEAM: Marker for an unknown team

Attributes

name[R]

The name of the bracket

teams[R]

The teams in the bracket

rounds[R]

The number of rounds in the bracket

winners[R]

The winners of each game in the bracket

Public Class Methods

new(teams = nil) click to toggle source

Creates a new bracket with the given teams

    # File lib/tournament/bracket.rb, line 16
16:   def initialize(teams = nil)
17:     @teams = teams || [:t1, :t2, :t3, :t4, :t5, :t6, :t7, :t8, :t9, :t10, :t11, :t12, :t13, :t14, :t15, :t16]
18:     @rounds = (Math.log(@teams.size)/Math.log(2)).to_i
19:     @winners = [@teams] + (1..@rounds).map do |r|
20:       [UNKNOWN_TEAM] * games_in_round(r)
21:     end
22:   end

random_bracket(teams = nil) click to toggle source

Generates a bracket for the provided teams with a random winner for each game.

     # File lib/tournament/bracket.rb, line 326
326:   def self.random_bracket(teams = nil)
327:     b = Tournament::Bracket.new(teams)
328:     1.upto(b.rounds) do |r|
329:       1.upto(b.games_in_round(r)) { |g| b.set_winner(r, g, b.matchup(r, g)[rand(2)]) }
330:     end
331:     return b
332:   end

Private Class Methods

jbin(num, size = 8) click to toggle source

(Not documented)

     # File lib/tournament/bracket.rb, line 336
336:   def self.jbin(num, size = 8)
337:     return num.to_s(2).rjust(size, '0')
338:   end

Public Instance Methods

bracket_for(possibility) click to toggle source

Given a binary possibility number, compute the bracket that would result.

     # File lib/tournament/bracket.rb, line 172
172:   def bracket_for(possibility)
173:     pick_bracket = Tournament::Bracket.new(self.teams)
174:     round = 1
175:     while round <= pick_bracket.rounds
176:       gir = pick_bracket.games_in_round(round)
177:       game = 1
178:       while game <= gir
179:         matchup = pick_bracket.matchup(round, game)
180:         mask = 1 << (gir - game)
181:         # Shift for round
182:         mask = mask << (2 ** (pick_bracket.rounds - round) - 1)
183:         pick = (mask & possibility) > 0 ? 1 : 0
184:         #puts "round #{round} game #{game} mask #{Tournament::Bracket.jbin(mask)} poss: #{Tournament::Bracket.jbin(possibility)} pick #{pick} winner #{matchup[pick]}"
185:         pick_bracket.set_winner(round, game, matchup[pick])
186:         game += 1
187:       end
188:       round += 1
189:     end
190:     return pick_bracket
191:   end

champion() click to toggle source

Returns the champion of this bracket

     # File lib/tournament/bracket.rb, line 260
260:   def champion
261:     return @winners[@rounds][0]
262:   end

complete?() click to toggle source

Returns true if all games have been decided

    # File lib/tournament/bracket.rb, line 65
65:   def complete?
66:     round = 0
67:     while round < self.rounds
68:       return false if @winners[round+1].any? {|t| t == UNKNOWN_TEAM}
69:       round += 1
70:     end
71:     return true
72:   end

each_possibility() click to toggle source

Iterates over each possiblity by representing the possibility as a binary number and yielding each number to the caller’s block. The binary number is formed by assuming each game is a bit. If the first team in the matchup wins, the bit is set to 0. If the second team in the matchup wins, the bit is set to

repeat for each round and the entire bracket result can be represented.

As an example, consider a 8 team bracket:

  Round 0:    t1  t2    t3  t4   t5  t6    t7  t8    Bits
        1:      t1        t4       t6        t7     0 1 1 0
        2:           t4                 t6            1 0
        3:                    t6                       1

  final binary number: 0110101

If no games have been played, we can represent each possibility by every possible 7 bit binary number.

     # File lib/tournament/bracket.rb, line 100
100:   def each_possibility
101:     # bit masks of games that have been played
102:     # played_mask is for any game where a winner has been determined
103:     # first is a mask where the first of the matched teams won
104:     # second is a mask where the second of the matched teams won
105:     shift = 0
106:     round = @rounds
107:     played_mask, winners, left_mask = @winners[1..-1].reverse.inject([0,0,0]) do |masks, round_winners|
108:       game = games_in_round(round)
109:       round_winners.reverse.each do |game_winner|
110:         #puts "checking matchup of round #{round} game #{game} winner #{game_winner} matchup #{matchup(round,game)}"
111:         val = 1 << shift
112:         if UNKNOWN_TEAM != game_winner
113:           # played mask
114:           masks[0] = masks[0] | val
115:           # winners mask
116:           if matchup(round,game).index(game_winner) == 1
117:             masks[1] = masks[1] | val
118:           end
119:         else
120:           # games left mask
121:           masks[2] = masks[2] | val
122:         end
123:         shift += 1
124:         game -= 1
125:       end
126:       round -= 1
127:       masks
128:     end
129:     #puts "played mask: #{Tournament::Bracket.jbin(played_mask, teams.size - 1)}"
130:     #puts "  left mask: #{Tournament::Bracket.jbin(left_mask, teams.size - 1)} #{left_mask}"
131:     #puts "    winners: #{Tournament::Bracket.jbin(winners, teams.size - 1)}"
132: 
133:     # for the games left mask, figure out which bits are 1 and what
134:     # their index is.  If left mask is 1001, the shifts array would be
135:     # [0, 3].  If left mask is 1111, the shifts array would be
136:     # [0, 1, 2, 3]
137:     count = 0
138:     shifts = []
139:     Tournament::Bracket.jbin(left_mask, teams.size - 1).reverse.split('').each do |c|
140:       if c == '1'
141:         shifts << count
142:       end
143:       count += 1
144:     end
145: 
146:     #puts "    shifts: #{shifts.inspect}"
147: 
148:     # Figure out the number of possibilities.  This is simply
149:     # 2 ** shifts.size
150:     num_possibilities = 2 ** shifts.size
151:     #num_possibilities = 0
152:     #shifts.size.times { |n| num_possibilities |= (1 << n) }
153: 
154:     #puts "Checking #{num_possibilities} (#{number_of_outcomes}) possible outcomes."
155:     possibility = num_possibilities - 1
156:     while possibility >= 0
157:       #puts "    possibility: #{Tournament::Bracket.jbin(possibility, teams.size - 1)}"
158:       real_poss = 0
159:       shifts.each_with_index do |s, i|
160:         real_poss |= (((possibility & (1 << i)) > 0 ? 1 : 0) << s)
161:       end
162:       #puts "    real_poss: #{Tournament::Bracket.jbin(real_poss, teams.size - 1)}"
163:       real_poss = winners | real_poss
164:       #puts "    real_poss: #{Tournament::Bracket.jbin(real_poss, teams.size - 1)}"
165:       yield(real_poss)
166:       possibility -= 1
167:     end
168:   end

each_possible_bracket() click to toggle source

For each possible outcome remaining in the pool, generates a bracket representing that outcome and yields it to the caller’s block. This can take a very long time with more than about 22 teams left.

    # File lib/tournament/bracket.rb, line 47
47:   def each_possible_bracket
48:     puts "WARNING: This is likely going to take a very long time ... " if teams_left > 21
49:     each_possibility do |possibility|
50:       yield(bracket_for(possibility))
51:     end
52:   end

games_in_round(round) click to toggle source

Returns the number of games in the given round

     # File lib/tournament/bracket.rb, line 206
206:   def games_in_round(round)
207:     return @teams.size / 2 ** round
208:   end

games_played() click to toggle source

Returns the number of games that have been decided in the bracket

    # File lib/tournament/bracket.rb, line 40
40:   def games_played
41:     @winners[1..-1].inject(0) { |sum, arr| sum += arr.inject(0) {|sum2, t| sum2 += (t != UNKNOWN_TEAM ? 1 : 0) } }
42:   end

inspect() click to toggle source

Pretty print.

     # File lib/tournament/bracket.rb, line 252
252:   def inspect
253:     str = ""
254:     1.upto(rounds) do |r| str << "round #{r}: games: #{games_in_round(r)}: matchups: #{(1..games_in_round(r)).map{|g| matchup(r,g)}.inspect}\n" end
255:     str << "Champion: #{champion.inspect}"
256:     return str
257:   end

matchup(round, game) click to toggle source

Returns a two element array containing the Teams in the matchup for the given round and game

     # File lib/tournament/bracket.rb, line 195
195:   def matchup(round, game)
196:     return @winners[round-1][(game-1)*2..(game-1)*2+1]
197:   end

maximum_score(other_bracket, scoring_strategy) click to toggle source

Compute the maximum possible score if all remaining picks in this bracket turn out to be correct using the given scoring strategy.

     # File lib/tournament/bracket.rb, line 266
266:   def maximum_score(other_bracket, scoring_strategy)
267:     score = 0
268:     round = 1
269:     while round <= self.rounds
270:       games_in_round = self.games_in_round(round)
271:       game = 1
272:       while game <= games_in_round
273:         winner, loser = other_bracket.winner_and_loser(round, game)
274:         pick = self.winner(round, game)
275:         winner = pick if winner == UNKNOWN_TEAM && other_bracket.still_alive?(pick)
276:         score += scoring_strategy.score(pick, winner, loser, round)
277:         game += 1
278:       end
279:       round += 1
280:     end
281:     return score
282:   end

number_of_outcomes() click to toggle source

Returns the number of possible outcomes for the bracket

    # File lib/tournament/bracket.rb, line 80
80:   def number_of_outcomes
81:     @number_of_outcomes ||= (2 ** (self.teams_left)) / 2
82:   end

number_rounds_complete() click to toggle source

Returns the number of rounds that have been completed

    # File lib/tournament/bracket.rb, line 55
55:   def number_rounds_complete
56:     round = 0
57:     while round < self.rounds
58:       break if @winners[round+1].any? {|t| t == UNKNOWN_TEAM}
59:       round += 1
60:     end
61:     return round  
62:   end

pick_correct(round, game, team) click to toggle source

Returns true if the given team was the winner of the round and game

     # File lib/tournament/bracket.rb, line 201
201:   def pick_correct(round, game, team)
202:     return team != UNKNOWN_TEAM && team == winner(round, game)
203:   end

round_and_game(overall_game) click to toggle source

Given a overall game number, return the round and round game number

     # File lib/tournament/bracket.rb, line 231
231:   def round_and_game(overall_game)
232:     1.upto(rounds) do |r|
233:       if overall_game <= games_in_round(r)
234:         return [r, overall_game]
235:       else
236:         overall_game -= games_in_round(r)
237:       end
238:     end
239:   end

score_against(other_bracket, scoring_strategy) click to toggle source

Computes the total score of this bracket using other_bracket to determine correct picks. Use the provided scoring strategy to compute the score.

     # File lib/tournament/bracket.rb, line 287
287:   def score_against(other_bracket, scoring_strategy)
288:     score = 0
289:     round = 1
290:     while round <= self.rounds
291:       games_in_round = self.games_in_round(round)
292:       game = 1
293:       while game <= games_in_round
294:         winner, loser = other_bracket.winner_and_loser(round, game)
295:         score += scoring_strategy.score(self.winner(round, game), winner, loser, round)
296:         #puts "round #{round} game #{game} winner #{winner} loser #{loser} pick #{self.winner(round,game)}"
297:         game += 1
298:       end
299:       round += 1
300:     end
301:     return score
302:   end

scores_for_round(round, other_bracket, scoring_strategy) click to toggle source

Compute the score for a particular round against the other_bracket using the provided scoring strategy. Returns an array of two element arrays, one for each game in the round. The first element of the subarray is the score and the second element is the team that was picked. If the winner of the game is unknown (because it has not been played), the score element will be nil.

     # File lib/tournament/bracket.rb, line 311
311:   def scores_for_round(round, other_bracket, scoring_strategy)
312:     games_in_round = self.games_in_round(round)
313:     return (1..games_in_round).to_a.map do |g|
314:       winner, loser = other_bracket.winner_and_loser(round, g)
315:       pick = self.winner(round, g)
316:       score = nil
317:       if winner != UNKNOWN_TEAM || !other_bracket.still_alive?(pick)
318:         score = scoring_strategy.score(pick, winner, loser, round)
319:       end
320:       [score, pick]
321:     end
322:   end

set_winner(round, game, team) click to toggle source

Sets the winner of the given round and game to the provided team

     # File lib/tournament/bracket.rb, line 242
242:   def set_winner(round, game, team)
243:     if UNKNOWN_TEAM == team || matchup(round, game).include?(team)
244:       @winners[round][game-1] = team
245:       @number_of_outcomes = nil
246:     else
247:       raise "Round #{round}, Game #{game} matchup does not include team #{team.inspect}"
248:     end
249:   end

still_alive?(team) click to toggle source

Returns true if the provided team has not lost

    # File lib/tournament/bracket.rb, line 25
25:   def still_alive?(team)
26:     return false if team == UNKNOWN_TEAM
27:     team_index = @winners[0].index(team)
28:     game = team_index/2
29:     round = 1
30:     #puts "Checking round #{round} game #{game} winner #{@winners[round][game].inspect} team #{team.short_name}"
31:     while @winners[round][game] == team && round < self.rounds
32:       round += 1
33:       game /= 2
34:       #puts "Checking round #{round} game #{game} winner #{@winners[round][game].inspect} team #{team.short_name}"
35:     end
36:     return [UNKNOWN_TEAM, team].include?(@winners[round][game])
37:   end

teams_left() click to toggle source

Returns the number of teams left in the bracket.

    # File lib/tournament/bracket.rb, line 75
75:   def teams_left
76:     return 1 + @winners.inject(0) { |memo, arr| arr.inject(memo) {|memo2, team| memo2 += (team == UNKNOWN_TEAM ? 1 : 0)} }
77:   end

winner(round, game) click to toggle source

Returns the winner of the given round and game

     # File lib/tournament/bracket.rb, line 211
211:   def winner(round, game)
212:     return @winners[round][game-1]
213:   end

winner_and_loser(round, game) click to toggle source

Returns a two element array whose first element is the winner and the second element is the loser of the given round and game

     # File lib/tournament/bracket.rb, line 217
217:   def winner_and_loser(round, game)
218:     winner = winner(round,game)
219:     if UNKNOWN_TEAM == winner
220:       return [UNKNOWN_TEAM, UNKNOWN_TEAM]
221:     end
222:     matchup = matchup(round, game)
223:     if matchup[0] == winner
224:       return matchup
225:     else
226:       return matchup.reverse
227:     end
228:   end

In Files

Parent

Methods