I've been waiting to do a write up of this forever, it is probably the side project that was most useful for the longest, even though the actual algorithm makes me embarrassed, but anyone that talked with me for more than a couple hours probably already had to endure me talking about it.
The last place I lived in was a house for 8 people, we were all friends and shared expenses equally. We had no shared bank account, or any money stored, any expenses on the house(including bills or investments) were noted somewhere so that at the end of the month the people that did not pay anything would transfer their share to the people that paid for stuff. The first step for simplifying this seems obvious, we made a spreadsheet where we would input each expense in a row, and each column represented how much each person spent, and would output how much each person had to receive/ pay up. Here is an example of the spreadsheet:
In this example, Person A paid $150 for water bills, Person B paid 80 for electricity bills, and Person C paid 10$ for some new kitchenware. In total, we spent $240, so if we spent all this money from some joint account, on a house of 8 people, everyone should transfer $30 to that joint account and be done with it. However, such a joint account does not exist, we spent that money from our personal money, so Person A and Person B should receive some money, and Person C should have to pay a little less. That's exactly what the last row shows. This worked fine for a year, but we still needed a person to transform these totals into multiple payments between people in the house. This is where the interesting part begins. We had people with accounts on multiple banks, for some people it was easier to transfer money to certain people, for others, with different banks, it was much harder(For example, Person A has accounts on the same bank as Person B, but transferring to Person C is hard because he has to pay taxes to transfer to that bank). I spent that entire year thinking how to automate the decisions of who has to transfer to who, but could never come up with anything. When the person responsible for this left the house, I decided to really try to solve this problem, and even asked for help.
Turns out even the simpler version of this problem, where there are no easier/harder transfers(all transfer have the same cost) is already NP-Hard, it is the Subset Sum problem. At this point, I lost hope of finding a good solution for my problem, and even though it seemed generic enough for some research, I knew that nothing would be really really good, but still wanted solve it somehow for next month's bills. So I decided to brute force my way through. I tried to describe the idea behind my solution in the stack overflow question, not sure if it was clear enough, but at least I tried. Initially I did it in python, but the recursion I used turned out so slow, I redid it in C to get it down to times I didn't get impatient waiting. In the end, I was not even sure it always gave the best solutions(I did multiple tests, and every time I found cases that could be solved better, I made it slower to find these solutions), and it performed as badly as expected. The following plot shows time spent calculating depending on the number of people to organize(ran on a Ryzen 3950x):
As you can see, I had to put it in logarithm scale so we could actually see something. I'm not remotely proud of this performance, but I wanted to solve this quickly before I lost interest in this project, and it's still acceptable performance for 8 people, so I learned to live with it.
Ok, so at this point I have a C program that receives debts and costs, and spills me all necessary transfer to be made. Classically, I could spend 1 minute every month running this program, or I could automate it. But if I automate it, I could also add some cool nice-to-haves. It just so happens that all communication groups related to the house are on Telegram, and Telegram has bots. I set out to make a bot with the following requirements:
- At the end of every month, the bot will warn everyone it is time to settle debts
- It will wait for people to agree that everything on the spreadsheet was correct, or postpone to the other day if we still needed time to settle everything
- If everything is OK, it will pull data from the appropriate month on the spreadsheet, pipe it to the algorithm we described above and send the results in a well formatted message to the group
- It will wait for people to respond the message saying they paid up, tracking who still has debts to settle
- Every day at a set time, it will remind the people that didn't pay up yet(this is the final reason that convinced me to make the telegram bot, I wanted to automate the process of bugging people)
And so I did. The code ended up very messy, but the utility was okay.
Here is the bot, at the beginning of the month telling everyone that it is time to settle debts, and informing the commands for postponing or advancing(never mind my custom theme(I have that background in svg by the way, if anyone is interested)).
After this message, the bot waits 8 hours for people to send in commands to postpone or advance the calculation. This is necessary because frequently, people haven't put everything they paid for in the spreadsheet yet. If enough postpone commands are received, the bot won't do anything today, and will start the same process next day. If 8 hours pass, or enough advance commands are received, he will fire the calculator, and then send the following message:
The table informs all transactions that must be made, we use a 3 letter code that is basically an abbreviation of each person's name. To make everyone's life easier, the bot may choose to keep some debts for next month(nothing big, normally some cents ) to facilitate transactions. These debts are automatically added to next month's spreadsheet.
Everyday at midday, the bot sends a reminder message with the missing transactions, and tags everyone that still has to pay, the reminder looks like this:
People have to respond to either the message containing the original table or any of the reminders with various forms and tenses of the word "paid". The person can also chose to settle only it's debts with a certain person, in case of more than one pending transaction, or to pay only a certain amount and still be reminded later of the remaining value):
When all debts are settled, the bot thanks everyone and stays silent the rest of the month(unless someone asks for a simulation of the next payment, which is very, very rarely used…).
Fortunately (or sadly, for my bot), now in Brazil we have a service called Pix, that made it very easy to transfer money between banks, and so every transaction has virtually zero cost. Simplifying transactions is now the same as solving the subset sum problem, for which I can definitely find a much better algorithm online, as it's a much more common problem. One could argue the bot is no longer necessary, and there are less buggy apps to do this, and they certainly wouldn't require tweaking from time to time(every new year I have to update the spreadsheet link, every new resident I have to update the Users database, etc), but I still had a lot of fun doing it, and it was useful for years, so I have absolutely no regrets. Maybe someone someday needs something similar and finds this? Who knows. I just hope this person is brave enough to go through all the mess of Portuguese mixed with English that is the bot code(Not the calculator though, I tried my best to make it's code the cleaner I could, as this is the most reusable and novel part of this. Anyone can quickly make a telegram bot nowadays, so I didn't care about cleaning this part of the code too much).