Coding logical code to figuring out who to pay in Poker-CodePudding

I want to write a script that will help me calculate how a group of people should pay each other after a poker cash game night.

Currently, I have 2 dictionaries. The 1st dictionary's key will be player name, and the value will be initial buyin. The 2nd dictionary's key will be player name, and the value will be final # of chips on the table.

I will then store the profit and loss of each player in a 3rd dictionary, with key being player's name and value being the profit/loss of that specific player.

Problem I need help with now is to figure out the best way to pay each other, and the best way is defined to be the least # of transactions. Im stuck on the logic and finding a way to code this properly.

For example, say this is the profit/loss dictionary:

PLDictionary = {
   'Player1': 200,
   'Player2': 500,
   'Player3': -100,
   'Player4': -500,
   'Player5': -100
}

I want the output to be:

Player4 pays Player2 500
Player3 pays Player1 100
Player5 pays Player1 100

Theoretically, the following output would also work, but its not ideal as more transactions are needed.

Player4 pays Player1 200
Player4 pays Player2 300
Player3 pays Player2 100
Player5 pays Player2 100

The solution to this problem don't have to revolve around a dictionary. I just used dictionaries because I thought it would be an easy way to keep track of player-chips information.

CodePudding user response：

If you want to avoid checking every possible combination you will need some heuristics. I'm not aware of any known algorithm, but one option comes to mind:

select the largest debit, and the largest credit
pay the selected credit with the selected debit
record that payment, and update data (for instance, if the debit was less than the credit, then the debit is eliminated but the credit is only reduced)
loop until there are no more credits to pay.

Here is a possible implementation:

PLDictionary = {
   'Player1': 200,
   'Player2': 500,
   'Player3': -100,
   'Player4': -500,
   'Player5': -100
}
creds = sorted([[credit,player] for player, credit in PLDictionary.items() if credit > 0])
debts = sorted([[abs(debit),player] for player, debit in PLDictionary.items() if debit < 0])
payments=[]
while creds:
    if debts[-1][0] < creds[-1][0]:
        payments.append((debts[-1][1], creds[-1][1], debts[-1][0]))
        creds[-1][0] -= debts[-1][0]
        creds.sort()
        _ = debts.pop()
    elif debts[-1][0] > creds[-1][0]:
        payments.append((debts[-1][1], creds[-1][1], creds[-1][0]))
        debts[-1][0] -= creds[-1][0]
        debts.sort()
        _ = creds.pop()
    else:
        payments.append((debts[-1][1], creds[-1][1], creds[-1][0]))
        _ = debts.pop()
        _ = creds.pop()

for payment in payments:
    print(f'{payment[0]:15} pays {payment[2]:4d} to {payment[1]}')

Player4         pays  500 to Player2
Player5         pays  100 to Player1
Player3         pays  100 to Player1

I'm sure this may be optimized a lot, but it should be enough to give you an idea.