#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2004
    Posts
    1
    Rep Power
    0

    Creating Random Match Lists


    Ok this is going to take some explaining so you might wanna grab a coffee.
    First off let me point out this is a piece of coursework for college, but I'm not asking for anyone to do it for me, I just got a bit stuck and need help. I would ask my tutors but they don't know Python.

    First off I'll give an explanation of the problem before I put the code I have already created:

    Part of the program I need to create is creating a match list of students for a schools games competition (entirely fiction and entirely pointless)

    The students are split into classes, and houses. There are 6 classes and two houses (Yellow and Green) classes contain an even number of students between 4 and 8 students in each class. The classes contain an equal mix of students from both houses.

    The match list will match the students against each other in four games: Snap, Cribbage, Spillikins, and Scrabble (I have a feeling they came up with this over a 15 minute lunch break)

    The houses are competing against each other, but students cannot play students from the same class, they can only play another student once, and they will only take part in one match for each game.

    A list of the students, their class numbers and houses can be found here: http://notacake.com/students.txt

    So far I have this code to create a shelve object to store a series of Student classes for each student:

    Code:
    #!/usr/local/bin/python
    
    import shelve, random
    
    class Student:
        pass
    
    studentList = open('competitors.txt').readlines()
    students = shelve.open('students')
    
    for line in studentList:
        splitted = ''
        student = ''
        
        splitted = line.split(',')
        student = Student()
        student.name = splitted[0]
        student.classNo = splitted[1]
        student.house = splitted[2]
        student.matched = [False, False, False, False]
        student.opponents = ['', '', '', '']
        student.scores = [0,0,0,0,0,0,0,0,0,0,0,0]
        
        students[student.name] = student
    
    students.close()
    This is code to create the match list:

    Code:
    #!/usr/local/bin/python
    
    import shelve, random
    
    class Student:
        pass
    
    # Return a random student that hasn't been matched for the given gameType
    # Returns: Student class type
    def getUnmatched(gameType):
        student = random.choice(studentListGroup2)
        while student.matched[gameType]:
            student = random.choice(studentListGroup2)
        return student
    
    students = shelve.open('students')
    
    # Game Types:
    # 0 = Snap
    # 1 = Cribbage
    # 2 = Spillikins
    # 3 = Scrabble
    games = ['Snap', 'Cribbage', 'Spillikins', 'Scrabble']
    
    # Create two lists so the students can be split into 2 equal amounts
    # this should make matching easier
    studentListGroup1 = []
    studentListGroup2 = []
    
    # Splits the students into the two lists by classes, since Classes 1, 2 and 4
    # are equal to classes 3, 5 and 6
    for studentName in students.keys():
        student = students[studentName]
        if student.classNo == '1' or student.classNo == '2' or student.classNo == '4':
            studentListGroup1.append(student)
        else:
            studentListGroup2.append(student)
    
    # Goes through each student in the first group, and picks a random opponent
    # from the second list
    for student in studentListGroup1:
        # This make sure it does it for each gameType
        for gameType in range(0, 4):
            # Just to make sure they haven't been matched in this gameType
            # Note: this came from an earlier method and now seems to be
            # redundant, but it is a useful check anyway
            if not student.matched[gameType]:
                # Pick random student
                unmatchedStudent = getUnmatched(gameType)
                
                # Check this random student is not in the same house or class
                # The commented bit is supposed to check that they are not
                # already playing this student in another match, but this
                # causes the program to enter an infinite loop
                # ==== This is where the problem is ====
                # or at least this is where a flaw in my method becomes apparent
                while (unmatchedStudent.house == student.house) or (unmatchedStudent.classNo == student.classNo): # or (unmatchedSudent.name not in student.opponents):
                    unmatchedStudent = getUnmatched(gameType)
                
                # Set the students as matched and sets the name of the student
                # they are matched with
                student.matched[gameType] = True
                student.opponents[gameType] = unmatchedStudent.name
    
                unmatchedStudent.matched[gameType] = True
                unmatchedStudent.opponents[gameType] = student.name
    
                # Prints the match list to the console
                print '%s is matched with %s for %s' % (student.name, unmatchedStudent.name, games[gameType])
    
    # Puts the student types back into the shelve
    for student in studentListGroup1:
        students[student.name] = student
    
    for student in studentListGroup2:
        students[student.name] = student
    
    students.close
    Now it's either one of two things:

    I've come up with a stupid way of doing it -or-
    I've made a stupid mistake

    Any ideas?
  2. #2
  3. I <3 ASCII
    Devshed Regular (2000 - 2499 posts)

    Join Date
    Aug 2003
    Posts
    2,399
    Rep Power
    1232
    I haven't ran your code, but based on the fact that you're getting an infinite loop i'd suggest a different algorithm, or at least a modified one.

    Without putting too much thought into this (sorry =P ) I'm suggesting a brute force method similar to the following.

    Code:
    #(pseudo pythonish code)
    def GenerateMatchlist (YellowHouse, GreenHouse)
        matchlist = None
        while GenerateNewMatchList(YellowHouse, GreenHouse, matchlist, 'snap') :
            while GenerateNewMatchList(YellowHouse, GreenHouse, matchlist, 'scrabble') : 
                while GenerateNewMatchList (YellowHouse, GreenHouse, matchlist, 'Cribbage') :
                     if GenerateNewMatchList ( YellowHouse, GreenHouse, matchlist, 'Spillikins') :
                           return matchlist
    where GenerateMatchlist does the following :

    1.) looks at the current matchlist items for the game type
    2.) if there is no entries in the matchlist for the game type adds the first logical valid entry (ex. Green 1 playes Yellow 1... G2 vs Y2 etc assuming there's no one in the same class)
    3.) If there is a current entry it finds the next valid logical entry (if the current entry is G1Y1 G2Y2 G3Y3 G4Y4 the next entry would be G1Y1 G2Y2 G3Y4 G4Y3)

    4.) If it's at it's last valid entry (G1Y4 G2Y3 G3Y2 G4Y1) return False

    If it makes it all the way to the end return the current match list

    It's brute force but it should work, I don't really know of an easy way to make it more intelligent though.

    Note: If possible I would use recursion on GenerateMatchList to generate the matches easier.

    -MBirchmeier

IMN logo majestic logo spyfu logo threadwatch logo seochat tools logo