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.

  • 1
    I think you should change "You have to output the most simplified scenario which requires least number of transactions." to "You have to output the scenario which requires least number of transactions. If multiple such scenarios exist choose one with the least total notional of transactions." since I believe it is clearer. – Jonathan Allan Nov 19 at 7:59
  • 1
    Nice challenge. But it will probably require more complex test cases to make sure that solutions really are always optimal. – Arnauld Nov 19 at 9:16
  • 3
    What is "least total notional"? – lirtosiast Nov 19 at 9:26
  • 1
    @JonathanAllan still confused by the word “notional”. where is that coming from? based on test case 3 it looks like one should prefer answers where the same person does not both give and receive? is that correct? also why is that described as notional? – Jonah Nov 19 at 13:16
  • 1
    @Jonah I used "total notional" since the directions of the transactions should not be considered (just their absolute size), although I now realise it's somewhat redundant (as having two transactions that counteract each other wouldn't be considered once tie-breaking!). [Notional is just the term used in finance.] – Jonathan Allan Nov 19 at 14:47

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.