Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question

put on hold as off-topic by Geobits, Timtech, es1024, user23013, proud haskeller 18 hours ago

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – Geobits, Timtech, es1024, user23013, proud haskeller
If this question can be reworded to fit the rules in the help center, please edit the question.

2  
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
1  
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 18 hours ago

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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

Not the answer you're looking for? Browse other questions tagged or ask your own question.