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

1 Answer 1

up vote 1 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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