Today I want to share with you a funny side of a project I’m working on.
In the past weeks I’ve implemented a system that seeds the rounds of a Round Robin Tournament aka all-play-all tournament.
The interesting part is how we can seed the matches to let each team play against all the others. For example in a tournament of 6 teams we have 5 rounds with 3 matches per round.
Let’s see how we can schedule all the matches:
Teams: A, B, C, D, E, F
Round 1:
A B C
| | |
F E D
Round 2:
A F B
| | |
E D C
…
Round 5:
A C D
| | |
B F E
The important thing we can see is that the first team A keeps its position across all the rounds while all the other teams change their position in each round. This is the trick we’re going to use in order to create the all-play-all matches.
Let’s see how we can implement this behavior in Ruby.
First of all we need a class for the tournament.
class Tournament
attr_reader :rounds
def initialize teams
@rounds = {}
seed teams
end
private
def seed teams
# logic for seeding all the rounds
end
end
Now we have to implement the seed method. We need an array of teams with an even number of participants, otherwise we have to add a nil element to the teams array, which will eventually deliver a bye match for each team.
def seed teams
teams.push(nil) if teams.size.odd?
# ...
end
At this point we have to create all the rounds. In a Round Robin Tournament the number of rounds equals the number of participants, less 1.
def seed teams
teams.push(nil) if teams.size.odd?
rounds = teams.size - 1
rounds.times do |index|
@rounds[index] = []
# ...
end
end
For each round we want to seed the matches. The number of matches for each round are equal to the half of the number of participants. To implement the behavior showed above we need to take the team in a certain position in the teams array, reverse it and take the opponent in the same position.
def seed teams
teams.push(nil) if teams.size.odd?
rounds = teams.size - 1
matches_per_round = teams.size / 2
rounds.times do |index|
@rounds[index] = []
matches_per_round.times do |match_index|
@rounds[index] << [teams[match_index], teams.reverse[match_index]]
end
# ...
end
end
The last and most important part of this method is to cycle the teams array in order to create different matches in all rounds. We said that the cycle process does not concern the first element which have to preserve its position.
def seed teams
teams.push(nil) if teams.size.odd?
rounds = teams.size - 1
matches_per_round = teams.size / 2
rounds.times do |index|
@rounds[index+1] = []
matches_per_round.times do |match_index|
@rounds[index+1] << [teams[match_index], teams.reverse[match_index]]
end
teams = [teams[0]] + teams[1..-1].rotate(-1)
end
end
Thanks to the rotate(-1) method applied to the whole array of participants except for the first element we achieve exactly what we want.
Creating a tournament with our example array results in:
t = Tournament.new ["A", "B", "C", "D", "E", "F"]
# 5
t.rounds
# {
# 1=>[["A", "F"], ["B", "E"], ["C", "D"]],
# 2=>[["A", "E"], ["F", "D"], ["B", "C"]],
# 3=>[["A", "D"], ["E", "C"], ["F", "B"]],
# 4=>[["A", "C"], ["D", "B"], ["E", "F"]],
# 5=>[["A", "B"], ["C", "F"], ["D", "E"]]
# }
And this is the code for the complete class:
class Tournament
attr_reader :rounds
def initialize teams
@rounds = {}
seed teams
end
private
def seed teams
teams.push(nil) if teams.size.odd?
rounds = teams.size - 1
matches_per_round = teams.size / 2
rounds.times do |index|
@rounds[index+1] = []
matches_per_round.times do |match_index|
@rounds[index+1] << [teams[match_index], teams.reverse[match_index]]
end
teams = [teams[0]] + teams[1..-1].rotate(-1)
end
end
end
I hope you enjoyed this post!
See you soon!
Leave a Reply