tournament_2.py

#! /usr/bin/env python

import sys

class Game(object):

    def __init__(self, num_players, num_courts):
        self.a = map(lambda x: 'a' + str(x), xrange(1, num_players + 1))
        self.b = map(lambda x: 'b' + str(x), xrange(1, num_players + 1))
        self.played_together = dict()
        self.played_against = dict()
        self.num_courts = num_courts

    def rank(self, player):
        '''Return the rank of a player'''
        return int(player[1])

    def all_teams(self):
        '''Generate all possible teams, excluding teams which have players of the same rank'''
        teams = list()
        for a in self.a:
            for b in self.b:
                if self.rank(a) != self.rank(b):
                    teams.append((a, b))
        return teams

    def played_together_before(self, team):
        '''Check if players (a, b) in 'team' have played a match before'''
        a, b = team
        result = False
        if self.played_together.has_key(a):
            if b in self.played_together[a]:
                result = True
            else:
                result = False
        elif self.played_together.has_key(b):
            if a in self.played_together[b]:
                result = True
            else:
                result = False
        return result

    def played_against_before(self, a, b):
        '''Check if a has played against b before'''
        result = False
        if self.played_against.has_key(a):
            if b in self.played_against[a]:
                result = True
            else:
                result = False
        elif self.played_against.has_key(b):
            if a in self.played_against[b]:
                result = True
            else:
                result = False
        return result

    def match_done(self, teams):
        '''Players in 'teams' have now played a match together'''
        # update played_together
        for team in teams:
            a, b = team
            if self.played_together.has_key(a):
                self.played_together[a].append(b)
            elif self.played_together.has_key(b):
                self.played_together[b].append(a)
            else:
                self.played_together[a] = [b]
        # update played_against
        for (a, b) in ( (teams[0][0], teams[1][1]), (teams[1][0], teams[0][1]) ):
            if self.played_against.has_key(a):
                self.played_against[a].append(b)
            elif self.played_against.has_key(b):
                self.played_against[b].append(a)
            else:
                self.played_against[a] = [b]
                self.played_against[b] = [a]

    def match_possible(self, team_1, team_2):
        '''Check if a match is possible between team_1 and team_2'''
        # check if the same player is in both the teams
        players = set()
        for i in xrange(0, 2):
            players.add(team_1[i])
            players.add(team_2[i])
        if len(players) < 4:
            return False
        
        # check if the players from either of the teams have played together before
        if self.played_together_before(team_1) or self.played_together_before(team_2):
            return False

        # check if 'a' from one team has played against 'b' from the second team once
        a = team_1[0]; b = team_2[1];
        if self.played_against_before(a, b):
            return False
        a = team_2[0]; b = team_1[1];
        if self.played_against_before(a, b):
            return False

        return True

    def all_matches(self):
        '''
        Generate a tournament (a list of all the matches possible), taking into
        account the conditions under which a match may or not may not be played
        '''
        teams = self.all_teams()
        tournament = list()
        for i in xrange(0, len(teams)):
            for j in xrange(0, len(teams)):
                if i != j:
                    if self.match_possible(teams[i], teams[j]):
                        tournament.append((teams[i], teams[j]))
                        self.match_done((teams[i], teams[j]))
        return tournament

    def players_in_a_match(self, match):
        '''Utility function to return all the players playing in a match'''
        players = list()
        for i in xrange(0, 2):
            for j in xrange(0, 2):
                players.append(match[i][j])
        return players

    def play_tournament(self, tournament):
        '''Organize the matches, given the number of courts which the tournament can use'''
        stages = list()
        while len(tournament) > 0:
            players = list() # currently playing in this stage
            indices = list() # indices of all matches being played in this stage
            for index in xrange(0, len(tournament)):
                if len(indices) == self.num_courts:
                    break
                else:
                    match = tournament[index]
                    can_play = True
                    for player in self.players_in_a_match(match):
                        if player in players:
                            can_play = False
                            break
                    if can_play:
                        indices.append(index)
                        players.extend(self.players_in_a_match(match))
            # matches that will be played in this stage
            matches = list()
            for index in indices:
                matches.append(tournament[index])
                tournament[index] = None
            stages.append(matches)
            # pick the matches that remain to be played
            tournament = [match for match in tournament if match is not None]
        return stages

def main(num_players, num_courts):
    game = Game(num_players, num_courts)
    tournament = game.all_matches()
    print "Following matches will be played in the tournament =>"
    for i in xrange(0, len(tournament)):
        print "Match #%d => %s" % (i + 1, tournament[i])
    print "Tournament will be played on %d courts as follows =>" % num_courts
    stages = game.play_tournament(tournament)
    for i in xrange(0, len(stages)):
        print "Round %d => %s" % (i + 1, " and ".join([str(match) for match in stages[i]]))

if __name__ == "__main__":
    try:
        num_players = int(sys.argv[1])
        num_courts = int(sys.argv[2])
    except:
        print "Usage: %s <num_players> <num_courts>" % sys.argv[0]
        exit(1)
    else:
        if num_courts < 1:
            print "num_courts must be greater than 0"
            exit(1)
        main(num_players, num_courts)