gistfile1.py

from collections import defaultdict
"""
"""

class Solution(object):
    def minTransfers(self, transactions):
        """
        :type transactions: List[List[int]]
        :rtype: int
        """
        
        gm = defaultdict(int)
        g = defaultdict(dict)        

        for frm,to,amount in transactions:
            gm[to] += amount
            gm[frm] -= amount
            g[frm][to] = amount

        positive = []
        negative = []

        for x in gm:
            if gm[x] == 0:
                continue
            elif gm[x] > 0:
                positive.append(gm[x])
            else:
                negative.append(gm[x])

        negative = sorted(negative)
        positive = sorted(positive)

        self.minum = 10000

        def calculate(i):
            if len(set(negative)) == 1 and 0 in set(negative):                
                self.minum = min(self.minum, i)

            for x in xrange(0,len(positive)):
                if positive[x] != 0:
                    for n in xrange(0, len(negative)):
                        if negative[n] != 0:
                            nn = negative[n]

                            newN = nn + positive[x]
                            tempPos = positive[x]
                            tempNeg = negative[n]

                            if newN > 0:
                                paddition = positive[x] + nn
                                positive[x] -= paddition
                                negative[n] = 0
                            else:
                                negative[n] += positive[x]
                                positive[x] = 0

                            calculate(i + 1)


                            positive[x] = tempPos
                            negative[n] = tempNeg


        calculate(0)
        print(self.minum)


s = Solution()

transactions = [[0,1,10], [2,0,5]]

transactions = [[0,1,10], [1,0,1], [1,2,5], [2,0,5]]

s.minTransfers(transactions)

A group of friends went on holiday and sometimes lent each other money. For example, Alice paid for Bill's lunch for $10. Then later Chris gave Alice $5 for a taxi ride. We can model each transaction as a tuple (x, y, z) which means person x gave person y $z. Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person's ID), the transactions can be represented as [[0, 1, 10], [2, 0, 5]].

Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt.

Note:

A transaction will be given as a tuple (x, y, z). Note that x ≠ y and z > 0. Person's IDs may not be linear, e.g. we could have the persons 0, 1, 2 or we could also have the persons 0, 2, 6. Example 1:

Input: [[0,1,10], [2,0,5]]

Output: 2

Explanation: Person #0 gave person #1 $10. Person #2 gave person #0 $5.

Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each. Example 2:

Input: [[0,1,10], [1,0,1], [1,2,5], [2,0,5]]

Output: 1

Explanation: Person #0 gave person #1 $10. Person #1 gave person #0 $1. Person #1 gave person #2 $5. Person #2 gave person #0 $5.

Therefore, person #1 only need to give person #0 $4, and all debt is settled.