Create a gist now

Instantly share code, notes, and snippets.

@shane5ul /splitup.py
Last active Aug 29, 2015

What would you like to do?
Given a set of contributions (and optionally expemptions) creates a list of pair-wise transactions which "settles" all accounts
#!/usr/bin/env python
#
# (c) Sachin Shanbhag, 2015
# Last Modified: March 7, 2015
#
# Given a set of contributions (and optionally expemptions) creates a list of pair-wise
# transactions which "settles" all accounts
#
# example : python splitup.py INPUTFILENAME
#
# : if INPUTFILENAME not provided then looks for csv file "input_table"
#
# : INPUTFILE = csv file containing 2 or three columns, for example
#
# Two column example: NAME, CONTRIBUTION
# Person1, 10
# Person2, 20
# Person3, 5
# Person4, 15
# Person5, 10
#
#
# Three column example: NAME, CONTRIBUTION, AND EXPEMPTION (AMOUNT EXEMPT FROM)
# Person1, 10, 0
# Person2, 20, 5
# Person3, 5, 0
# Person4, 15, 5
# Person5, 10, 0
import sys
import numpy as np
from operator import itemgetter
#---------------------------------------------------------------------------------------------------
def parse_input(fname):
#
# File reads in input file containing three columns, and parses it: outputs number of entries, and
# and list of lists, the first element is the name, and the second element is the net contribution
# that is rounded off, and tested to strictly obey cent level conservation
#---------------------------------------------------------------------------------------------------
#
# Read in the CSV file, and organize it by columns
#
importData = list()
numFields = 0
inputfile = open(fname,"r")
for line in inputfile:
record = (line.rstrip("\n")).split(",")
importData.append(record)
#
# Need to handle with or without exemptions
#
numFields = len(record)
if(numFields < 2):
print "Only two or three columns allowed", record
quit()
inputfile.close()
N = len(importData)
#
# Convert to Float
#
sumInput = 0.
sumExemp = 0.
for i in range(N):
inp = float(importData[i][1])
if(numFields == 3):
exemp = float(importData[i][2])
else:
exemp = 0.
importData[i][1] = inp
if(numFields == 3):
importData[i][2] = exemp
else:
importData[i].append(exemp)
sumInput = sumInput + inp
sumExemp = sumExemp + exemp
sumTmpv = 0.
#
# Account for exemptions. Find what each one is liable for
#
for i in range(N):
importData[i].append(sumInput - importData[i][2]) # Base Cost - Exemption
importData[i].append(0.) # cost responsible
sumTmpv = sumTmpv + importData[i][3]
importData = sorted(importData, key=itemgetter(3),reverse=True)
n = N
#
# In column 5 find personal cost basis: somewhat nontrivial operation
#
while n > 0 and sumTmpv > 0.:
sumTmpv = 0.
for i in range(n):
importData[i][4] = importData[i][4] + importData[n-1][3]/n
importData[i][3] = importData[i][3] - importData[n-1][3]
sumTmpv = sumTmpv + importData[i][3]
n = n - 1
#
# Find net contribution, round it
#
total = 0
for i in range(N):
importData[i][1] = int(100*round(importData[i][1] - importData[i][4],2))
total = total + importData[i][1]
del importData[i][2:5] # delete extra-columns
#
# Any cent-level round-offs redistribute randomly
#
for i in range(abs(total)):
select = np.random.randint(N)
importData[select][1] = importData[select][1] - np.sign(total)
#
# Test whether redistribution is conservative
#
total = 0
for i in range(N):
total = total + importData[i][1]
if(abs(total) > 0):
print "Conservation Problems: total ", total
return N, importData
#---------------------------------------------------------------------------------------------------
def generateTransactions(N, listData):
# generate list of transactions from the listData, which contains names and assets/liabilities
#---------------------------------------------------------------------------------------------------
TransList = list()
#
# This is a roughly written routine. Could be easily optimized
# But generally "N" is small, so my time is more valuable!
#
while N > 1:
listData = sorted(listData, key=itemgetter(1))
#
# credit < debit: Debtor pays off creditor. Creditor out of list
#
if(-listData[0][1] > listData[N-1][1]):
TransList.append([listData[0][0], listData[N-1][0], listData[N-1][1]])
listData[0][1] = listData[0][1] + listData[N-1][1] # reduce
del listData[-1]
#
# debit < credit: Debtor pays creditor. Debtor out of list
#
elif(-listData[0][1] < listData[N-1][1]):
TransList.append([listData[0][0], listData[N-1][0], -listData[0][1]])
listData[N-1][1] = listData[N-1][1] + listData[0][1] # reduce
del listData[0]
#
# exactly equal: both exchange and both out of list
#
else:
TransList.append([listData[0][0], listData[N-1][0], -listData[0][1]])
del listData[0]
del listData[-1]
N = N - 1
return TransList
#---------------------------------------------------------------------------------------------------
def writeOutput(TransList, isTransactionwise, isPersonwise):
#---------------------------------------------------------------------------------------------------
if(isTransactionwise):
# print
# print TransList, len(TransList)
# print
print "Transaction List"
print "----------------"
print
for i in range(len(TransList)):
print TransList[i][0], "->", TransList[i][1], "$", TransList[i][2]/100.0
if(isPersonwise):
print
print "Transaction List: Person Wise"
print "-----------------------------"
print
for i in range(len(names)):
print names[i]
for j in range(len(TransList)):
if TransList[j][0] == names[i]:
print "\tpays", TransList[j][1], "$", TransList[j][2]/100.
elif TransList[j][1] == names[i]:
print "\tgets paid by", TransList[j][0], "$", TransList[j][2]/100.
print
#****************************************************************
#
# Main Driving Routine: Accepts inputs from the command line
#
#
#
# ***************************************************************
if __name__ == '__main__':
if len(sys.argv) == 2:
fname = sys.argv[1]; # file to read
else:
fname = 'input_table'
N, listData = parse_input(fname)
# print listData
names = list()
for i in range(N):
names.append(listData[i][0])
TransList = generateTransactions(N, listData)
writeOutput(TransList, True, True) # TransactionsList, and PersonWise
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment