At the heart of this application there is a binary file, written in C, which takes a list of numbers from standard input, and prints a list of transactions in the form A -> B : $X, where A and B are positions of numbers in the input list, and X is the amount of the transaction. For example, say the binary file was named "iou". Then running "./iou 2 4 6" would print 0 -> 2 : $2.00.
Since this kind of output isn't very meaningful to users, and there are more appropriate ways to parse names from input than with C, an intermediate step is required, between the web interface and the backend. This comes in the form of a perl script, acting as a wrapper for the binary file.
When the "Calculate IOU!" in pressed, some javascript goes to work formatting the list of names and amounts into two comma delimited strings. These strings are sent as params to the perl script, which separates them back into lists. A string representation of the list of amounts is created and the binary file is run with this string following. The script then replaces the numbers in the output of the binary with the corresponding names on its list of names, and formats it to be ready for the web (with some nice HTML). Finally, the script prints out what can be seen on the IOU page, which the javascript then stores, and places on the page.
Here is a description of the problem that this program solves:
There are n roommates sharing a house.
Over a period of time, they all spend money on communal items.
At some point they all decide to pay each other back.
They are all logicians, and want to pay each other back in the
least possible number of transactions.
Who pays what amount to whom?
Consider the following naive algorithm for calculating IOU's:
Since at each step, one person is removed, it would appear that this requires n transactions for a list of n people, however the last transaction must remove two people (one from each list), so there are actually n-1 transactions for a list of n people. This is not optimal. If there are any self contained sublists in the list of people, then the list can be split up into smaller systems, and the above algorithm can be applied to them.
The self contained property of these sublist requires that the sum of amounts owed is equal to the sum of the amounts owing.
Suppose k was the length of a given sublist. Then it would take k-1 transactions to resolve that sublist. If the main list can split up into m sublists, then it would take n-m transactions to resolve everyone.
The goal becomes to maximise m. To do this, the sum of all possible subsets (apart from {}) are calculated for the owing partition and the owed partition and stored in two lists. Then, the sum of every pair of numbers from these lists is found. In the event where the sum is zero, the combination of people from both list is stored as a potential subsystem. Now it is required to find the maximum valid combination of subsystems. The sum of all subsets of amounts payed in each subsystem are calculated and stored in a list. Then, out of all the subsets summing to the total amount to be payed, the one with the highest cardinality is found. This is the optimal subset, as it will maximise the number of subsystems. Each of the subsystems is then solved using the naive algorithm.