splitting the bill algorithmically & fair, afterwards :)

I'm trying to solve the following real-life problem you might have encountered yourselves:

You had dinner with some friends and you all agreed to split the bill evenly. Except that when the bill finally arrives, you find out not everyone has enough cash on them (if any, cheap bastards).

So, some of you pays more than others... Afterwards you come home and try to decide "who owes who what amount?".

This, I'm trying to solve algorithmically & fair :)

it seems so easy at first, but I'm getting stuck with rounding and what not, I feel like a total loser ;)

Any ideas on how to tackle this?

EDIT: Some python code to show my confusion

>>> amounts_paid = [100, 25, 30]
>>> total = sum(amounts_paid)
>>> correct_amount = total / float(len(amounts_paid))
>>> correct_amount
51.666666666666664
>>> diffs = [amnt-correct_amount for amnt in amounts_paid]
>>> diffs
[48.333333333333336, -26.666666666666664, -21.666666666666664]
>>> sum(diffs)
7.10542735开发者_高级运维76010019e-015

Theoratically, the sum of the differences should be zero, right?

for another example it works :)

>>> amounts_paid = [100, 50, 150]
>>> total = sum(amounts_paid)
>>> correct_amount = total / float(len(amounts_paid))
>>> correct_amount
100.0
>>> diffs = [amnt-correct_amount for amnt in amounts_paid]
>>> diffs
[0.0, -50.0, 50.0]
>>> sum(diffs)
0.0

---

http://www.billmonk.com/

Amongst others. The problem has already been solved. Many times over.

---

"Theoratically, the sum of the differences should be zero, right?"

Yes. Since you've used float, however, you have representation issues when the number of people is not a power of two.

Never. Use. float For. Finance.

Never

Always. Use. decimal For. Finance.

Always

---

The trick is to treat each person as a separate account.

You can easily determine (from the original bill) how much each person should pay. Set this as a negative amount for each person. Next, record the amount that each person has paid by adding the amount paid to their account. At this point, the people who have overpaid (lenders) will have positive balances, and the people who have underpaid (borrowers) will have negative balances.

There is no one right answer to which borrower owes money to each lender, except in the obvious case where there is only one lender. Amounts paid by a borrower can go to any of the lenders. Simply add the amount to the borrower's total, and subtract amounts from the lenders who receive the payment.

When all accounts hit zero, everyone has paid up.

Edit (in response to comments):

I think my problem lies with the fact that the amount is not always evenly divisible, so coming up with an algorithm that handles this elegantly seems to trip me up again & again.

When dealing with dollars and cents, there is no 100% clean way to handle the rounding. Some people will pay one cent more than others. The only way to be fair is to assign the extra $0.01 at random (as required). This would be done only once, when the "amount owed" is being calculated by dividing up the bill. It sometimes helps to store monetary values as cents, not as dollars ($12.34 would be stored as 1234, for example). This lets you use integers instead of floats.

To distribute the extra cents, I would do the following:

total_cents = 100 * total;
base_amount = Floor(total_cents / num_people);
cents_short = total_cents - base_amount * num_people;
while (cents_short > 0)
{
    // add one cent to a random person
    cents_short--;
}

Note: the easiest way to assign the pennies "randomly" is to assign the first extra cent to the first person, the second to the second, etc. This only becomes a problem if you always enter the same people in the same order.

---

I'm not a python guy, but I found it an interesting problem =) Here's my solution. Dev time ~45min. I write clean perl... should be easy to port.

~/sandbox/$ ./bistro_math.pl 
Anna owes Bill 7.57
Anna owes Mike 2.16
John owes Mike 2.62

~/sandbox/$ cat bistro_math.pl 
#!/usr/bin/perl
use strict;
use warnings;

### Dataset.
###    Bill total:  50.00
###    Paid total:  50.00
my @people = (
  { name => 'Bill', bill =>  5.43, paid => 13.00 },
  { name => 'Suzy', bill => 12.00, paid => 12.00 },
  { name => 'John', bill => 10.62, paid =>  8.00 },
  { name => 'Mike', bill =>  9.22, paid => 14.00 },
  { name => 'Anna', bill => 12.73, paid =>  3.00 },
);

### Calculate how much each person owes (or is owed: -/+)
calculate_balances(\@people);

### Tally it all up =)  This algorithm is designed to have bigger lenders
### paid back by the fewest number of people possible (they have the least
### hassle, since they were the most generous!).
sub calculate_balances {
  my $people = shift;

  ### Use two pools    
  my @debtors;
  my @lenders;

  foreach my $person (@$people) {
    ### Ignore people who paid exactly what they owed.
    $person->{owes} = $person->{bill} - $person->{paid};

    push @debtors, $person if ($person->{owes} > 0);
    push @lenders, $person if ($person->{owes} < 0);
  }

  LENDERS: foreach my $lender (@lenders) {
    next if ($lender->{owes} >= 0);

    DEBTORS: foreach my $debtor (@debtors) {
      next if ($debtor->{owes} <= 0);

      my $payment = ($lender->{owes} + $debtor->{owes} < 0) 
        ? abs $debtor->{owes} 
        : abs $lender->{owes};

      $lender->{owes} += $payment;
      $debtor->{owes} -= $payment;

      $debtor->{pays} = [] if (not exists $debtor->{pays});
      print "$debtor->{name} owes $lender->{name} $payment\n";

      next LENDERS if ($lender->{owes} >= 0);
    }
  }
}

exit;
~/sandbox/$ 

---

You know the total everyone owed, and who was short. Take that total short that everyone was and divy it out to those who paid more, starting from the highest overpayer to lowest.

---

The "problem" you are seeing has to do with binary representation of floating-point numbers as explained here. At any rate, 7.1054273576010019e-015 is a tiny, tiny number, so if you round your results to the nearest cent, as you should, you wouldn't have any problems.