Algorithm for student project

Hello devs,

I need help with my current project. I am building a Python application that tracks expenses for a group of users (Split Wise analog).

You can create “groups” and add users to these groups. A group can have one or more expenses (each expense is a number in USD). The application tracks how much each user paid for each expense.

The application should be able to tell the balance: how much any user owes to any other user based on group expenses (assuming all users should spend an equal amount for summary expenses). I need an algorithm how to calculate the balance.

Let’s take a look at a simplified example.
Say, we have a “Party” group with 3 users, John, Mary, and Maya. There are 2 expenses related to the “Party” group: “wine” ($30) and “food” ($60). Users paid:

Expense: “Wine” (30):

  • John: 0
  • Mary: 0
  • Maya: 30

Expense: “Food” (60):

  • John: 60
  • Mary: 0
  • Maya: 0

This means Maya bought all wine for $30 and John bought all food for $60.

let’s calculate the balance for the “Party” group.

Wine expense balance:

  • John owes Mary 0
  • John owes Maya 10
  • Mary owes John 0
  • Mary owes Maya 10
  • Maya owes John -10
  • Maya owes Mary -10

Hence, each user will spend 10.

Food Expense balance:

  • John owes Mary -20
  • John owes Maya -20
  • Mary owes John 20
  • Mary owes Maya 10
  • Maya owes John 20
  • Maya owes Mary 0

Hence, each user will spend 20.

Total balance for the “Party” group:

  • John owes Mary -20
  • John owes Maya -10
  • Mary owes John 20
  • Mary owes Maya 10
  • Maya owes John 10
  • Maya owes Mary -10

So the total spend of the group = 60 + 30 = 90. Each user should spend 90/3 = 30

John, Mary, and Maya will spend $30 each after:

Mary pays John 20 and Maya 10,
Maya pays John 10.

I need an algorithm (ideally a Python code) how to calculate the user balance for the group, sort of:

def calculate_balance(group_expenses):
    
    balance = {}

    # Do the magic here
    
    return balance


# Test the function with the example data
group_expenses = [
    {"John": 0, "Mary": 0, "Maya": 30},
    {"John": 60, "Mary": 0, "Maya": 0}
]

balance = calculate_balance(group_expenses)
print("John's balance:", balance["John"])  # {Mary: -20, Maya: -10}
print("Mary's balance:", balance["Mary"])  # {John:20, Maya: 10}
print("Maya's balance:", balance["Maya"])  # {John: 10, Mary: -10}

Because the example data is super simple and even I was able to sort out results intuitively. But at this point, I can’t develop a formula for calculating balance mathematically.

This is really a basic vector math problem, perfect for tech artists! In fact I did this in Maya so I could have vectors. In real computing you’d want to use something like NumPy to get arbitrary sized matrices and vectors.

import maya.api.OpenMaya as api

m = api.MMatrix
v = api.MVector # to handle up to 4 people, since maya matricxes are 4x4

# here the rows are food, "other", wine, and "other2"
# the columns are maya, mary, john, and "other"
expenses = m((
    0,     0,  60, 0,
    0,     0,   0, 0,
    30,    0,  0, 0,
    0,     0,  0,  0
) )

# each item in a vector-matrix multiply is basically the sum
# of a column.  So that would get ytou a flat list of totals:
person_totals = v(1.0,1.0,1.0 ) * expenses
print ("pay-ins", person_totals)

# total cost...
total_expenses  = sum(person_totals)                     
print ("total", total_expenses)

# we want each person to pay 1/3 of the total
final_shares = v(1,1,1) / 3.0

# here's what they actually paid as a % of the total
paid_shares = person_totals / total_expenses

#so the remainder are the difference between the expected fraction
# and the actual paid fraction, multiplied by the total again:
print ("payouts", (final_shares - paid_shares) * total_expenses)

this produces:

pay-ins (30, 0, 60)
total 90.0
payouts (0, 30, -30)

indicating that John is good and Mary pays Maya 30. If necessary you could iterate over the payouts to, say, minimize the number of payments from “positive” debtors to “negative” creditors but that’s a detail.

1 Like