Welcome, guest | Sign In | My Account | Store | Cart

Here is a handy script that uses the simplex algorithm to compute an optimum list of refunds (for example, after a trip with shared expenses with friends).

It minimizes the number of transactions (refunds) required to reach the balance.

Python, 61 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61``` ```#!/usr/bin/python # # This script takes dues in input (std input) and compute an optimum # list of refunds. # Format of input list (a negative is a due) # John -10 # Jack +20 # Jessie - # # If the sum is not equal to zero, the algorithm never stops. import sys # CONSTANTS BALANCE_THRESHOLD = 0.02 # Init map of dues dues = {} # Read std in for line in sys.stdin : # Split into two parts (name, due) = line.strip().split() # Fill the map of dues dues[name] = float(due) # Init list of refunds (from, to, sum) refunds = [] # Loop until the balance is reached while True : # Get the min/max due maxName = max(dues, key=dues.get) minName = min(dues, key=dues.get) # Min == Max ?? => exit if minName == maxName : break # Get dues minDue = dues[minName] maxDue = dues[maxName] # What can we exchange ? maxRefund = min(abs(minDue), abs(maxDue)) # Balance reached ? if maxRefund <= BALANCE_THRESHOLD : break # Add a refund refunds.append((minName, maxName, maxRefund)) # Update dues dues[minName] += maxRefund dues[maxName] -= maxRefund # Print refunds for (fromName, toName, refund) in refunds : print "%s => %s : %.2f" % (fromName, toName, refund) ```

This script takes a list of dues in standard input in this format

``````Gerald -36.56
Remi -36.56
Marco -237.97
Marion -102.47
Raphael -96.11
Nicolas -23.47
Francois +29.83
Magali +118.32
Anthony +385.01
``````

The negative amount are dues. The sum should be equal to zero, for the script to ends correctly.

You may call this script with ''cat'':

``````cat dues.txt | balance.py
``````

The output looks like this :

``````Marco => Anthony : 237.97
Marion => Anthony : 102.47
Raphael => Magali : 96.11
Gerald => Anthony : 36.56
Remi => Francois : 29.83
Nicolas => Magali : 22.21
Remi => Anthony : 6.73
Nicolas => Anthony : 1.26
``````
 Created by Raphaël Jolivet on Tue, 26 Apr 2011 (MIT)

### Required Modules

• (none specified)