29 Optimální splacení dluhů

var names = ['trojice']
var datasets = [
  {arg:[['alena', 100, 200], ['bronislav', 250, 150]], out: [['alena', 'bronislav', 100]]},
  {arg: [['a', 98, 13], ['b', 11, 27], ['c', 131, 12], ['d', 5, 19], ['e', 38, 123], ['f', 12, 109], ['g', 6, 12], ['h', 163, 4], ['i', 21, 176], ['j', 115, 105]], out: []},
]
function validator(result, dataset) {
  const arg = dataset.arg;
  const sum = {};
  for (const [j, _1, _2] of dataset.arg) {
    sum[j] = 0;
  }
  for (const [i, j, c] of result) {
    if (c <= 0) {
        return false;
    }
    sum[i] += c;
    sum[j] -= c;
  }
  return dataset.arg.every(([j, p, r]) => sum[j] == r - p);
}

Několik kamarádů jelo na výlet. Spoustu toho nakupovali společně, buďto pro všechny, anebo jen pro menší skupinu. Každý má zapsáno, kolik toho platil (celkem, za sebe i za ostatní) a kolik užíval (vyjádřeno v penězích, a skupinové platby jsou rozpočítané každému). Máme tedy záruku, že součet všech plateb se rovná součtu všech užívání.

Úkolem programu je naplánovat nanejvýš n - 1 plateb tak, aby dluhy byly splacené, kde n je počet kamarádů.

Vstupem je seznam trojic, kde každá se vztahuje k jednomu kamarádovi:

• první ve trojici je jméno dotyčného kamaráda,
• druhé je nezáporné číslo vyjadřující součet, kolik platil,
• třetí je nezáporné číslo vyjadřující součet, kolik užíval.

Platby mají být na výstupu vyjmenované jako seznam trojic:

• první číslo v trojici je index toho, kdo má platit,
• druhé číslo je index, komu má zaplatit,
• třetí číslo je kladná částka, kterou má poslat.

Pokud je možných víc řešení, pak program může vrátit libovolné z nich.

def main(trojice):
  # nahodile vybereme posledniho v seznamu
  p_jmeno, p_platil, p_uzival = trojice[-1]
  return [(a_jmeno, p_jmeno, a_uzival - a_platil)
      for a_jmeno, a_platil, a_uzival in trojice[:-1]]

Kdyby program směl vytvořit n * (n-1) / 2 plateb, bylo by to docela jednoduché, jenže to nesmí.