# 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? – Hasturkun Sep 6 '12 at 17:23 • @Hasturkun - Because I'd like to try this on an Excel spreadsheet. – Rocketmagnet Sep 6 '12 at 17:44 • id recommend having an exact win condition; before the heavy-handed moderators swing on by :) – NRGdallas Oct 24 '12 at 17:07 • you need to specify a winning condition for the question in order for it to be on-topic – proud haskeller Sep 15 '14 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. – Rocketmagnet Oct 24 '12 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. – ESultanik Oct 25 '12 at 14:29