Project 0: An Expense Splitting Calculator
The first small project that I wrapped up and posted started off as a python script that I created to solve a niche problem. After writing it, I kept coming back to the script wanting to use it time after time. After coming back to it for the 5th time, I thought it was useful enough to turn into a webapp, so I started building, secured a domain name (or two), and shipped.
Say hello to: okaytapin.com (or oktapin.com )
The entire webapp, in all its glory.
This small static webapp is written in vanilla HTML / CSS / JavaScript. It's an implementation of an algorithm that helps answer the age-old question of how a group of friends can split a set of expenses where different people paid for different pieces.
When I first thought of tackling this problem, I thought I could easily solve it with my limited spreadsheet skills, that is until I gave it a shot. Edge cases started cropping up left and right, and I quickly ran aground.
- What happens if I bought 2 plane tickets for two friends? Clearly, the two friends should split the cost of the plane tickets (assuming both tickets were cost the same price)
- What happens if I paid for something that we want to split 6 ways?
- What if three friends decided to sponsor a fourth friend's expenses and cover that friend's portion of the expenses?
I couldn't come up with a way to handle all cases like these without an iterative algorithm. I knew I wanted to build and simplify a debt matrix, but every solution I came up with involved an iterative algorithm in one way or another. So I ditched the spreadsheet and switched over to python for the initial version.
Debt Matrix
A debt matrix is a matrix with all participants along the rows and columns, where each cell represents how much money a participant owes another participant. Filling this debt matrix requires a for-loop over each transaction.
The webapp's default debt matrix, showing debts between four people named "A", "B", "C", and "D"
However, the webapp takes things a step further.
Transactions
Sure, this webapp calculates the final debt matrix between people for a set of expenses, but this webapp goes a step further and simplifies the debt matrix to minimize the number of transactions to settle all outstanding debts. Let me illustrate this with an example.
Say we have the following debt matrix:
An example debt matrix showing four pending transactions.
Here the debt matrix indicates that there are 4 outstanding transactions: 1. Bill must pay John $40.00 2. John must pay Steve $20.00 3. John must pay Adam $20.00 4. Adam must pay Steve $20.00
... and as shown by the transaction section, all 4 of those debts are settled with the single transaction: "Bill pays $40.00 to Steve"
Intuitively, if Bill hands John $40.00, and John immediately turns around and hands those $40.00 to both Steve and Adam, then John is just a middle man in this transaction. Cut him out!
Here's the updated debt table summary: 1. Bill must pay Steve $20.00 2. Bill must pay Adam $20.00 3. Adam must pay Steve $20.00
Awesome, now we're down to three transactions. Let's keep looking for middlemen to cut out. Just like the case before, Bill owes Steve $20.00 indirectly throught Adam, so if we cut out Adam as a middle-man and let Bill pay Steve directly, we are left with one final entry in the debt matrix:
- Bill must pay Steve $40.00
A single transaction!
Now I haven't sat down to prove this, but my intuition tells me that any NxN debt matrix can be completely settled with no more than N-1 transactions, and having a calculator that computes those N-1 transactions is pretty cool.
Sharing
The webapp has a few additional bells and whistles. I'm a huge fan of the Desmos graphing utility website, and I particularly like how its sharing mechanism works.
In Desmos, if I want to share the current state of some graph I'm staring at, I can hit the share button, and a unique link will be generated that recreates the exact state of the graph at the moment the link was generated. It makes sharing graphs super easy. It's not collaborative like Google Docs (two people can't edit the same graph at the same time, which is actually a good thing given how complicated desmos setups can become), but it works great for sharing. I send a friend a link to the graph I'm staring at, they make some changes, and share back a new link with their new changes. It just works!
In addition to making sharing easy, I also use this system to save intermediate graphs along the way. Click share, copy the link, stash it somewhere, and keep tinkering. I enjoy this workflow and its simplicity, so I sought to emulate it in the webapp.
Click "Share", and you'll get a URL encoded with the current webapp state.
When the "Share" buttin is clicked, the entire state of the webapp is encoded into the URL parameters. The webapp state is then decoded when the link is visited. Because the entire state is encoded into the URL, this can lead to some insanely long URLs, caveat emptor! Maybe some day I'll do something fancy like saving the state server-side and generating a unique ID / URL for that state (which would require having a backend, boo), or maybe I could try some compression techniques to shorten the length of the encoded state. Either way, sounds like a problem for future me.
Conclusion
Next time you've got a bunch of expenses to split from some trip with friends, and want to simplify your life, give it a shot!