Class representing a bracket in a tournament.

Methods
Classes and Modules
Class Tournament::Bracket::BasicScoringStrategy
Class Tournament::Bracket::UpsetScoringStrategy
Constants
UNKNOWN_TEAM = :unk unless defined?(UNKNOWN_TEAM)
Attributes
[R] name
[R] rounds
[RW] scoring_strategy
[R] teams
[R] winners
Public Class methods
available_strategies()

Returns names of available strategies. The names returned are suitable for use in the strategy_for_name method

[ show source ]

    # File lib/tournament/bracket.rb, line 38
38:   def self.available_strategies
39:     return ['basic_scoring_strategy', 'upset_scoring_strategy']
40:   end
new(teams = nil)

Creates a new bracket with the given teams

[ show source ]

    # File lib/tournament/bracket.rb, line 51
51:   def initialize(teams = nil)
52:     @teams = teams || [:t1, :t2, :t3, :t4, :t5, :t6, :t7, :t8, :t9, :t10, :t11, :t12, :t13, :t14, :t15, :t16]
53:     @rounds = (Math.log(@teams.size)/Math.log(2)).to_i
54:     @winners = [@teams] + (1..@rounds).map do |r|
55:       [UNKNOWN_TEAM] * games_in_round(r)
56:     end
57:     @scoring_strategy = BasicScoringStrategy.new
58:   end
random_bracket(teams = nil)

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

[ show source ]

     # File lib/tournament/bracket.rb, line 339
339:   def self.random_bracket(teams = nil)
340:     b = Tournament::Bracket.new(teams)
341:     1.upto(b.rounds) do |r|
342:       1.upto(b.games_in_round(r)) { |g| b.set_winner(r, g, b.matchup(r, g)[rand(2)]) }
343:     end
344:     return b
345:   end
strategy_for_name(name)

Returns an instantiated strategy class for the named strategy.

[ show source ]

    # File lib/tournament/bracket.rb, line 43
43:   def self.strategy_for_name(name)
44:     clazz = Tournament::Bracket.const_get(name.capitalize.gsub(/_([a-zA-Z])/) {|m| $1.upcase})
45:     return clazz.new
46:   end
Public Instance methods
bracket_for(possibility)

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

[ show source ]

     # File lib/tournament/bracket.rb, line 197
197:   def bracket_for(possibility)
198:     pick_bracket = Tournament::Bracket.new(self.teams)
199:     pick_bracket.scoring_strategy = self.scoring_strategy
200:     round = 1
201:     while round <= pick_bracket.rounds
202:       gir = pick_bracket.games_in_round(round)
203:       game = 1
204:       while game <= gir
205:         matchup = pick_bracket.matchup(round, game)
206:         mask = 1 << (gir - game)
207:         # Shift for round
208:         mask = mask << (2 ** (pick_bracket.rounds - round) - 1)
209:         pick = (mask & possibility) > 0 ? 1 : 0
210:         #puts "round #{round} game #{game} mask #{Tournament::Bracket.jbin(mask)} poss: #{Tournament::Bracket.jbin(possibility)} pick #{pick} winner #{matchup[pick]}"
211:         pick_bracket.set_winner(round, game, matchup[pick])
212:         game += 1
213:       end
214:       round += 1
215:     end
216:     return pick_bracket
217:   end
champion()

Returns the champion of this bracket

[ show source ]

     # File lib/tournament/bracket.rb, line 275
275:   def champion
276:     return @winners[@rounds][0]
277:   end
each_possibility() {|real_poss| ...}

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

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

[ show source ]

     # File lib/tournament/bracket.rb, line 125
125:   def each_possibility
126:     # bit masks of games that have been played
127:     # played_mask is for any game where a winner has been determined
128:     # first is a mask where the first of the matched teams won
129:     # second is a mask where the second of the matched teams won
130:     shift = 0
131:     round = @rounds
132:     played_mask, winners, left_mask = @winners[1..-1].reverse.inject([0,0,0]) do |masks, round_winners|
133:       game = games_in_round(round)
134:       round_winners.reverse.each do |game_winner|
135:         #puts "checking matchup of round #{round} game #{game} winner #{game_winner} matchup #{matchup(round,game)}"
136:         val = 1 << shift
137:         if UNKNOWN_TEAM != game_winner
138:           # played mask
139:           masks[0] = masks[0] | val
140:           # winners mask
141:           if matchup(round,game).index(game_winner) == 1
142:             masks[1] = masks[1] | val
143:           end
144:         else
145:           # games left mask
146:           masks[2] = masks[2] | val
147:         end
148:         shift += 1
149:         game -= 1
150:       end
151:       round -= 1
152:       masks
153:     end
154:     #puts "played mask: #{Tournament::Bracket.jbin(played_mask, teams.size - 1)}"
155:     #puts "  left mask: #{Tournament::Bracket.jbin(left_mask, teams.size - 1)} #{left_mask}"
156:     #puts "    winners: #{Tournament::Bracket.jbin(winners, teams.size - 1)}"
157: 
158:     # for the games left mask, figure out which bits are 1 and what
159:     # their index is.  If left mask is 1001, the shifts array would be
160:     # [0, 3].  If left mask is 1111, the shifts array would be
161:     # [0, 1, 2, 3]
162:     count = 0
163:     shifts = []
164:     Tournament::Bracket.jbin(left_mask, teams.size - 1).reverse.split('').each do |c|
165:       if c == '1'
166:         shifts << count
167:       end
168:       count += 1
169:     end
170: 
171:     #puts "    shifts: #{shifts.inspect}"
172: 
173:     # Figure out the number of possibilities.  This is simply
174:     # 2 ** shifts.size
175:     num_possibilities = 2 ** shifts.size
176:     #num_possibilities = 0
177:     #shifts.size.times { |n| num_possibilities |= (1 << n) }
178: 
179:     #puts "Checking #{num_possibilities} (#{number_of_outcomes}) possible outcomes."
180:     possibility = num_possibilities - 1
181:     while possibility >= 0
182:       #puts "    possibility: #{Tournament::Bracket.jbin(possibility, teams.size - 1)}"
183:       real_poss = 0
184:       shifts.each_with_index do |s, i|
185:         real_poss |= (((possibility & (1 << i)) > 0 ? 1 : 0) << s)
186:       end
187:       #puts "    real_poss: #{Tournament::Bracket.jbin(real_poss, teams.size - 1)}"
188:       real_poss = winners | real_poss
189:       #puts "    real_poss: #{Tournament::Bracket.jbin(real_poss, teams.size - 1)}"
190:       yield(real_poss)
191:       possibility -= 1
192:     end
193:   end
each_possible_bracket() {|bracket_for(possibility)| ...}

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.

[ show source ]

    # File lib/tournament/bracket.rb, line 82
82:   def each_possible_bracket
83:     puts "WARNING: This is likely going to take a very long time ... " if teams_left > 21
84:     each_possibility do |possibility|
85:       yield(bracket_for(possibility))
86:     end
87:   end
games_in_round(round)

Returns the number of games in the given round

[ show source ]

     # File lib/tournament/bracket.rb, line 232
232:   def games_in_round(round)
233:     return @teams.size / 2 ** round
234:   end
games_played()

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

[ show source ]

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

Pretty print.

[ show source ]

     # File lib/tournament/bracket.rb, line 267
267:   def inspect
268:     str = ""
269:     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
270:     str << "Champion: #{champion.inspect}"
271:     return str
272:   end
matchup(round, game)

Returns a two element array containing the Team‘s in the matchup for the given round and game

[ show source ]

     # File lib/tournament/bracket.rb, line 221
221:   def matchup(round, game)
222:     return @winners[round-1][(game-1)*2..(game-1)*2+1]
223:   end
maximum_score(other_bracket)

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

[ show source ]

     # File lib/tournament/bracket.rb, line 281
281:   def maximum_score(other_bracket)
282:     score = 0
283:     round = 1
284:     while round <= self.rounds
285:       games_in_round = self.games_in_round(round)
286:       game = 1
287:       while game <= games_in_round
288:         winner, loser = other_bracket.winner_and_loser(round, game)
289:         pick = self.winner(round, game)
290:         winner = pick if winner == UNKNOWN_TEAM && other_bracket.still_alive?(pick)
291:         score += other_bracket.scoring_strategy.score(pick, winner, loser, round)
292:         game += 1
293:       end
294:       round += 1
295:     end
296:     return score
297:   end
number_of_outcomes()

Returns the number of possible outcomes for the bracket

[ show source ]

     # File lib/tournament/bracket.rb, line 105
105:   def number_of_outcomes
106:     @number_of_outcomes ||= (2 ** (self.teams_left)) / 2
107:   end
number_rounds_complete()

Returns the number of rounds that have been completed

[ show source ]

    # File lib/tournament/bracket.rb, line 90
90:   def number_rounds_complete
91:     round = 0
92:     while round < self.rounds
93:       break if @winners[round+1].any? {|t| t == UNKNOWN_TEAM}
94:       round += 1
95:     end
96:     return round  
97:   end
pick_correct(round, game, team)

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

[ show source ]

     # File lib/tournament/bracket.rb, line 227
227:   def pick_correct(round, game, team)
228:     return team != UNKNOWN_TEAM && team == winner(round, game)
229:   end
score_against(other_bracket)

Computes the total score of this bracket using other_bracket as the guide

[ show source ]

     # File lib/tournament/bracket.rb, line 301
301:   def score_against(other_bracket)
302:     score = 0
303:     round = 1
304:     while round <= self.rounds
305:       games_in_round = self.games_in_round(round)
306:       game = 1
307:       while game <= games_in_round
308:         winner, loser = other_bracket.winner_and_loser(round, game)
309:         score += other_bracket.scoring_strategy.score(self.winner(round, game), winner, loser, round)
310:         #puts "round #{round} game #{game} winner #{winner} loser #{loser} pick #{self.winner(round,game)}"
311:         game += 1
312:       end
313:       round += 1
314:     end
315:     return score
316:   end
scores_for_round(round, other_bracket)

Compute the score for a particular round against the other_bracket 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.

[ show source ]

     # File lib/tournament/bracket.rb, line 324
324:   def scores_for_round(round, other_bracket)
325:     games_in_round = self.games_in_round(round)
326:     return (1..games_in_round).to_a.map do |g|
327:       winner, loser = other_bracket.winner_and_loser(round, g)
328:       pick = self.winner(round, g)
329:       score = nil
330:       if winner != UNKNOWN_TEAM || !other_bracket.still_alive?(pick)
331:         score = other_bracket.scoring_strategy.score(pick, winner, loser, round)
332:       end
333:       [score, pick]
334:     end
335:   end
set_winner(round, game, team)

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

[ show source ]

     # File lib/tournament/bracket.rb, line 257
257:   def set_winner(round, game, team)
258:     if UNKNOWN_TEAM == team || matchup(round, game).include?(team)
259:       @winners[round][game-1] = team
260:       @number_of_outcomes = nil
261:     else
262:       raise "Round #{round}, Game #{game} matchup does not include team #{team.inspect}"
263:     end
264:   end
still_alive?(team)

Returns true if the provided team has not lost

[ show source ]

    # File lib/tournament/bracket.rb, line 61
61:   def still_alive?(team)
62:     team_index = @winners[0].index(team)
63:     game = team_index/2
64:     round = 1
65:     #puts "Checking round #{round} game #{game} winner #{@winners[round][game].inspect} team #{team.short_name}"
66:     while @winners[round][game] == team && round < self.rounds
67:       round += 1
68:       game /= 2
69:       #puts "Checking round #{round} game #{game} winner #{@winners[round][game].inspect} team #{team.short_name}"
70:     end
71:     return [UNKNOWN_TEAM, team].include?(@winners[round][game])
72:   end
teams_left()

Returns the number of teams left in the bracket.

[ show source ]

     # File lib/tournament/bracket.rb, line 100
100:   def teams_left
101:     return 1 + @winners.inject(0) { |memo, arr| arr.inject(memo) {|memo, team| memo += (team == UNKNOWN_TEAM ? 1 : 0)} }
102:   end
winner(round, game)

Returns the winner of the given round and game

[ show source ]

     # File lib/tournament/bracket.rb, line 237
237:   def winner(round, game)
238:     return @winners[round][game-1]
239:   end
winner_and_loser(round, game)

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

[ show source ]

     # File lib/tournament/bracket.rb, line 243
243:   def winner_and_loser(round, game)
244:     winner = winner(round,game)
245:     if UNKNOWN_TEAM == winner
246:       return [UNKNOWN_TEAM, UNKNOWN_TEAM]
247:     end
248:     matchup = matchup(round, game)
249:     if matchup[0] == winner
250:       return matchup
251:     else
252:       return matchup.reverse
253:     end
254:   end