Splitting The Bill

Question

Task

Suppose that p pepole have to split a bill; each of them is identified by a triple (Name, n, k) made up of:

• Name: the name;
• n: the amount she/he has to pay;
• k: the amount she/he actually paid.

The challenge here is to find out how much who owes whom.

Assumptions

• Input and output can be in any convenient format.

• p \$\in \mathbb{N}, \,\;\;\$n \$\in \mathbb{N}^{+},\;\$ k \$\in \mathbb{N}.\$

• p \$\gt 1.\$

• Names are unique strings of arbitrary length, composed of lower case alphabet characters.

Solution

The solution is represented by the minimum set of transactions among the p people; in particular they are triples (from, to, amount)

• from: name of the person that gives money;
• to: name of the person that receives money;
• amount: amount of money of the transaction.

NOTE: The sum of all the debts (n) can differ from the sum of all the already payed amounts (k). In this case, you must add in the output ('owner', Name, amount) or (Name, 'owner', amount) in the format you have chosen. Any name will never be owner.The string 'owner' is flexible.

If several mimimum sets exist, select the one with the minimum sum of all the transaction amounts (absolute values); in case of a tie, choose one of them.

Test Cases:

inputs(Name,n,k):
[('a',30,40),('b',40,50),('c',30,15)]
[('a',30,30),('b',20,20)]
[('a',30,100),('b',30,2),('c',40,0)]
[('a',344,333),('b',344,200),('c',2,2)]
[('a',450,400),('b',300,300),('c',35,55)]

outputs(from, to, amount):
[('c','a',10),('c','b',5),('owner','b',5)] or [('c','b',10),('c','a',5),('owner','a',5)]
[]
[('owner','a',2),('b','a',28),('c','a',40)] PS: [('owner','a',2),('b','a',68),('c','b',40)] has the same number of transactions, but it is not a valid answer, because the total amount of its transaction is greater than that of the proposed solution.
[('a','owner',11),('b','owner',144)]
[('a','owner',30),('a','c',20)]

This is code-golf: shortest code wins.

Answer 1

JavaScript (ES6),  252 227 223 222  215 bytes

Takes input as [[n0, k0, name0], [n1, k1, name1], ...].

Transactions in the solution may be either positive or negative. The owner is called undefined.

a=>(m=g=(B,t,s)=>B.some(x=>x)?B.map((b,x)=>B.map((c,y)=>b*c<0&b*b<=c*c&&g(C=[...B],[...t,[a[x][2],b,a[y][2]]],s+a.length-1/b/b,C[C[y]+=b,x]=0))):m<s||(r=t,m=s))([...a.map(([x,y])=>t-(t+=y-x),t=0),t],[],a.push(g))&&r

Try it online!

Commented

a => (                              // a[] = input array
  m =                               // initialize m to a non-numeric value
  g = (B, t, s) =>                  // g = function taking: B = balances, t = transactions,
                                    //     s = score of the current solution
    B.some(x => x) ?                // if at least one balance is not equal to 0:
      B.map((b, x) =>               //   for each balance b at position x:
        B.map((c, y) =>             //     for each balance c at position y:
          b * c < 0 &               //       if b and c are of opposite sign
          b * b <= c * c &&         //       and |b| <= |c|,
          g(                        //       do a recursive call to g:
            C = [...B],             //         - with a copy C of B
            [ ...t,                 //         - append the new transaction to t[]
              [a[x][2], b, a[y][2]] //           in [from_name, amount, to_name] format
            ],                      //
            s + a.length - 1/b/b,   //         - add (a.length - 1/b²) to s
            C[C[y] += b, x] = 0     //         - update C[y] and clear C[x]
          )                         //       end of recursive call
        )                           //     end of inner map()
      )                             //   end of outer map()
    :                               // else:
      m < s ||                      //   if the score of this solution is lower than m,
      (r = t, m = s)                //   update r to t and m to s
)(                                  // initial call to g:
  [                                 //   build the list of balances:
    ...a.map(([x, y]) =>            //     each balance is equal to:
      t - (t += y - x),             //     due_value - paid_value
      t = 0                         //     keep track of the total t ...
    ),                              //
    t                               //   ... which is appended at the end of this array
  ],                                //   (this is the balance of the owner)
  [],                               //   start with t = []
  a.push(g)                         //   append a dummy owner to a[]; start with s = 1
) && r                              // return r