Last active
December 29, 2015 16:39
-
-
Save dmitriy-sqrt/7699115 to your computer and use it in GitHub Desktop.
Perfect team mixing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#################################Тестирование################################# | |
def print_row(teams) #просто выводит команды на какомто этапе | |
teams.each_slice(2) do |team1, team2| | |
print team1.to_s + '-' + team2.to_s + " " | |
end | |
puts | |
end | |
def random_play(team1,team2) | |
p = 0.5/(team1-team2).abs #коефициент - вероятность победы соседних команд #p=вероятность победы | |
winner = ( (team1 < team2) && (rand(0.01..1.01) > p) ) ? team1 : team2 | |
end | |
def play_round(teams, add_random) #раунд #команды играют, команда с рейтингом выше(а у нас это просто индекс-меньше=круче) 100% выигрывает | |
winners = [] | |
teams.each_slice(2) do |team1, team2| | |
if add_random | |
winner = random_play(team1,team2) #шансы на победу пропорциональны разнице позиций команд | |
else | |
winner = (team1 < team2) ? team1 : team2 #команда с лучшей позицией побеждает | |
end | |
winners << winner | |
end | |
winners | |
end | |
def play_tournament(teams, add_random) #турнир - играем раунды, пока не останется одна команда | |
round = 1 | |
while teams.size > 1 do | |
line = "#{round})" | |
round+= 1 | |
teams = play_round(teams, add_random) | |
teams.each_slice(2) do |team1, team2| | |
line << " #{team1.to_s}-#{team2.to_s} " #вывод пары команд | |
end | |
puts line | |
end | |
end | |
#################################Алгоритм################################# | |
##в раунде m играет 2**rounds-round+1 команд | |
##в раунде m мин рейтинг команды 2**round | |
def mix_teams(teams) | |
rounds = Math.log(teams, 2).to_i | |
teams = [1] #сверху у нас всегда одна топовая команда | |
rounds.downto(1) do | |
teams = populate(teams) | |
end | |
teams | |
end | |
def populate(array) | |
new_array = [] | |
max = array.count*2 #минимальный рейтинг соперника на текущем этапе | |
array.each do |el| | |
new_array << el << max-el+1 | |
end | |
new_array | |
end | |
teams = do_new_shit(64) | |
print_row(teams) | |
play_tournament(teams, false) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment