# Expense Sharing Calculation

The following is my solution to the problem presented on this CodeReview post:

Friends A, B, C, D go for a trip. They spend on various expenses. Cost of the expense is shared.

Example :

• A spends 100 for breakfast for A, B, C and D
• D spends 500 for cab for B and C
• B spends 300 for lunch for A, B and C

Write a program to calculate how much each should get or each should give to one another. App should be scalable that number of friends can change

Design:

We need two data sets, which each respectively:

• record transactions
• tally amount due to each person

Simply strip off the info we need from the transactions and record either how much each person is owed, or how much each person should give.

Any input is welcome!

using System;
using System.Collections.Generic;

namespace CodeReview
{
class Transaction
{
class Account
{
private int totalDebt = 0;
private Dictionary<char, int> debtors = new Dictionary<char, int>();

public Account(char initialDebtor, int initialDebt)
{
debtors.Add(initialDebtor, initialDebt);
}

public Dictionary<char, int> Debtors
{
get
{
return debtors;
}
}

public int TotalDebt
{
get
{
foreach (char debtor in debtors.Keys)
{
totalDebt += debtors[debtor];
}

return totalDebt;
}
}
}

static void Main(string[] args)
{
Queue<Tuple<char, int, List<char>>> transactions = new Queue<Tuple<char, int, List<char>>>();
Dictionary<char, Account> ledger = new Dictionary<char, Account>();

transactions.Enqueue(Tuple.Create('A', 100, new List<char>() { 'A', 'B', 'C', 'D' }));
transactions.Enqueue(Tuple.Create('D', 500, new List<char>() { 'B', 'C' }));
transactions.Enqueue(Tuple.Create('B', 300, new List<char>() { 'A', 'B', 'C' }));

while (transactions.Count > 0)
{
Tuple<char, int, List<char>> transaction = transactions.Dequeue();

foreach (char beneficiary in transaction.Item3)
{
if (!beneficiary.Equals(transaction.Item1))
{
if (ledger.ContainsKey(beneficiary))
{
Dictionary<char, int> debtors = ledger[beneficiary].Debtors;

if (debtors.ContainsKey(transaction.Item1))
{
debtors[transaction.Item1] += transaction.Item2;
}
else
{
debtors.Add(transaction.Item1, transaction.Item2);
}
}
else
{
ledger.Add(beneficiary, new Account(transaction.Item1, transaction.Item2));
}
}
}
}

foreach (char beneficiary in ledger.Keys)
{
Account account = ledger[beneficiary];

Console.WriteLine("User " + beneficiary + " owes $" + account.TotalDebt + ":"); foreach (char debtor in account.Debtors.Keys) { int debt = account.Debtors[debtor]; Console.WriteLine(" -$" + debt + " to " + debtor);
}
}

Console.ReadKey();
}
}
}

• Does the program actually solves the problem? Write a program to calculate how much each should get or each should give to one another. I would expect something like: A -> B: 200, A -> D: 400, B -> D 300, C -> A: 100, C -> D: 500, C -> B: 300, ... as result. – JanDotNet Oct 13 '17 at 12:26
• @JanDotNet That solution is exactly what the second part of the question is asking for. Since that solution is harder, I went w/ the first option. This is detailed in the "Design" portion of the block comment. – T145 Oct 13 '17 at 13:30
• I don't understand the question that way, but OK. It is not common for programming problems to have one simple and one hard solution ;) – JanDotNet Oct 13 '17 at 13:38
• @JanDotNet Honestly I didn't find the second solution harder; it just has a performance that's worse than the first. I've added in my take on the second solution. Enjoy! – T145 Oct 13 '17 at 14:05
• IMO, it is still not the correct solution for the problem. Again, the correct answer should look like: A owes B 200, A owes D 400, B owes D 300, C owes A 100, C owes D 500, C owes B 300 and C owes A 100. – JanDotNet Oct 13 '17 at 18:39

## 3 Answers

• The main issue I can see, is the excessive use of generic data types like tuples and dictionaries instead of domain classes. That may be a matter of taste, but I prefer meaningful named domain classes like your Account class.

• In the Account class, the dictionary is exposed as public member. IMHO internal data structures should be encapsulated. The class should be extended by appropriated methods to manipulate that data structures. That would automatically move code like

if (debtors.ContainsKey(transaction.Item1))
{
debtors[transaction.Item1] += transaction.Item2;
}
else
{
debtors.Add(transaction.Item1, transaction.Item2);
}


into the domain class. Imagine use have to add items somewhere else, that kind of code must be duplicated each time.

• Instead of
if (!beneficiary.Equals(transaction.Item1))
{
...
}


You could use

 if (beneficiary.Equals(transaction.Item1))
{
continue;
}

....


to reduce nesting.

• The instance variable debtors should be read-only.

• Another small point: I would use strings to store the users because you can store names and you do not run into problems if the group becomes greater than 26 persons :P - of course, that is not relevant for the algorithm.

Generall Approach

Your approach is, to build up two dictionaries (the ledger and the debtors within the account class). The data structure of nested dictionaries matches the requirements exactly. If the requirements change, you have to restructure your whole code.

It is better to transform the data in a simple generally usable data structure and implement your algorithm for that data structure.

Such a simple data structure may be a list of Transactions:

public class Transaction
{
public Transaction(string payer, string payee, int amount)
{
Payer = payer;
Amount = amount;
Payee = payee;
}

public string Payer { get; }
public int Amount { get; }
public string Payee { get; }
}


The algorithms could be implemented in a class like Bank:

public class Bank
{
private readonly List<Transaction> myTransactions = new List<Transaction>();
private readonly HashSet<string> myPayers = new HashSet<string>();
private readonly HashSet<string> myPayees = new HashSet<string>();

public void AddTransaction(string payer, string payee, int amount)
{
myTransactions.Add(new Transaction(payer, payee, amount));
myPayers.Add(payer);
myPayees.Add(payee);
}

public void PrintPayees()
{
foreach (var payee in myPayees)
{
var trans = myTransactions.Where(t => t.Payee == payee);
Console.WriteLine($"User {payee} owes${trans.Sum(t => t.Amount)} total:");
foreach (var groupedTransaction in trans.GroupBy(t => t.Payer))
Console.WriteLine($"-${groupedTransaction.Sum(t => t.Amount)} from {groupedTransaction.Key}");
}
}

public void PrintPayer()
{
foreach (var payer in myPayers)
{
var trans = myTransactions.Where(t => t.Payer == payer);
Console.WriteLine($"User {payer} gets${trans.Sum(t => t.Amount)} total:");
foreach (var groupedTransaction in trans.GroupBy(t => t.Payee))
Console.WriteLine($"-${groupedTransaction.Sum(t => t.Amount)} to {groupedTransaction.Key}");
}
}
}


Usage base on the list of tuples:

void Main()
{
var bank = new Bank();

foreach (var transaction in new[] { Tuple.Create("A", 100, new [] { "A", "B", "C", "D" }),
Tuple.Create("D", 500, new [] { "B", "C" }),
Tuple.Create("B", 300, new [] { "A", "B", "C" }) })
{
var payer = transaction.Item1;
var amount = transaction.Item2;
foreach (var payee in transaction.Item3)
if (payee != payer)
bank.AddTransaction(payer, payee, amount);
}

bank.PrintPayees();
bank.PrintPayer();
}


I reviewed your code. I wanted to give you some feedback and share my approach to the problem.

Your code relies on some advanced data structures such as Queues and Dictionaries, and I am fond of those things, but in the interest of readability, maintainability, and simplicity, I took a class-based approach, with advanced data structures as required. One of the main principles I follow in object-oriented programing (OOP) is "Let the objects do the work."

First let's review the output of your program: The amounts that people owe and the amounts people pay are incorrect. The total of all the transactions is $900, so how can C alone owe$900? D owes 1/4 of the $100 breakfast she participated in, not the full$100, and she winds up netting $900 on the deal (as highlighted). When I first reviewed your code, it was unclear how it was solving the problem. When I ran it, the output showed that it wasn't. The key thing I think you're missing is calculating each participant's liability for each transaction. I see that you are grouping by Payer, but what's missing is calculating the liability per participant. Rather than pinpoint the bugs in your code, I figured that demonstrating my approach would give you some food for thought. I invite you to review my approach. I wanted to solve the problem with classes, and respect their autonomy - i.e. avoid manipulating their data from outside, ask them nicely to do things, etc. For the sake of anyone first encountering this post, this is the 4th iteration of my solution. The first two suffered from my own lack of properly reading the problem. One thing that tripped me up initially was the fact that D paid for a cab for B & C, but did not ride in the cab, so should get all their money back instead of paying 1/3 of the fare. Here's the output: Each transaction shows the payments to balance itself, then the reconciliation gives us the net payments across all transactions. In this case it combines "A pays B$25" and "B pays A $100", into "B pays A$75".

The net payments calculation requires matching transactions by both parties, regardless of side. While my LINQ skills are improving, there may be a more efficient way to do it.

I have also added the ability to read the transactions from a file formatted like this:

A,100,breakfast,A,B,C,D
D,500,cab,B,C
B,300,lunch,A,B,C


And I have added a random transaction generator. Here's the output from 30 random transactions: I have also improved the logic that determines if an Account has a credit or debit balance, and to avoid plunging further into rounding madness, it now ignores balances of +/-$0.01. using System; using System.Collections.Generic; using System.IO; using System.Linq; namespace CodeReview { //https://codereview.stackexchange.com/questions/177795/expense-sharing-calculation public class App_ExpenseEqualizer { private Random rnd = new Random(); public void Run(string fileName = @"d:\temp\expenses.txt") { //pick one source for the transactions //(i.e. - uncomment only one of the lines that sets "t" //Hardcoded transactions from the problem definition //var t = transactions(); //Get transactions from a file //var t = transactionsFromFile(fileName); //Get Random transactions var t = randomTransactions(rnd, 30); //Show transaction detail before processing //t.ForEach(u => u.Print()); var rec = new Reconciliation(t); rec.PrintTransactions(); rec.Reconcile(); Console.WriteLine(); rec.PrintNetPayments(); } private List<Transaction> transactions() { var list = new List<Transaction>(); list.Add(new Transaction("breakfast", new List<Participation> { new Participation(new Person("A"), 100), new Participation(new Person("B")), new Participation(new Person("C")), new Participation(new Person("D")) })); list.Add(new Transaction("taxi", new List<Participation> { new Participation(new Person("B")), new Participation(new Person("C")), new Participation(new Person("D"), 500, particpated: false) })); list.Add(new Transaction("lunch", new List<Participation> { new Participation(new Person("A")), new Participation(new Person("B"), 300), new Participation(new Person("C")) })); return list; } private List<Transaction> randomTransactions(Random rnd, int count) { var list = new List<Transaction>(); var i = 0; list.AddRange(Enumerable.Range(1, count).Select(x => randomTransaction(rnd, ++i)).ToList()); return list; } private Transaction randomTransaction(Random rnd, int i) { var maxParticipants = 3; return new Transaction($"evt{pad(i.ToString(),'0',3)}", randomParticipations(rnd, maxParticipants));
}

private string pad(string s, char c, int len)
{
var num = len - s.Length > 0 ? len - s.Length : 0;
return $"{new String(c, num)}{s}"; } private List<Participation> randomParticipations(Random rnd, int count) { var num = rnd.Next(1, count); var list = new List<Participation>(); var payer = randomPayerParticipation(rnd); list.Add(payer); var people = randomPeople(rnd, count, exclude:payer.Person.Id); list.AddRange(people.Select(p=>new Participation(p)).ToList()); return list; } private Participation randomPayerParticipation(Random rnd) { return new Participation(randomPerson(rnd), randomAmount(rnd), rnd.Next(10) < 8); //80% chance that they participated } private List<Person> randomPeople(Random rnd, int count, string exclude) { var list = Enumerable.Range(1, count + 1).Select(x => randomPerson(rnd)).Distinct(new PersonCompare(i => i.Id)).ToList(); return list.Where(p => !p.Id.Equals(exclude)).Take(count).ToList(); } private Person randomPerson(Random rnd) { //string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; string chars = "ABCDEFG"; var people = chars.Select(c => new Person(c.ToString())).ToList(); var person = people.ElementAt(rnd.Next(0, chars.Length - 1)); return person; } private decimal randomAmount(Random rnd) { var min = 1; var max = 1500; return rnd.Next(min, max); } private List<Transaction> transactionsFromFile(string path) { var lines = File.ReadAllLines(path); return lines.Select(l => toTransaction(l)).ToList(); } private Transaction toTransaction(string line) { var tokens = line.Split(','); var payer = new Person(tokens); var amount = decimal.Parse(tokens); var name = tokens; var participants = tokens.Skip(3).Select(t => new Person(t)).OrderBy(p=>p.Id).ToList(); var participation = new List<Participation>(); //payer participation.Add(new Participation(payer, amount, participants.Select(p=>p.Id).Contains(payer.Id))); participation.AddRange(participants.Where(p => p.Id != payer.Id).Select(p => new Participation(p, 0)).ToList()); return new Transaction(name, participation); } } public class Reconciliation { private List<Transaction> transactions; public decimal TotalAmount { get { return transactions.Sum(t => t.TotalAmount); } } public List<Payment> AllPayments { get { return transactions.SelectMany(t => t.Payments).ToList(); } } public List<Payment> NetPayments { get { var separator = '~'; //group payments that involve the same parties so we can net them out var a = AllPayments .GroupBy(p =>$"{p.Party1.Id}{separator}{p.Party2.Id}")
.Select(g => new
{
g.Key,
Amount = g.Sum(w => w.SignedAmount)
})
.ToList();

//create the new set of net payments
return a.Select(p => toPayment(p.Key, p.Amount, separator)).ToList();
}
}

public Reconciliation(List<Transaction> transactions)
{
this.transactions = transactions;
}

public void Reconcile()
{
transactions.ForEach(t => t.Reconcile());

//transactions.ForEach(t => t.Print());
}

private Payment toPayment(string key, decimal amount, char separator)
{
var parties = key.Split(separator);

var flip = amount < 0;

var payerSlot = flip ? 1 : 0;

var recipientSlot = flip ? 0 : 1;

var payer = new Person(parties[payerSlot]);

var recipient = new Person(parties[recipientSlot]);

return new Payment(payer, recipient, Math.Abs(amount));
}

public void PrintTransactions()
{
transactions.ForEach(t => Console.WriteLine(t.ToString()));
}

public void PrintNetPayments()
{
Console.WriteLine("Net Payments:");
NetPayments.OrderBy(p=>p.Payer.Id).ThenBy(p=>p.Recipient.Id).ToList().ForEach(p => Console.WriteLine(p.ToString()));
}
}

public class Transaction
{
private List<Account> debtors
{
get
{
return Accounts
.Where(a => a.OwesMoney)
.OrderBy(a => a.Balance)
.ToList();
}
}

private List<Account> creditors
{
get
{
return Accounts
.Where(a => a.IsOwed)
.OrderByDescending(a => a.Balance)
.ToList();
}
}

private bool debtRemains
{
get
{
return debtors.Where(a => a.OwesMoney).Any();
}
}

public string Name { get; set; }

public decimal TotalAmount
{
get
{
return AllParticipation.Sum(p => p.AmountPaid);
}
}

public List<Person> People
{
get
{
return AllParticipation.Select(p => p.Person).Distinct(new PersonCompare(i => i.Id)).ToList();
}
}

public List<Participation> AllParticipation { get; set; }

public List<Participation> PaidParticipation
{
get
{
return AllParticipation.Where(p => p.AmountPaid > 0).ToList();
}
}

public List<Participation> ActivityParticipation
{
get
{
return AllParticipation.Where(p => p.Particpated).ToList();
}
}

public List<Person> Payers
{
get
{
return PaidParticipation.Select(p => p.Person).ToList();
}
}

public List<Person> ActivityParticipants
{
get
{
return ActivityParticipation.Select(p => p.Person).ToList();
}
}

public int NumParticipants
{
get
{
return AllParticipation.Where(p => p.Particpated).Count();
}
}

public decimal LiabilityPerParticipant
{
get
{
decimal x = 0;

if(NumParticipants > 0)
{
x = Decimal.Round(TotalAmount / NumParticipants, 2);
}

return x;
}
}

public List<Account> Accounts
{
get
{
return People.Select(p => p.Account).ToList();
}
}

public List<Payment> Payments { get; private set; } = new List<Payment>();

public Transaction(string name, List<Participation> allParticipation)
{
Name = name;
AllParticipation = allParticipation;
Accounts.ForEach(a => a.Apply(this));
}

public void Reconcile()
{
calculatePayments();
}

private void calculatePayments()
{
while (debtors.Count > 0 && creditors.Count > 0)
{
var debtor = debtors.First();

var creditor = creditors.First();

decimal amount = 0;

amount = debtor.AbsBalance >= creditor.AbsBalance ? creditor.AbsBalance : debtor.AbsBalance;

var p = new Payment(debtor.Owner, creditor.Owner, amount);

debtor.Deduct(amount);

creditor.Pay(amount);

Payments.Add(p);
}
}

public void Print()
{
Console.WriteLine(ToString());
Console.WriteLine(LiabilityToString());
PrintAccounts();
PrintPayments();
Console.WriteLine();
}

public void PrintAccounts()
{
Accounts.ForEach(a => Console.WriteLine(a.ToString()));
Console.WriteLine();
}

public void PrintPayments()
{
Payments.ForEach(p => Console.WriteLine(p.ToString()));
}

public string LiabilityToString()
{
var participants = string.Join(", ", ActivityParticipants.Select(p => p.Id).OrderBy(p => p));

return $"{participants} each owe${ LiabilityPerParticipant,4}";
}

public override string ToString()
{
var payers = string.Join(", ", Payers.Select(p => p.Id));

var participants = string.Join(", ", ActivityParticipants.Select(p => p.Id).OrderBy(p=>p));

return $"{payers} paid${TotalAmount,5} for {Name} for {participants}";
}
}

public class Account
{
public Person Owner { get; private set; }

public decimal Paid { get; private set; }

public decimal Liability { get; private set; }

public decimal Balance
{
get
{
return Rounding.RoundDown(Liability - Paid, 2);
}
}

public decimal AbsBalance
{
get
{
return Math.Abs(Balance);
}
}

public bool OwesMoney
{
get
{
return Balance != 0m && Balance > 0.01m;
}
}

public bool IsOwed
{
get
{
return Balance != 0m && Balance < 0.01m;
}
}

public Account() { }

public Account(Person owner)
{
Owner = owner;
}

public void Apply(Transaction trans)
{
Paid += trans.PaidParticipation.Where(p => p.Person.Equals(Owner)).Sum(p => p.AmountPaid);

if (trans.ActivityParticipants.Contains(Owner))
{
Liability += trans.LiabilityPerParticipant;
}
}

public void Pay(decimal amount)
{
Paid -= Rounding.RoundUp(amount, 2);
}

public void Deduct(decimal amount)
{
Paid += Rounding.RoundUp(amount, 2);
}

public void Print()
{
Console.WriteLine(ToString());
}

public override string ToString()
{
return $"{Owner.Id,-5} Liability:${Liability,7} \tPaid: ${Paid,7} \tBalance:${Balance,7}";
}
}

public class Participation
{
public Person Person { get; private set; }

public decimal AmountPaid { get; private set; }

public bool Particpated { get; private set; }

public Participation (Person person, decimal amountPaid = 0, bool particpated = true)
{
Person = person;
AmountPaid = amountPaid;
Particpated = particpated;
}
}

public class Person
{
public string Id { get; private set; }

public Account Account { get; private set; }

public Person(string id)
{
Id = id;
Account = new Account(this);
}
}

public class Payment
{
private Person party1;

private Person party2;

private decimal amount;

private bool flip;

public Person Party1 { get { return party1; } }

public Person Party2 { get { return party2; } }

public Person Payer { get { return flip ? party2 : party1; } }

public Person Recipient { get { return flip ? party1 : party2; } }

public decimal Amount { get { return Math.Abs(amount); } }

public decimal SignedAmount {get { return amount; } }

public Payment(Person payer, Person recipient, decimal amount)
{
flip = flipParties(payer, recipient);

party1 = flip ? recipient : payer;

party2 = flip ? payer : recipient;

this.amount = flip ? -amount : amount;
}

public void Execute()
{
Payer.Account.Deduct(amount);
Recipient.Account.Pay(amount);
}

public override string ToString()
{
return $"{Payer.Id} pays {Recipient.Id}${Amount}";
}

private bool flipParties(Person p1, Person p2)
{
return string.Compare(p1.Id, p2.Id) > 0;
}
}

//https://www.codeproject.com/Articles/535374/DistinctBy-in-Linq-Find-Distinct-object-by-Propert
public class PersonCompare : IEqualityComparer<Person>
{
private Func<Person, object> _funcDistinct;

public PersonCompare(Func<Person, object> funcDistinct)
{
_funcDistinct = funcDistinct;
}

public bool Equals(Person x, Person y)
{
return _funcDistinct(x).Equals(_funcDistinct(y));
}

public int GetHashCode(Person obj)
{
return _funcDistinct(obj).GetHashCode();
}
}

//https://stackoverflow.com/questions/13482159/how-to-round-up-or-down-in-c
public static class Rounding
{
public static decimal RoundUp(decimal number, int places)
{
decimal factor = RoundFactor(places);
number *= factor;
number = Math.Ceiling(number);
number /= factor;
return number;
}

public static decimal RoundDown(decimal number, int places)
{
decimal factor = RoundFactor(places);
number *= factor;
number = Math.Floor(number);
number /= factor;
return number;
}

internal static decimal RoundFactor(int places)
{
decimal factor = 1m;

if (places < 0)
{
places = -places;
for (int i = 0; i < places; i++)
factor /= 10m;
}

else
{
for (int i = 0; i < places; i++)
factor *= 10m;
}

return factor;
}
}
}

• Yes, the only thing I forgot to do in my implementation was to fix it so that the amount that person owed was a ratio of the total amount owed to the number of indebted. It's an easy fix. If you want a review on your solution, post it on a thread of your own and link this one! – T145 Dec 8 '17 at 3:50
• I had a couple errors in the data initialization methods - i.e. I had set different people to pay than defined in the problem. I fixed those and updated the output. – Aron Dec 8 '17 at 14:41
• Shout out to Dino for pointing out another error in my logic. Right now the code assumes that the person who pays is also a participant in the transaction. But for the cab ride, D pays $500 for B and C, while not participating himself. When I get time I'll rework the code to accommodate for that. – Aron Dec 8 '17 at 18:15 • I just posted my latest version, which I think has worked out the kinks. The prior issues stemmed from me missing some details in the question. For the record, Dino's Perl version weighed in at ~50 lines (without much prettifying of the output.) That's why I say, "Never play code golf with a Perl guy." – Aron Dec 9 '17 at 16:44 • I just posted version 4 with some enhancements, including the ability to get transactions from a file or generate them randomly. – Aron Dec 10 '17 at 14:56 In the course of debating the merits of OOP with my friend Dino the Perl guy, I also implemented it as a one-liner in LINQ: using System; using System.IO; using System.Linq; namespace Expenses { public class ExpensesLINQ { public void Run(string path = @"d:\temp\expenses.txt") { File.ReadAllLines(path) .Select(l => l.Split(',')) .Select(x => Tuple.Create(x, x, x, string.Join(",", x.Skip(3)))) .SelectMany(b => b.Item4.Split(',') .Where(f => f != b.Item1) .Select(f => new { Party1 = string.Compare(f, b.Item1) > 0 ? f : b.Item1, Party2 = string.Compare(f, b.Item1) > 0 ? b.Item1 : f, Amt = string.Compare(f, b.Item1) > 0 ? decimal.Parse(b.Item2) / b.Item4.Split(',').Count() : -decimal.Parse(b.Item2) / b.Item4.Split(',').Count(), })) .GroupBy(p => new { p.Party1, p.Party2 }) .Select(g => new { Party1 = g.Key.Party1, Party2 = g.Key.Party2, Amount = g.Sum(w => w.Amt) }) .Select(h => new { Payer = h.Amount < 0 ? h.Party2 : h.Party1, Recipient = h.Amount < 0 ? h.Party1 : h.Party2, Amount = Math.Abs(h.Amount) }) .Select(o =>$"{o.Payer} pays {o.Recipient} \${o.Amount}")
.ToList()
.ForEach(t => Console.WriteLine(t));
}
}
}

• Sorry, but this is totally incomprehensible because of the poor variable and method names and confusing indentation. – t3chb0t Jan 16 '18 at 5:20