Given a set of contributions (and optionally expemptions) creates a list of pair-wise transactions which "settles" all accounts

splitup.py

#!/usr/bin/env python3
#
# (c) Sachin Shanbhag, 2015
#		Last Modified: Jan 5, 2020 (input change to space separated; python3 compliance)
#
#		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
#               : fields are assumed to be space or tab separated
#
# 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
import numpy as np

#---------------------------------------------------------------------------------------------------
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 = np.genfromtxt(fname, dtype=str, delimiter=',').tolist() # for comma separated
	
	importData = np.genfromtxt(fname, dtype=str).tolist()
	numFields  = len(importData[0])
	
	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("\nTransaction List")
		print("----------------\n")
		for i in range(len(TransList)):
			print(TransList[i][0] + " -> " + TransList[i][1] + " $" + "{0:.2f}".format(TransList[i][2]/100.0))

	if(isPersonwise):
		print("\nTransaction List: Person Wise")
		print("-----------------------------\n")
		
		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] + " $" + "{0:.2f}".format(TransList[j][2]/100.))
				elif TransList[j][1] == names[i]:
					print("\tgets paid by " + TransList[j][0] + " $" + "{0:.2f}".format(TransList[j][2]/100.))
		

#****************************************************************
#
# 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