[Tutor] A (not so) simple question? Round Robin
Roland Schlenker
rol9999@attglobal.net
Mon, 18 Jun 2001 10:14:28 -0500
> 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