Welcome!

By registering with us, you'll be able to discuss, share and private message with other members of our community.

SignUp Now!
  • Guest, before posting your code please take these rules into consideration:
    • It is required to use our BBCode feature to display your code. While within the editor click < / > or >_ and place your code within the BB Code prompt. This helps others with finding a solution by making it easier to read and easier to copy.
    • You can also use markdown to share your code. When using markdown your code will be automatically converted to BBCode. For help with markdown check out the markdown guide.
    • Don't share a wall of code. All we want is the problem area, the code related to your issue.


    To learn more about how to use our BBCode feature, please click here.

    Thank you, Code Forum.

Python Help needed with back tracking type algorithm

Fredu4

New Coder
I am trying to develop a swiss tournament pairing algorithm and I am essentially using a backtracking algorithm that gives a value for each terminal position based on how well it has matched the players. It seems to mostly be working but it will for some reason allow an empty pairing list with a penalty value of 0 to be returned. I have been looking at this code for hours. Any insight would be appreciated!

Python:
    #Calculates the penalty value of a pairing
    def calculatePairingPenalty(self, pairing: Pairing) -> int:
        if pairing.white in pairing.black.playedAgainst:
            return 999999999
        return math.pow(pairing.white.points - pairing.black.points, 2)
    
    #Calculates the total penalty value of a pairing list
    def calculateTotalPenalty(self, pairings: list[Pairing]):
        if len(pairings) != len(self.players)/2:
            return 99999999
        totalPenalty = 0
        for pairing in pairings:
            totalPenalty += self.calculatePairingPenalty(pairing)
        return totalPenalty
 
    # minMax/backtracking type of algorhitm
    def generateNewRound(self, pairings: list[Pairing]):
        if len(pairings) == len(self.players)/2:    # if everyone has been paired return pairings
            #for i in pairings:
            #   print(i.white.name + " : " + i.black.name)
            #print(self.calculateTotalPenalty(pairings))
            return pairings
        
        bestPairings: list[Pairing] = []
        penaltyScore = 999999
        
        #Tries all possible permutations, needs to be optimized
        for player in self.players:
            if player.isPaired: continue

            for opponent in self.players:
                if opponent.isPaired or player.name == opponent.name or opponent in player.playedAgainst: continue
                
                pairings.append(Pairing(player, opponent))
                player.isPaired = True
                opponent.isPaired = True
                newPairings = self.generateNewRound(pairings)
                newPenaltyScore = self.calculateTotalPenalty(newPairings)

                if newPenaltyScore < penaltyScore:
                    penaltyScore = newPenaltyScore
                    bestPairings = newPairings

                player.isPaired = False
                opponent.isPaired = False
                pairings.pop()

        return bestPairings
 
Found the issue. Rather obvious actually... Since lists are mutable I change newPairings and bestPairings when doing pairings.pop() . My easyfix was to change
Python:
newPairings = self.calculateTotalPenalty(newPairings)
to
Python:
newPairings = self.calculateTotalPenalty(newPairings).copy()

Annoying little bug.
 

New Threads

Latest posts

Buy us a coffee!

Back
Top Bottom