Dette indlæg er alene udtryk for skribentens egen holdning.

Protip: Buddyledger deling af udgifter mellem venner

24 kommentarer.  Hop til debatten
Blogindlæg31. december 2015 kl. 17:12
errorÆldre end 30 dage

Kender I det at man skal holde nytårsfest eller andre ting, hvor flere skal dele udgifterne?

Så er det på tide at du lærer den lille applikation Buddyledger at kende. Den er lavet af Thomas Rasmussen, i daglig tale tykling. Han har lavet den som open source på https://github.com/tykling/buddyledger/blob/master/README.md men den findes online på https://buddyledger.baconsvin.org/

Problemet er:

  • Jeg køber kød 249kr
  • Du køber tilbehør 123kr
  • Alex køber sodavand 456kr
  • osv.
  • Bent, Ole og Georg skal dele en flaske vodka som Ole har købt, men de andre skal ikke betale denne udgift
  • Alle skal dele maden

Pyha, men her kommer Buddyledger flyvende ind og håndterer det hele! DET HELE!

Artiklen fortsætter efter annoncen

Lad os springe ud i det, jeg har her oprettet en ny ledger, indtastet personnavne og smider en udgift ind.

Denne udgift er betalt af HLK - 249kr og da den skal deles mellem alle er alle personer tilføjet - så alle skal have andel i denne udgift.

Lad os så antage jeg har tastet resten ind, og kommer til vodkaen som skal deles mellem tre.

og resultatet, alle udgifter registreret. Forestil jer en uge i Tyskland til summer camp med mad, øl, og diverse andre udgifter! Pyha!

og hvad så? Hvem skylder hvem og hvor meget? Tryk på knappen Result - og vupti! Alle udgifterne er delt og opsummeret.

Det er fandme smart! Så med Swipp og mobilepay er der hurtigt afregnet og alle kan være glade og fulde.

Godt nytår til alle og tak for opmuntring, diskussioner og snak i året 2015.

24 kommentarer.  Hop til debatten
Fortsæt din læsning
Debatten
Log ind for at deltage i debatten.
settingsDebatindstillinger
24
4. januar 2016 kl. 11:49

Sehttp://c2.com/doc/expense/

Ward Cunningham, som er en af opfinderne bag wiki skrev ovenstående program i 1981.

Et elegant script på få linjer :-)

23
3. januar 2016 kl. 19:41

Det er rigtigt. Så minimering af \sum_{i, j \in P} My_{ij} + x_{ij} at foretrække.

21
3. januar 2016 kl. 19:09

Jo, x variablerne er unbounded.

Du har ret i at man bør også bør minimere afregningsbeløbet, hvilket din objektfunktion gør.

Jeg kan ikke gennemskue om minimering af \sum_{i, j \in P} y_{ij} implicit vil minimere afregningsbeløbet. Hvis en person betaler mere end nødvendigt, skal det tilbageføres til den pågældende person. Spørgsmålet er om dette altid vil gøre at en ekstra x variabel stiger fra nul til en positiv værdi og dermed tvinger en ekstra y variabel til at være 1.

20
3. januar 2016 kl. 17:43

Objektfunktion:
Minimér \sum_{i, j \in P} y_{ij}

Hmm. Er betalingerne (x) ikke unbounded (<M)? Vi foretrækker vel den løsning af de mulige løsninger, som har det mindste afregningsbeløb.

Vil det kunne løses med flg. mål i stedet?

Minimér \sum_{i, j \in P} My_{ij} + x_{ij}

Eller overser jeg noget?

19
3. januar 2016 kl. 01:41

Hvorfor bruge et self signed cert når Let’s Encrypt findes…

Attackers might be trying to steal your information from buddyledger.baconsvin.org (for example, passwords, messages, or credit cards). NET::ERR_CERT_AUTHORITY_INVALID

18
2. januar 2016 kl. 20:22

Nedenstående - utestede - heltalsprogram (i Latex-syntaks) burde minimere antallet af betalinger mellem personer.

Mængder:

  • P er mængden af alle personer, indekseret med indeks i
  • R_i er mængden af delregnskaber for person i, indekseret med indeks r
  • P_r \subseteq P er mængden af personer som er med i delregnskab r

Parameter:

  • u_{ir} >= 0 er udlæg fra person i til delregnskab r

Beslutningsvariable:

  • reel x_{ij} >= 0 er betaling fra person i til person j
  • binær y_{ij} er lig 1 hvis og kun hvis x_{ij} > 0

Objektfunktion: Minimér \sum_{i, j \in P} y_{ij}

Begrænsninger:

  • for alle i,j \in P: y_{ij} >= x_{ij} / M
  • for alle i \in P: \sum_{r \in R_i} \sum_{j \in P_r} u_{jr} / |P_r| = \sum_{r \in R_i} u_{ir} + \sum_{j \in P} x_ij - \sum_{j \in P} x_{ji}

Selvom heltalsprogrammering (generelt) er NP-hårdt og store M begrænsninger ikke ligefrem gør tingene nemmere, så vil jeg gætte på at realistiske instanser kan løses på få sekunder af en god MIP solver.

17
2. januar 2016 kl. 18:33

Vil lige henlede til et alternativ i samme retning, dog beregnet til forhold over længere tid. I dette system er der ligeledes mulighed for en ujævn fordeling af betaling, såsom eksemplet i bloggen.

https://secure.splitwise.com/

16
2. januar 2016 kl. 18:14

Online demoen skal man lige være opmærksom på ikke egner sig til egentlig brug da de forskellige ledgers får et unikt ID (fortløbende fra 1 og frem) - man kan altså tilgå andres ledgers blot ved at ændre i URLen. Det er fint som et demo system, men man bør ikke bruge det til noget med rigtig data.

14
2. januar 2016 kl. 18:00

Så vidt jeg kan se i koden, sættes costen altid til 1 ...

Jeg kan heller ikke se, hvordan cost kan være andet end konstant. Der er ikke forskel på en betaling (af en given størrelse) uanset hvor den går fra eller til.

Men det betyder også, at algoritmen synes at flere del-betalinger "koster" det samme som en fuld betaling, og derfor har den ingen interesse i at minimere antallet af del-betalinger.

Maxflow sikrer mao. kun at alle betaler hvad de skal uden at nogen får for meget, men kan ikke kende forskel på en løsning, hvor alle debitorer betaler noget til alle kreditorer og en løsning med få betalingsstrømme, bare summerne stemmer - det samlede flow er det samme i de to, og ingen begrænsninger er overskredet.

Eksempel: A og B skal have 9 hver, og C, D og E skal betale 6 hver. En løsning vil være, at C betaler A og B 3 hver og D og E betaler 6 til hhv. A og B. Samlet flow er 18.

Men en løsning, hvor C, D og E alle betaler 3 til både A og B har også et samlet flow på 18. For maxflow vil de to løsninger være lige gode. Den ene med 4 betalinger og den anden med 6 (for fem aktører). Min anden løsning vil næppe blive førstevalg i praksis, men mon ikke der kan konstrueres tilpas snedige eksempler til at lokke almindelige implementationer af algoritmen i uføre?

Jeg frygter derfor at maxflow kan komme op med unødigt kompliceret løsninger. Måske ville en fornuftig heuristik være at foretrække?

12
2. januar 2016 kl. 12:31

Ja, hvis du kan finde passende subset. Viser det andet end, at med tilstrækkelig mange subsets, så vil problemet have en løsning? Men det løser vel ikke udfordringen med at finde det minimale sæt af betalinger?

Reduktionen går omvendt: Hvis vi kan finde det minimale antal betalinger, så kan vi løse subset sum. Ergo er det np-hårdt at finde det minimale antal betalinger.

Mere præcist vil vores subset-sum-algoritme svare "ja" netop når den antagede betalings-algoritme svarer n-2. (Og som du selv siger, hvis betalings-algoritmen er korrekt, vil den altid som minimum finde en n-1 betaling.)

Det er klart at vi kan opnå n-2 når svaret er ja: Det givne subset betaler til kreditor 1, de resterende betaler til kreditor 2. Hvis svaret er nej, må svaret stadig være mindst n-2, da der er n-2 debitorer. Hvis vi antager at det faktisk er n-2 (for at få en modsætning), må betalingerne udgøre to træer, med rod i de to kreditorer. Men så er der ingen mulighed for at en debitor kunne betale til mere en én kreditor, og så må debitorerne i første kreditors træ udgøre en undermængde med den søgte sum x.

Så ja, hvis man har n-1 betalinger, kan man altid kæde alting sammen, men hvis man vil bruge færre end det, kræver det at man opdeler i undermængder, der ikke kommunikerer/betaler med hinanden.

Jeg håber, at det giver mening :-)

11
2. januar 2016 kl. 11:52

I øvrigt kan problemet med at aftegne imellem n deltagere altid løses med n-1 betalinger:

Del deltagerne op i netto-debitorer og netto-kreditorer i vilkårlig orden. Hver debitorer betaler næste debitor, hvad han har modtaget fra foregående debitor plus hvad han selv skylder. Sidste debitor i rækken betaler første kreditor. Hver kreditor tager, hvad han har tilgode og betaler resten videre til næste kreditor. Når sidste kreditor modtager betaling er alt fuldt afregnet.

Det vil give stort cash-flow omkring det punkt, hvor man skifter fra debitorer til kreditorer, og det ignorerer at der kunne være subset, som internt ville kunne aftegne fuldt ud (og dermed reducere det samlede antal betalinger), så det kan egentlig kun bruges til at sætte et minimums niveau for heuristikker.

10
2. januar 2016 kl. 11:28

Og at bruge max flow:

Vil max flow finde det minimale sæt af betalinger? Der er vel ingen cost forbundet med at opsplitte betalingen i flere flows?

9
2. januar 2016 kl. 11:16

Du kan reducere til subset-sum.

Ja, hvis du kan finde passende subset. Viser det andet end, at med tilstrækkelig mange subsets, så vil problemet have en løsning? Men det løser vel ikke udfordringen med at finde det minimale sæt af betalinger?

8
2. januar 2016 kl. 03:46

Det lugter af at være en variant af et rygsæksproblem, men jeg kan ikke lige genkende det.

Du kan reducere til subset-sum.

Hvis du har en mængde S af positive tal, og vil teste om den har et subset med sum x, så kan du lave |S| personer med negativ "netto betaling", og to personer med positiv "netto". Personerne med positiv netto, som altså skal have penge af de andre, har henholdsvis betalt x og sum(S)-x for meget.

Hvis betalingerne kan klares med kun |S| overførsler, ved vi at alle kun har betalt til én person, og derfor var der et subset med summen x.

7
2. januar 2016 kl. 03:17

Er det ikke bare gaussisk eliminering?

Du kan finde en korrekt mængde af overførsler sådan. Det der gør problemet svært er, at vi er interesseret i den mindste sådan mængde - eller den hvor flest overførsler er 0.

For n personer kan man kan løse det i 3^n med dynamisk programmering over undermængder: http://www.spoj.com/problems/TRANSFER/Eller vel med interger linær programmering.

Buddy ledger lader til at give valget mellem en 'basic' udregning, som vist mere eller mindre bare starter fra en ende af: https://github.com/tykling/buddyledger/blob/master/src/buddyledger/views/basiccalc.pyOg at bruge max flow: https://github.com/tykling/buddyledger/blob/master/src/buddyledger/views/graphbuilder.py

I de fleste tilfælde virker det nok også lige så godt, men måske kunne det være sjovt at tilføje en eksakt, dynamisk-programmeringsversion også.

6
1. januar 2016 kl. 22:59

Er det ikke bare gaussisk eliminering?

Jeg havde selv en tanke om at det nok reducerede til et eller andet grafproblem, måske polynomielt måske ikke. Men Gauss-elimination er jo også lidt hen af det...

4
1. januar 2016 kl. 20:49

... men kan vi ikke reducere resultattrinnet yderligere?

Nemt. Men ikke meget. Hvis vi lige kigger på nettotallene:

Person Netto A 318 B -248 D -15 G -248 H 111 O 82

Derfor er flg. betalingsplan også en løsning:

Fra Til Beløb B A 248 D A 15 G A 55 G H 111 G O 82

Det lugter af at være en variant af et rygsæksproblem, men jeg kan ikke lige genkende det.

Det må være til at finde fornuftige heuristikker, idet løsningen ikke behøver være optimal, bare effektiv.

3
1. januar 2016 kl. 10:02

Det er snedigt, men kan vi ikke reducere resultattrinnet yderligere? Jeg hæfter mig eksempelvis ved at Bent skal betale til Ole, som skal betale videre til Du og HLK. Personer som Bent betaler til i forvejen..

2
31. december 2015 kl. 17:48

Hvis Thomas læser med her, vil du så ikke forklare hvilke to algoritmer du bruger til udligning?

1
31. december 2015 kl. 17:32

Men jeg må nu indrømme at jeg ikke bryder mig om den slags milimeter regnskab mellem venner ... der vil jeg hellere bare være den der giver, og så satse på at de andre også giver efter evne ... og hvis ikke lige det går op på den her fest / tur ... så gør det næste gang :-)