# Minimum number of transactions so everyone has paid the same [closed]

On a road trip, N people pay for fuel. Each pays a different amount. At the end of the trip, calculate the minimum number of transactions so that each person has paid the same amount.

e.g. on the road trip, these people pay for fuel

• Dave - $50 • John -$25
• George - $5 • Barry -$0

After the road trip:

• Barry pays Dave $20 • George pays John$5
• George pays Dave $10 Added: The output of the program should list the transactions. Bonus points if the solution is written in Visual Basic. • Why the Visual Basic bonus? Commented Sep 6, 2012 at 17:23 • @Hasturkun - Because I'd like to try this on an Excel spreadsheet. Commented Sep 6, 2012 at 17:44 • id recommend having an exact win condition; before the heavy-handed moderators swing on by :) Commented Oct 24, 2012 at 17:07 • you need to specify a winning condition for the question in order for it to be on-topic Commented Sep 15, 2014 at 15:19 ## 1 Answer # Python, 308 Characters I chose not to go after the bonus because the last time I used VB was over a decade ago, and I am still suffering from the PTSD ;-) I didn't try and golf this very much because I'm not sure if that's the goal. This code is guaranteed to return a solution with the minimum number of transactions. def t(p): a=sum(p)/float(len(p)) q=[([],p)] l=len(p) r=range(l) while q: n=q.pop(0) g=1 for i in r: d=n[1][i]-a if d>0: g=0 for j in r: if n[1][j]<a: v=min(d,a-n[1][j]) y=list(n[1]) y[i]-=v y[j]+=v if i!=j:q+=[(n[0]+[(j,i,v)],y)] if g:return n[0]  ## Usage The t function takes a list of the amounts that each person paid. Using the example from the question: > print t([50,25,5,0]) [(2, 0, 15.0), (3, 0, 15.0), (3, 1, 5.0)]  So the solution is for person 2 (George) to pay person 0 (Dave)$15 and for person 3 (Barry) to pay 0 (Dave) $15 and also to pay 1 (John)$5.

• Many thanks. I'll try to convert this to VB. Commented Oct 24, 2012 at 21:25
• The basic idea is that I start off with no transactions and perform a breadth-first traversal of the search tree generated by enumerating all possible transactions that can occur at a given state from a person that owes money to a person that is owed money. Commented Oct 25, 2012 at 14:29