[Tutor] A (not so) simple question? Round Robin

[Roland Schlenker]

> Adam Gordon wrote:

> Description
> 
> n teams are to play each other in a competition. In each round each
> team plays exactly one other team. We wish to have as few rounds as
> possible.
> 
> Write a program which, given an even number n, produces a "draw table"
> showing which team plays which team in each round. It is to take the
> minimum possible number of rounds. If more than one such draw table is
> possible your program may return whichever you wish.
> 
> For example here is an 4 player draw table
> 
>   A B C D
> A   1 2 3
> B 1   3 2
> C 2 3   1
> D 3 2 1
> 

Using the method suggested at:

http://www.rain.org/~mkummel/stumpers/09feb01a.html

I came up with:

def outerZip(aList):
    assert 0 == len(aList) % 2
    half = len(aList) / 2
    listA, listB = aList[:half], aList[half:]
    listB.reverse()
    return zip(listA, listB)

assert [(1, 6), (2, 5), (3, 4)] == outerZip([1, 2, 3, 4, 5, 6])

class RoundRobin:
    def __init__(self, teams):
        self.teams = teams
        self.rounds = []

    def makeRounds(self):
        numberOfRounds = len(self.teams) - 1
        pivotTeam, teams = self.teams[0], self.teams[1:]
        self.rounds = []
        while 1:
            if numberOfRounds == 0:
                break
            playsPivotTeam, teams = teams[0], teams[1:]
            round = [(pivotTeam, playsPivotTeam)] + outerZip(teams)
            self.rounds.append(round)
            teams = teams + [playsPivotTeam]
            numberOfRounds -= 1

    def playsWhoWhen(self, teamA, teamB):
        if teamA == teamB:
            return ''
        for round in self.rounds:
            for game in round:
                if teamA in game and teamB in game:
                    return self.rounds.index(round) + 1

    def roundsToString(self):
        result = []
        result.append(" ")
        for team in self.teams:
            result.append(" " + team)
        result.append('\n')
        for team in self.teams:
            result.append(team)
            for opposingTeam in self.teams:
                result.append(" %1s" % self.playsWhoWhen(team,
opposingTeam))
            result.append('\n')
        return ''.join(result)

aRound = RoundRobin(['A', 'B', 'C', 'D', 'E', 'F'])
aRound.makeRounds()
assert [[('A', 'B'), ('C', 'F'), ('D', 'E')],
        [('A', 'C'), ('D', 'B'), ('E', 'F')],
        [('A', 'D'), ('E', 'C'), ('F', 'B')],
        [('A', 'E'), ('F', 'D'), ('B', 'C')],
        [('A', 'F'), ('B', 'E'), ('C', 'D')]] == aRound.rounds
assert 1 == aRound.playsWhoWhen('C', 'F')
assert 5 == aRound.playsWhoWhen('A', 'F')
assert "  A B C D E F\n" +\
       "A   1 2 3 4 5\n" +\
       "B 1   4 2 5 3\n" +\
       "C 2 4   5 3 1\n" +\
       "D 3 2 5   1 4\n" +\
       "E 4 5 3 1   2\n" +\
       "F 5 3 1 4 2  \n" == aRound.roundsToString()


Roland Schlenker