7
\$\begingroup\$

I'm learning python and I want to model a single elimination tournament like they use in athletic events like tennis, basketball, etc. The idea would be to insert some meaningful metrics to determine the winner. I've already got a database that I plan to connect to to get the metrics, but I am hoping to find a better way to "process" games in the tournament to move the winner to the next round, and eventually find the tournament winner.

16 team tournament

So far this is the best I have come up with, but it doesn't scale (at all easily) to 32, 64, 128 entries & so-on. The "primary key" that I need to retain is the "seed id" (1-16, in this case), which matches the unique identifier in the database, so that I can pull the correct metrics for deciding which entry will win a matchup. Suggestions?

## this list represents the round 1 seeding order on the tournament sheet
## this doesnt easily scale to 32, 64, 128 entries
teamlist = [1,16,8,9,5,12,4,13,6,11,3,14,7,10,2,15]  

#In a single elim tournament with a full field, # of games is # of teams-1
totalgames = len(teamlist) - 1

#Set defaults
gameid = 0
roundid = 0
nextround = []

#simulate all of the games
while gameid < totalgames:
    if gameid in [8,12,14]:  ##this is a manual decision tree, doesn't scale at all
        #if a new round begins, reset the list of the next round
        print "--- starting a new round of games ---"
        teamlist = nextround
        nextround = []
        roundid = 0

    #compare the 1st entry in the list to the 2nd entry in the list
    homeid = teamlist[roundid]
    awayid = teamlist[roundid + 1]

    #the winner of the match become the next entry in the nextround list
    #more realistic metrics could be substituted here, but ID can be used for this example
    if homeid < awayid:
        nextround.append(homeid)
        print str(homeid) + " vs " + str(awayid) + ":  The winner is " + str(homeid)
    else:
        nextround.append(awayid)
        print str(homeid) + " vs " + str(awayid) + ":  The winner is " + str(awayid)

    #increase the gameid and roundid
    gameid += 1
    roundid += 2
    print "next round matchup list: " + str(nextround)

print nextround
\$\endgroup\$
3
\$\begingroup\$

You have two lines marked as "doesn't scale".

The initial team list can be obtained from your database table of available teams (select of team details).

The other "problem line", is

 if gameid in [8,12,14]:  ##this is a manual decision tree, doesn't scale at all

But that's easily avoided by noticing that the games in a round are always half the previous round, and the initial round is half the number of teams!

In other words, you can do something like (if you include the initial round):

def NewRoundIds( teams_in_tournament ):
    round_ids = []
    game_id = 0
    games_in_next_round = len(teams_in_tournament)/2 #need to count the number of teams_in_tournament list
    while games_in_next_round > 0:
        round_ids += [game_id]
        game_id += games_in_next_round
        games_in_next_round /= 2
    return round_ids

new_round_game_ids = NewRoundIds( teamlist )
...
if gameid in new_round_game_ids:
    # etc

== edit ==

This puts it well outside the brief of the site, but it was interesting. The following I think does what you want, generate_tournament(16). It could do with a bit of tidying up, and it's the sort of thing that will certainly benefit from docstrings and doctests, which I shall leave as a exercise.

import math

def tournament_round( no_of_teams , matchlist ):
    new_matches = []
    for team_or_match in matchlist:
        if type(team_or_match) == type([]):
            new_matches += [ tournament_round( no_of_teams, team_or_match ) ]
        else:
            new_matches += [ [ team_or_match, no_of_teams + 1 - team_or_match ] ]
    return new_matches

def flatten_list( matches ):
    teamlist = []
    for team_or_match in matches:
        if type(team_or_match) == type([]):
            teamlist += flatten_list( team_or_match )
        else:
            teamlist += [team_or_match]
    return teamlist

def generate_tournament( num ):
    num_rounds = math.log( num, 2 )
    if num_rounds != math.trunc( num_rounds ):
        raise ValueError( "Number of teams must be a power of 2" )
    teams = 1
    result = [1]
    while teams != num:
        teams *= 2
        result = tournament_round( teams, result )
    return flatten_list( result )
\$\endgroup\$
5
  • \$\begingroup\$ Thanks Glenn, excellent suggestions. I will give them a try. Do you have any good suggeestions on how to create the initial "team list" without typing it all out? Is there some kind of algorithm that we could identify that would follow the structure of a tourney so I could just insert the team ids? Notice they are not just numbered 1-16 down the lefthand side of the diagram. \$\endgroup\$ – RyanKDalton Oct 19 '12 at 14:39
  • \$\begingroup\$ That rather depends on what you meant by "I've already got a database that I plan to connect to to get the metrics" - it sounded like you have everything like that in your database. If you want a list of random numbers teamlist = [i + 1 for i in range( teams_in_tournament ), random.shuffle( teamlist ). Not sure what you mean by the algorithm. \$\endgroup\$ – Glenn Rogers Oct 19 '12 at 16:28
  • \$\begingroup\$ So, the "seed id" (1 through 16) is the "primary key" referenced in the database, but not the "structure" of the tournament (in regards to 'who plays who'). I do not want a randlom list, either, as in the first round team 1 plays 16, 9v8, etc. In the second round, the winner of team 1/16 needs to play the winner of 9/8, and so on... Make sense? \$\endgroup\$ – RyanKDalton Oct 19 '12 at 17:08
  • \$\begingroup\$ It does. Answer edited. \$\endgroup\$ – Glenn Rogers Oct 19 '12 at 22:36
  • 1
    \$\begingroup\$ Wow...That's amazing! I knew there had to be a better way, and you found it. I really appreciate you putting so much thought into your answer. I definitely learned a lot! \$\endgroup\$ – RyanKDalton Oct 20 '12 at 3:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.