Gemeinsame Ausgaben-Rechnungsteiler und Ausgleichsplaner

--- name: shared-expense-bill-splitter-and-settle-up-planner description: Teilt ein CSV-Kassenbuch gemeinsamer Kosten für eine Reise, WG oder Veranstaltung - gleichmäßig, Anteile, exakt, Prozent und Einzelposten-Rechnungen mit Steuer/Trinkgeld anteilig, 'alle außer'-Ausschlüsse, mehrere Zahler, Rückerstattungen, Rückzahlungen und mehrere Währungen zu vereinbarten Kursen - in Cent, und findet dann die nachweislich wenigsten Ausgleichsüberweisungen (exakte Nullsummen-Untergruppensuche). Liefert Salden, eine Prüfung pro Person und eine Chat-Nachricht. Enthält einen Stdlib-Python-Planer mit --self-test. --- # Gemeinsamer Ausgaben-Rechner und Ausgleichs-Planer Du verwandelst eine unübersichtliche Liste gemeinsamer Ausgaben in eine faire, überprüfbare Aufteilung und die kürzestmögliche Liste von Zahlungen. Du führst das Kassenbuch als CSV, das die Gruppe in jeder Tabellenkalkulation bearbeiten kann, wendest die Aufteilungsregel an, die jede Zeile wirklich braucht (wer war dabei, wer hat was bestellt, wer hat weniger Nächte übernachtet), rechnest Währungen zu Kursen um, auf die sich die Gruppe geeinigt hat, und gleicht alle mit den wenigsten Überweisungen ab. Jeder Cent ist verbucht, und jeder kann seine eigene Zahl Zeile für Zeile nachvollziehen. ## Dateien in dieser Fähigkeit - `scripts/settle_up.py` - liest das CSV-Kassenbuch, teilt jede Zeile in ganzen Cent (Rundung nach dem größten Rest), berechnet gezahlt/Anteil/Saldo pro Person und durchsucht alle Nullsummen-Untergruppen, um die Mindestanzahl an Überweisungen zu finden (exakt bis zu 18 Personen mit einem Saldo, darüber hinaus gierig) (nur Python 3.8+ Standardbibliothek) - `references/split-methods.md` - das CSV-Format, welche Aufteilung für welche Kosten, Einzelposten-Rechnungen mit Steuer und Trinkgeld, Ausschlüsse, Zahler, Rückerstattungen und Rückzahlungen - `references/settle-up-and-currency.md` - warum das Minimum unter "Personen - 1" liegen kann, wie die Suche funktioniert, Rundung, Wechselkurse und Kartengebühren, Zahlungsetikette - `templates/settle-up-summary.md` - die Zusammenfassung zum Zurückgeben und Einfügen in den Gruppenchat - `examples/lisbon-trip.csv` - 5 Freunde, 11 Zeilen: Anteile nach Nächten, eine ausgeschlossene Person, ein Einzelposten-Abendessen, eine USD-Buchung, Premium-Sitze, zwei Zahler, eine Rückerstattung, GBP-Snacks und eine bereits getätigte Rückzahlung - `examples/lisbon-settle-output.md` - die tatsächliche Ausgabe des Planers für dieses Kassenbuch - `examples/flat-october.csv` - 6 Mitbewohner, bei denen das Minimum (4 Überweisungen) besser ist als die größte Schuld an die größte Forderung zu zahlen (5) ## Arbeitsablauf ### 1. Kassenbuch erfassen Frage nach jeder gemeinsamen Kosten mit: was, wer hat gezahlt (und wie viel jeweils, wenn mehrere gezahlt haben), der Betrag und die Währung, und für wen es war. Stelle die Fragen, die die Aufteilung ändern: Ist jemand spät angekommen oder früh gegangen? Hat jemand eine Mahlzeit oder Aktivität ausgelassen? Wurde ein Abendessen geteilt oder einzeln bestellt? Hat schon jemand jemandem Geld zurückgezahlt? Vereinbare die Basiswährung und die Kurse (ein Kurs pro Währung für die gesamte Reise, es sei denn, die Gruppe möchte Kontoauszugskurse). Schreibe es als CSV in `references/split-methods.md`, mit `# people:`, damit Tippfehler bei Namen erkannt werden. ### 2. Planer ausführen ``` python3 scripts/settle_up.py examples/lisbon-trip.csv python3 scripts/settle_up.py flat.csv --base GBP --rates EUR=0.86 --detail Ben python3 scripts/settle_up.py ledger.csv --json python3 scripts/settle_up.py --self-test ``` Exit 0 = Plan gedruckt (Warnungen lesen), 2 = das Kassenbuch hat einen Fehler (Summen, die nicht übereinstimmen, fehlender Kurs, unbekannte Aufteilung oder Name) - korrigiere die genannte Zeile. Wenn du keinen Code ausführen kannst, folge denselben Schritten von Hand: jede Zeile in Basis-Cent umrechnen, aufteilen, gezahlt minus Anteil pro Person summieren, dann Schuldner mit Gläubigern abgleichen, wobei du zuerst nach Personen oder kleinen Gruppen suchst, deren Salden sich exakt aufheben. ### 3. Ergebnis mit der Gruppe prüfen - Die Prüfzeile muss `nets add up to 0.00` lauten; gezahlt und Anteile müssen gleich sein. - Lies die Salden in einfachen Worten vor ("Ana hat 990.00 gezahlt, ihr Anteil ist 377.31 und Eli hat ihr bereits 100.00 gegeben, also bekommt sie 512.69 zurück"). - Weise auf Zeilen hin, die das Ergebnis bestimmen und leicht anzufechten sind (Anteile nach Nächten, Einzelposten-Mahlzeiten, eine Rückerstattung, eine Rückzahlung), und biete `--detail <Name>` für jeden an, der seine eigene Aufschlüsselung möchte. - Wenn jemand lieber jemand anderen bezahlt (oder eine Person nicht direkt bezahlen kann), führe es erneut aus, nachdem du die vereinbarte Überweisung als `payment`-Zeile hinzugefügt hast; der Plan berechnet den Rest neu. ### 4. Liefern Fülle `templates/settle-up-summary.md`: Summen, die Saldentabelle, die nummerierten Überweisungen, die Annahmen (Kurse, wer wo ausgeschlossen war, wie Steuer/Trinkgeld verteilt wurde) und die kurze Gruppenchat-Nachricht. Schlage vor, jede Überweisung als erledigt zu markieren, indem du sie als `payment`-Zeile zum Kassenbuch hinzufügst, sodass ein zweiter Lauf für alle 0.00 anzeigt. ## Beispielergebnis Bei `examples/lisbon-trip.csv` (5 Personen, 1.583,07 EUR ausgegeben) hat Ana die Wohnung und die Fado-Tickets bezahlt und bekommt 512,69 EUR zurück; der Plan ist 4 Überweisungen: Ben zahlt Ana 243,17, Dara zahlt Ana 140,94, Eli zahlt Ana 128,58 und Eli zahlt Cem 0,85 (Eli's frühere 100,00-Rückzahlung ist bereits berücksichtigt). Bei `examples/flat-october.csv` heben sich Bo und Finn gegenseitig auf, sodass 6 Mitbewohner mit 4 Überweisungen abrechnen, während die größte Schuld an die größte Forderung 5 bräuchte. ## Regeln - Erfinde niemals Beträge, Kurse oder wer teilgenommen hat; frage nach oder markiere die Zeile als Annahme in der Zusammenfassung. - Verwende einen vereinbarten Kurs pro Währung und zeige ihn; mische keine Live-Kurse in eine fertige Aufteilung. - Halte alle Berechnungen in Cent und zeige, wohin die Rundungs-Cents gingen (größter Rest, Gleichstand an die zuerst aufgeführte Person). - Bewerte Ausgaben nicht; kennzeichne nur Zeilen, die wie Duplikate, Tippfehler oder fehlende Teilnehmer aussehen. - Eine Rückzahlung ist eine `payment`-Zeile, niemals eine negative Ausgabe; eine Rückerstattung ist eine negative Ausgabe, die von denselben Personen wie die ursprünglichen Kosten geteilt wird. - Präsentiere den Plan als Vorschlag; die Gruppe kann tauschen, wer wem zahlt, solange der Saldo jeder Person unverändert bleibt. FILE:references/split-methods.md # Aufteilungsmethoden und CSV-Format ## Spalten `date,description,paid_by,amount,currency,split,participants,details` - Kopfzeile erforderlich; jede Tabellenkalkulation kann sie exportieren. Optionale Kommentarzeilen vor der Kopfzeile: ``` # people: Ana, Ben, Cem, Dara, Eli (strikte Liste: ein falsch geschriebener Name ist ein Fehler) # base: EUR # rates: USD=0.92, GBP=1.16 (1 USD = 0.92 EUR) ``` Ohne `# people:` ist jeder, der irgendwo in der Datei genannt wird, ein Mitglied und `all` bedeutet alle; Namen werden ohne Beachtung der Groß-/Kleinschreibung abgeglichen. ## Aufteilungsmethode wählen | Kosten | Aufteilung | Beispiel `participants` / `details` | |---|---|---| | Lebensmittel, Taxi, Benzin, gemeinsame Tickets | `equal` | `all`, `Ana;Ben`, `all-Eli` | | Unterkunft, wenn Leute unterschiedliche Nächte blieben, Zimmer unterschiedlicher Größe | `shares` | `Ana:3;Ben:3;Dara:2` (Nächte oder Zimmergewichte) | | Tickets mit unterschiedlichen Preisen, ein bekannter Betrag pro Person | `exact` | `Ana:30;Ben:45` (andere in participants teilen den Rest gleichmäßig) | | Vereinbarte Prozentsätze (Miete nach Einkommen, Wein für die, die getrunken haben) | `percent` | `Ana:25;Ben:25;Dara:50` (muss 100 ergeben) | | Restaurantrechnung, bei der Leute separat bestellt haben | `itemized` | `Ana:31;Ben:28.50;shared:42` | | Jemand hat jemandem bereits zurückgezahlt | `payment` | participants = der eine Empfänger | ## Einzelposten-Rechnungen - `details` listet die Artikel jeder Person vor Steuer, Service und Trinkgeld; `shared` ist die Summe der Vorspeisen, Flaschen oder allem, was alle geteilt haben (gleichmäßig unter `participants` aufgeteilt). - `amount` ist die endgültige Rechnung. Die Differenz (amount - Artikel) ist Steuer, Service und Trinkgeld, proportional zu dem verteilt, was jede Person hatte, sodass jemand, der mehr bestellt hat, mehr Trinkgeld zahlt. Die Ausgabe zeigt es als `+17.3% tax/tip`. - Wenn die Artikel mehr ergeben als die Rechnung (ein Rabatt oder ein Tippfehler), stoppt der Planer; gib den Rabatt ein, indem du die Artikelpreise senkst, auf die er angewendet wurde. ## Ausschlüsse und teilweise Teilnahme - `all-Eli` oder `all except Eli` = alle außer Eli; mehrere verketten: `all-Bo-Finn`. - Für Personen, die nur zeitweise anwesend waren, verwende `shares` mit Nächten oder Tagen, anstatt sie auszuschließen. - Ein Kind oder Gast, das von einem Mitglied bezahlt wird: liste es unter dem Namen des Mitglieds auf (`shares`-Gewicht 1.5) oder füge es zu `# people:` hinzu und gleiche mit den Eltern ab. ## Zahler - Ein Zahler: `Ana`. Mehrere Zahler auf einer Rechnung: `Ben:40;Cem:20` (Beträge in der Zeilenwährung, müssen `amount` ergeben). - Eine Karte, die ein Paar teilt: behandle das Paar als eine Person oder teile den Zahlerbetrag. ## Rückerstattungen, Anzahlungen, Rückzahlungen - Rückerstattung nach einer Stornierung: negativer `amount`, `paid_by` = wer das Geld erhalten hat, gleiche Teilnehmer wie die ursprünglichen Kosten. - Anzahlung vom Vermieter zurück: negativer `amount`, aufgeteilt wie die Anzahlung. - Geld, das zwischen Mitgliedern übergeben wurde: `payment` (von `paid_by` an die eine Person in `participants`). Nimm Ausgleichsüberweisungen genauso auf; ein erneuter Lauf zeigt dann, wer noch offen ist. ## Häufige Fehler, die der Planer erkennt - Exakte Beträge oder Prozentsätze, die nicht aufgehen, Zahlerbeträge, die von der Rechnung abweichen, Artikel über der Rechnung. - Eine Währung ohne Kurs, ein unbekanntes Aufteilungswort, ein falsch geschriebener Name, wenn `# people:` gesetzt ist. - Zwei identische Zeilen (gleiches Datum, Beschreibung, Betrag und Zahler) - als Warnung gemeldet, nicht entfernt. - Nullbeträge - mit Warnung übersprungen. FILE:references/settle-up-and-currency.md # Ausgleich und Währung ## Nettosaldo Für jede Person: `net = gezahlt + gesendete Zahlungen - Anteil - erhaltene Zahlungen`. Positiv = bekommt Geld zurück, negativ = schuldet. Die Salden ergeben immer exakt 0.00, weil jede Zeile in ganzen Cent aufgeteilt wird, die zur Zeilensumme summieren. ## Warum "wenigste Überweisungen" weniger als Personen - 1 sein kann - Jede Gruppe mit k Personen mit einem Saldo kann in höchstens k - 1 Überweisungen abrechnen (jede Überweisung klärt mindestens eine Person). - Wenn sich die Gruppe in Untergruppen aufteilt, deren Salden jeweils Null ergeben, gleicht jede Untergruppe für sich ab: mit g solcher Untergruppen ist das Minimum k - g. Beispiel: Bo +300 und Finn -300 heben sich auf, also brauchen 6 Mitbewohner 4 Überweisungen, nicht 5. - Die größte Schuld an die größte Forderung zu zahlen (der übliche App-Ansatz) sucht nicht nach diesen Untergruppen und kann mehr Überweisungen erfordern. - Die beste Aufteilung in Nullsummen-Untergruppen zu finden, ist im Allgemeinen ein schwieriges Problem; der Planer löst es exakt für bis zu 18 Personen mit einem Saldo ungleich Null (dynamische Programmierung über Teilmengen, unter einer Sekunde) und fällt darüber hinaus auf den gierigen Plan zurück und sagt dies. - Innerhalb jeder Untergruppe zahlt der Plan die größte Schuld an die größte Forderung, was genau (Untergruppengröße - 1) Überweisungen verwendet. - Mehrere Pläne können dieselbe Mindestanzahl haben; jeder davon ist fair, weil der Gesamtbetrag jeder Person rein oder raus durch ihren Saldo festgelegt ist. ## Rundung - Jede Zeile wird einmal in Basis-Cent umgerechnet (`amount x rate`, halb aufgerundet), dann mit der Methode des größten Rests aufgeteilt: jeder bekommt den abgerundeten Betrag, und die übrig gebliebenen Cent gehen an die größten Brüche, Gleichstand an die zuerst in `# people:` aufgeführte Person. - Über eine ganze Reise bewegt dies höchstens ein paar Cent pro Person; sag das, wenn jemand fragt, warum 10.00 / 3 für eine Person 3.34 ist. ## Wechselkurse - Vereinbare einen Kurs pro Währung vor der Aufteilung: den Kurs an dem Tag, an dem die meisten Kosten gezahlt wurden, den Durchschnitt der Reise oder den Kurs auf dem Kontoauszug des Zahlers (der den Bankaufschlag enthält). - Wenn die Karte des Zahlers eine Auslandstransaktionsgebühr berechnet hat, entweder in den Betrag einbeziehen (die Gruppe teilt sie) oder weglassen (der Zahler absorbiert sie) - entscheide einmal für die gesamte Reise. - Gib Beträge in der tatsächlich gezahlten Währung ein und lass den Planer umrechnen; rechne nicht einige Zeilen von Hand vorab um. - Gleiche in der Basiswährung ab. Wenn jemand in einer anderen Währung zahlt, rechne die Überweisung zum selben vereinbarten Kurs um und erfasse sie als `payment`-Zeile in dieser Währung. ## Zahlungsetikette - Sende die Gruppenchat-Nachricht mit den Überweisungen und einem Link zum Kassenbuch; gib den Leuten ein oder zwei Tage, um eine Zeile anzufechten, bevor sie zahlen. - Kleine Überweisungen (unter ~2 EUR/USD) können erlassen oder in die nächsten gemeinsamen Kosten einbezogen werden, wenn beide zustimmen - erfasse das als `payment`-Zeile, damit das Kassenbuch exakt bleibt. - Wenn alle gezahlt haben, füge jede Überweisung als `payment`-Zeile hinzu und führe erneut aus: jeder Saldo sollte 0.00 sein. FILE:templates/settle-up-summary.md # Ausgleich: <Reise / WG / Veranstaltung>, <Daten> **Gruppe:** <Ana, Ben, Cem, Dara, Eli> **Basiswährung:** <EUR> **Gesamtausgaben:** <1.583,07 EUR> über <11> Zeilen **Vereinbarte Kurse:** <1 USD = 0.92 EUR, 1 GBP = 1.16 EUR (Reisedurchschnitt)> ## Salden | Person | Gezahlt | Fairer Anteil | Bereits gesendet / erhalten | Saldo | |---|---|---|---|---| | <Ana> | <990.00> | <377.31> | <100.00 erhalten> | <+512.69 bekommt zurück> | | <Ben> | <64.00> | <307.17> | <-> | <-243.17 schuldet> | ## Überweisungen (<n>, das Minimum möglich) 1. <Ben zahlt Ana 243.17 EUR> 2. <Dara zahlt Ana 140.94 EUR> 3. <...> ## Wie Zeilen aufgeteilt wurden - <Wohnung: nach Nächten, Dara und Eli 2 von 3 Nächten> - <Flughafentaxi: alle außer Eli (kam mit dem Zug)> - <Abendessen: Einzelposten, 17.3% Steuer und Trinkgeld nach dem verteilt, was jede Person bestellte; Vorspeisen 42.00 geteilt> - <Palasttickets-Rückerstattung: zurück an Ben und Cem, die sie bezahlt haben> - <Eli's 100.00 an Ana ist bereits berücksichtigt> ## Annahmen und offene Punkte - <Kurse oben; Kartengebühren nicht enthalten> - <Zeile 5 prüfen (Surfkurs): war Ben dabei?> ## Gruppenchat-Nachricht ``` Ausgleich (<EUR>, <11> Zeilen, Kurse: <USD 0.92, GBP 1.16>): - <Ben -> Ana: 243.17 EUR> - <Dara -> Ana: 140.94 EUR> Vollständige Tabelle: <Link zum Blatt>. Meldet euch innerhalb von 2 Tagen, wenn eine Zeile falsch ist. ``` **Wenn bezahlt:** füge jede Überweisung als `payment`-Zeile hinzu und führe erneut aus - jeder Saldo sollte 0.00 lauten. FILE:examples/lisbon-trip.csv # people: Ana, Ben, Cem, Dara, Eli # base: EUR # rates: USD=0.92, GBP=1.16 date,description,paid_by,amount,currency,split,participants,details 2026-10-02,Apartment 3 nights (Dara and Eli 2 nights),Ana,840.00,EUR,shares,all,Ana:3;Ben:3;Cem:3;Dara:2;Eli:2 2026-10-02,Airport taxi (Eli came by train),Ben,48.00,EUR,equal,all-Eli, 2026-10-02,Groceries for the flat,Eli,63.75,EUR,equal,all, 2026-10-03,Dinner at Taberna do Mar,Cem,212.40,EUR,itemized,all,Ana:31;Ben:28.50;Cem:24;Dara:36;Eli:19.50;shared:42 2026-10-03,Surf lesson (booked on a US site),Dara,180.00,USD,equal,Ana;Dara;Eli, 2026-10-03,Fado tickets (premium seats for Dara and Eli),Ana,150.00,EUR,exact,all-Cem,Ana:30;Ben:30;Dara:45;Eli:45 2026-10-04,Train to Sintra,Ben:40;Cem:20,60.00,EUR,equal,all, 2026-10-04,Wine for the flat,Dara,36.00,EUR,percent,,Ana:25;Ben:25;Dara:50 2026-10-04,Palace tickets refunded (rain),Ben,-24.00,EUR,equal,Ben;Cem, 2026-10-05,Snacks at the London layover,Cem,27.00,GBP,equal,all, 2026-10-05,Eli paid Ana back for the apartment,Eli,100.00,EUR,payment,Ana, FILE:examples/lisbon-settle-output.md # Ausgleichsplan Basiswährung: EUR Personen: 5 Zeilen: 11 Gesamtausgaben: 1.583,07 EUR Verwendete Kurse: 1 GBP = 1.16 EUR, 1 USD = 0.92 EUR ## Ausgaben | # | Datum | Was | Gezahlt von | Betrag | In EUR | Aufteilung | Unter | |---|---|---|---|---|---|---|---| | 1 | 2026-10-02 | Apartment 3 nights (Dara and Eli 2 nights) | Ana | 840.00 EUR | 840.00 | shares | all | | 2 | 2026-10-02 | Airport taxi (Eli came by train) | Ben | 48.00 EUR | 48.00 | equal | Ana, Ben, Cem, Dara | | 3 | 2026-10-02 | Groceries for the flat | Eli | 63.75 EUR | 63.75 | equal | all | | 4 | 2026-10-03 | Dinner at Taberna do Mar | Cem | 212.40 EUR | 212.40 | itemized (+17.3% tax/tip) | all | | 5 | 2026-10-03 | Surf lesson (booked on a US site) | Dara | 180.00 USD | 165.60 | equal | Ana, Dara, Eli | | 6 | 2026-10-03 | Fado tickets (premium seats for Dara and Eli) | Ana | 150.00 EUR | 150.00 | exact | Ana, Ben, Dara, Eli | | 7 | 2026-10-04 | Train to Sintra | Ben 40.00, Cem 20.00 | 60.00 EUR | 60.00 | equal | all | | 8 | 2026-10-04 | Wine for the flat | Dara | 36.00 EUR | 36.00 | percent | Ana, Ben, Dara | | 9 | 2026-10-04 | Palace tickets refunded (rain) | Ben | -24.00 EUR | -24.00 | equal | Ben, Cem | | 10 | 2026-10-05 | Snacks at the London layover | Cem | 27.00 GBP | 31.32 | equal | all | | 11 | 2026-10-05 | Eli paid Ana back for the apartment | Eli | 100.00 EUR | 100.00 | payment | to Ana | ## Salden | Person | Gezahlt | Anteil | Gesendet | Erhalten | Saldo | |---|---|---|---|---|---| | Ana | 990.00 | 377.31 | 0.00 | 100.00 | 512.69 (bekommt zurück) | | Ben | 64.00 | 307.17 | 0.00 | 0.00 | -243.17 (schuldet) | | Cem | 263.72 | 262.87 | 0.00 | 0.00 | 0.85 (bekommt zurück) | | Dara | 201.60 | 342.54 | 0.00 | 0.00 | -140.94 (schuldet) | | Eli | 63.75 | 293.18 | 100.00 | 0.00 | -129.43 (schuldet) | Prüfung: Salden ergeben 0.00 (gezahlt 1.583,07 = Anteile 1.583,07). ## Überweisungen (4) 1. Ben zahlt Ana **243.17 EUR** 2. Dara zahlt Ana **140.94 EUR** 3. Eli zahlt Ana **128.58 EUR** 4. Eli zahlt Cem **0.85 EUR** Minimum möglich: 4 Überweisungen für 5 Personen mit einem Saldo (keine kleinere Untergruppe gleicht sich von selbst aus). ## Nachricht für den Gruppenchat ``` Ausgleich (EUR, 11 Zeilen, Kurse: GBP 1.16, USD 0.92): - Ben -> Ana: 243.17 EUR - Dara -> Ana: 140.94 EUR - Eli -> Ana: 128.58 EUR - Eli -> Cem: 0.85 EUR Vollständige Tabelle im gemeinsamen Blatt. Meldet euch innerhalb von 2 Tagen, wenn eine Zeile falsch ist. ``` FILE:examples/flat-october.csv # people: Asha, Bo, Chen, Dev, Ema, Finn # base: EUR date,description,paid_by,amount,currency,split,participants,details 2026-10-01,Festival tickets for Bo and Finn,Bo,600,EUR,exact,Bo;Finn,Bo:300;Finn:300 2026-10-31,October groceries (Bo and Finn on tour),Asha,800,EUR,equal,all-Bo-Finn, 2026-10-31,Electricity Sep-Oct (Bo and Finn on tour),Chen,600,EUR,equal,all-Bo-Finn, 2026-10-20,Second-hand sofa (Dev and Ema's part),Asha,250,EUR,exact,Dev;Ema,Dev:150;Ema:100 FILE:scripts/settle_up.py #!/usr/bin/env python3 """Gemeinsamer Ausgaben-Rechner und Ausgleichs-Planer (nur Python 3.8+ Standardbibliothek). Liest ein CSV-Kassenbuch gemeinsamer Kosten (eine Reise, eine WG, eine Veranstaltung), teilt jede Zeile in ganzen Cent und findet die KLEINSTMÖGLICHE Anzahl an Überweisungen, die die Gruppe ausgleicht (exakte Suche über Nullsummen-Untergruppen, nicht nur "höchstens Personen - 1"). CSV-Spalten (Kopfzeile erforderlich, zusätzliche Spalten werden ignoriert): date,description,paid_by,amount,currency,split,participants,details paid_by Ana ein Zahler Ana:40;Ben:20 mehrere Zahler (Beträge in der Zeilenwährung, müssen aufgehen) amount Summe in der Zeilenwährung; negativ = Rückerstattung von paid_by erhalten currency leer = Basiswährung split equal | shares | exact | percent | itemized | payment participants all | Ana;Ben;Cem | all-Eli (alle außer Eli) | leer = Namen in details details shares: Ana:3;Ben:2 (Personen in participants, die nicht aufgelistet sind, bekommen 1) exact: Ana:30;Ben:45 (Rest, falls vorhanden, gleichmäßig unter den anderen Teilnehmern aufgeteilt) percent: Ana:50;Ben:30;Cem:20 (muss 100 ergeben) itemized: Ana:18;Ben:22.50;shared:12 (Artikelpreise vor Steuer/Trinkgeld; "shared" Artikel werden gleichmäßig aufgeteilt; amount - Artikel = Steuer/Service/Trinkgeld, aufgeteilt im Verhältnis zu dem, was jede Person bestellt hat) payment: (keine) paid_by gab `amount` an die eine Person in participants Kommentarzeilen oben setzen die Gruppe und die Kurse (oder verwende die CLI-Flags): # people: Ana, Ben, Cem # base: EUR # rates: USD=0.92, GBP=1.16 (1 Einheit dieser Währung = Kurs Einheiten der Basis) Verwendung: python3 settle_up.py ledger.csv [--base EUR] [--rates USD=0.92,GBP=1.16] [--people Ana,Ben] [--detail Ana] [--json] python3 settle_up.py --self-test Exit-Codes: 0 = ausgeglichener Plan gedruckt, 2 = ungültige Eingabe (unbekannte Aufteilung, Summen, die nicht übereinstimmen, fehlender Wechselkurs, unbekannte Person in einer strikten Liste). """ import argparse import csv import io import json import re import sys from decimal import Decimal, ROUND_HALF_UP, InvalidOperation MAX_EXACT = 18 # Personen mit einem Saldo ungleich Null für die exakte Minimumsuche (2^18 Zustände) SPLITS = ("equal", "shares", "exact", "percent", "itemized", "payment") class LedgerError(ValueError): pass def dec(s, what): try: return Decimal(str(s).replace(",", "").strip()) except (InvalidOperation, AttributeError): raise LedgerError("%s: %r ist keine Zahl" % (what, s)) def to_cents(amount): return int((amount * 100).quantize(Decimal("1"), rounding=ROUND_HALF_UP)) def fmt(cents, cur=""): sign = "-" if cents < 0 else "" c = abs(cents) s = "%s%d.%02d" % (sign, c // 100, c % 100) s = re.sub(r"(\d)(?=(\d{3})+\.)", r"\1,", s) return (s + " " + cur).strip() def allocate(total, weights, order): """Teilt ganzzahlige `total` Cent proportional zu `weights` (dict Name -> Decimal >= 0). Methode des größten Rests; Gleichstand geht an den früheren Namen in `order`. Summe ist exakt.""" names = [n for n in order if n in weights] wsum = sum(weights[n] for n in names) if wsum <= 0: raise LedgerError("Gewichte ergeben Null") sign = -1 if total < 0 else 1 t = abs(total) raw = {n: Decimal(t) * weights[n] / wsum for n in names} base = {n: int(raw[n]) for n in names} left = t - sum(base.values()) rank = sorted(names, key=lambda n: (-(raw[n] - base[n]), order.index(n))) for n in rank[:left]: base[n] += 1 return {n: sign * v for n, v in base.items() if v} def parse_pairs(text, what): out = {} for part in [p for p in re.split(r"[;|]", text or "") if p.strip()]: if ":" not in part: raise LedgerError("%s: %r sollte wie Name:Wert aussehen" % (what, part.strip())) k, v = part.split(":", 1) k = k.strip() out[k] = out.get(k, Decimal(0)) + dec(v, what) return out class Ledger: def __init__(self, text, base=None, rates=None, people=None): self.warnings = [] self.base = base self.rates = {} self.people = [] self._canon = {} header_people = None body = [] for line in text.splitlines(): s = line.strip() if s.startswith("#"): m = re.match(r"#\s*(people|base|rates?)\s*:\s*(.*)$", s, re.I) if m: key, val = m.group(1).lower(), m.group(2) if key == "people": header_people = [p.strip() for p in re.split(r"[,;]", val) if p.strip()] elif key == "base" and not self.base: self.base = val.strip().upper() elif key.startswith("rate"): self._add_rates(val) continue body.append(line) self.base = (self.base or "EUR").upper() if rates: self._add_rates(rates) self.rates[self.base] = Decimal(1) for p in (people or header_people or []): self._person(p, declare=True) self.strict = bool(people or header_people) rows = list(csv.DictReader(io.StringIO("\n".join(body)))) if not rows: raise LedgerError("keine Ausgabenzeilen gefunden (Kopfzeile und mindestens eine Zeile erforderlich)") need = {"description", "paid_by", "amount", "split"} cols = {c.strip().lower() for c in rows[0].keys() if c} if not need <= cols: raise LedgerError("fehlende CSV-Spalten: %s" % ", ".join(sorted(need - cols))) self.rows = [] for r in rows: r = {(k or "").strip().lower(): (v or "").strip() for k, v in r.items()} if not any(r.values()): continue self.rows.append(r) # erster Durchgang: jeden Namen lernen, wenn keine Personenliste angegeben wurde if not self.strict: for r in self.rows: for p in self._names_in(r): self._person(p, declare=True) self.lines = [self._line(n, r) for n, r in enumerate(self.rows, 1)] self._check_duplicates() # -- Personen und Kurse def _add_rates(self, text): for part in re.split(r"[,;]", text): if not part.strip(): continue if "=" not in part: raise LedgerError("Kurs %r sollte wie USD=0.92 aussehen" % part.strip()) k, v = part.split("=", 1) r = dec(v, "Kurs " + k.strip()) if r <= 0: raise LedgerError("Kurs für %s muss positiv sein" % k.strip()) self.rates[k.strip().upper()] = r def _person(self, name, declare=False): key = name.strip().lower() if not key: raise LedgerError("leerer Personenname") if key in self._canon: canon = self._canon[key] if canon != name.strip() and declare: self.warnings.append("'%s' und '%s' werden als dieselbe Person behandelt" % (canon, name.strip())) return canon if not declare: raise LedgerError("unbekannte Person %r (nicht in der Personenliste)" % name.strip()) self._canon[key] = name.strip() self.people.append(name.strip()) return name.strip() def _names_in(self, r): names = [] pb = r.get("paid_by", "") names += list(parse_pairs(pb, "paid_by").keys()) if ":" in pb else [pb] part = r.get("participants", "") if part and not part.lower().startswith("all"): names += [p for p in re.split(r"[;|]", part) if p.strip()] if r.get("split", "").lower() != "payment": names += [k for k in parse_pairs(r.get("details", ""), "details") if k.lower() != "shared"] return [n for n in names if n.strip()] def _participants(self, r, ln): part = r.get("participants", "").strip() if not part: return None if part.lower().startswith("all"): rest = part[3:].strip() excl = [] if rest: rest = re.sub(r"^(except|but|without)\s+", "", rest.lstrip("-").strip(), flags=re.I) excl = [self._person(x) for x in re.split(r"[-;|,]", rest) if x.strip()] return [p for p in self.people if p not in excl] return [self._person(p) for p in re.split(r"[;|]", part) if p.strip()] # -- eine CSV-Zeile -> gezahlt / Anteil in Basis-Cent def _line(self, ln, r): desc = r.get("description") or "Zeile %d" % ln where = "Zeile %d (%s)" % (ln, desc) split = (r.get("split") or "equal").lower() if split not in SPLITS: raise LedgerError("%s: unbekannte Aufteilung %r (verwende %s)" % (where, split, ", ".join(SPLITS))) cur = (r.get("currency") or self.base).upper() if cur not in self.rates: raise LedgerError("%s: kein Wechselkurs für %s (füge '# rates: %s=...' oder --rates hinzu)" % (where, cur, cur)) amount = dec(r.get("amount"), where + " Betrag") if amount == 0: self.warnings.append("%s hat Betrag 0 und wurde übersprungen" % where) total = to_cents(amount * self.rates[cur]) # Zahler pb = r.get("paid_by", "") if ":" in pb: pays = {self._person(k): v for k, v in parse_pairs(pb, where + " paid_by").items()} if sum(pays.values()) != amount: raise LedgerError("%s: Zahler ergeben %s, aber der Betrag ist %s" % (where, sum(pays.values()), amount)) paid = allocate(total, {k: abs(v) for k, v in pays.items()}, self.people) if total else {} if total < 0: paid = {k: -abs(v) for k, v in paid.items()} else: paid = {self._person(pb): total} if total else {} people = self._participants(r, ln) details = parse_pairs(r.get("details", ""), where + " details") if split != "payment" else {} share = {} if split == "payment": if not people or len(people) != 1: raise LedgerError("%s: eine Zahlung braucht genau einen Empfänger in participants" % where) share = {people[0]: total} elif split == "equal": people = people or self.people share = allocate(total, {p: Decimal(1) for p in people}, self.people) elif split == "shares": d = {self._person(k): v for k, v in details.items()} people = people or list(d) w = {p: d.get(p, Decimal(1)) for p in people} extra = [p for p in d if p not in people] if extra: raise LedgerError("%s: %s in details, aber nicht in participants" % (where, ", ".join(extra))) if any(v < 0 for v in w.values()): raise LedgerError("%s: Anteile können nicht negativ sein" % where) share = allocate(total, w, self.people) elif split == "percent": d = {self._person(k): v for k, v in details.items()} if sum(d.values()) != 100: raise LedgerError("%s: Prozentsätze ergeben %s, nicht 100" % (where, sum(d.values()))) people = list(d) share = allocate(total, d, self.people) elif split == "exact": d = {self._person(k): v for k, v in details.items()} people = people or list(d) fixed = sum(d.values()) rest_people = [p for p in people if p not in d] if fixed > abs(amount) or (fixed != abs(amount) and not rest_people): raise LedgerError("%s: exakte Beträge ergeben %s, aber die Rechnung ist %s" % (where, fixed, amount)) w = dict(d) if rest_people: each = (abs(amount) - fixed) / len(rest_people) for p in rest_people: w[p] = each share = allocate(total, w, self.people) elif split == "itemized": people = people or self.people shared = details.pop("shared", details.pop("Shared", Decimal(0))) d = {self._person(k): v for k, v in details.items()} items = sum(d.values()) + shared if items > abs(amount): raise LedgerError("%s: Artikel ergeben %s, mehr als die Rechnung %s" % (where, items, amount)) per = {p: d.get(p, Decimal(0)) + (shared / len(people) if shared else 0) for p in people} for p in d: if p not in per: per[p] = d[p] if sum(per.values()) <= 0: raise LedgerError("%s: keine Artikel zum Aufteilen" % where) # Steuer/Trinkgeld proportional zu den Artikeln jeder Person == Gesamtbetrag nach Artikelgewichten aufteilen share = allocate(total, per, self.people) rec = {"n": ln, "date": r.get("date", ""), "desc": desc, "split": split, "currency": cur, "amount": amount, "total": total, "paid": paid, "share": share, "among": sorted(share, key=self.people.index)} if split == "itemized": rec["extra_pct"] = (abs(amount) - items) / items * 100 if items else Decimal(0) if sum(paid.values()) != sum(share.values()): raise LedgerError("%s: interner Rundungsfehler" % where) # nie erwartet return rec def _check_duplicates(self): seen = {} for l in self.lines: key = (l["date"], l["desc"].lower(), l["total"], tuple(sorted(l["paid"]))) if key in seen: self.warnings.append("Zeile %d sieht aus wie ein Duplikat von Zeile %d (%s, %s)" % (l["n"], seen[key], l["desc"], fmt(l["total"], self.base))) else: seen[key] = l["n"] def balances(self): b = {p: {"paid": 0, "share": 0, "sent": 0, "received": 0} for p in self.people} for l in self.lines: if l["split"] == "payment": for p, c in l["paid"].items(): b[p]["sent"] += c for p, c in l["share"].items(): b[p]["received"] += c else: for p, c in l["paid"].items(): b[p]["paid"] += c for p, c in l["share"].items(): b[p]["share"] += c for p in b: b[p]["net"] = b[p]["paid"] + b[p]["sent"] - b[p]["share"] - b[p]["received"] return b # ----------------------------------------------------------------------------- Ausgleich def greedy(net, order): """Größter Schuldner zahlt größtem Gläubiger, bis alle ausgeglichen sind (höchstens k-1 Überweisungen).""" cred = {p: v for p, v in net.items() if v > 0} debt = {p: -v for p, v in net.items() if v < 0} out = [] while cred and debt: c = max(cred, key=lambda p: (cred[p], -order.index(p))) d = max(debt, key=lambda p: (debt[p], -order.index(p))) x = min(cred[c], debt[d]) out.append((d, c, x)) cred[c] -= x debt[d] -= x if not cred[c]: del cred[c] if not debt[d]: del debt[d] return out def minimal(net, order): """Wenigste Überweisungen: n - (maximale Anzahl disjunkter Nullsummen-Gruppen). Gibt (Überweisungen, Gruppen, exakt) zurück.""" people = [p for p in order if net.get(p)] n = len(people) if n == 0: return [], [], True if n > MAX_EXACT: return greedy(net, order), [people], False vals = [net[p] for p in people] size = 1 << n sums = [0] * size for m in range(1, size): low = m & -m sums[m] = sums[m ^ low] + vals[low.bit_length() - 1] dp = [0] * size for m in range(1, size): best = 0 mm = m while mm: low = mm & -mm v = dp[m ^ low] if v > best: best = v mm ^= low dp[m] = best + (1 if sums[m] == 0 else 0) # absteigen, bei jedem Nullsummen-Checkpoint eine Gruppe abschneiden groups, m, last = [], size - 1, size - 1 while m: mm, pick = m, None target = dp[m] - (1 if sums[m] == 0 else 0) while mm: low = mm & -mm if dp[m ^ low] == target: pick = low break mm ^= low m ^= pick if sums[m] == 0: groups.append(last ^ m) last = m out, named = [], [] for g in reversed(groups): members = [people[i] for i in range(n) if g >> i & 1] named.append(members) out += greedy({p: net[p] for p in members}, order) return out, named, True # ----------------------------------------------------------------------------- Ausgabe def render(led, detail=None): b = led.balances() net = {p: b[p]["net"] for p in led.people} tr, groups, exact = minimal(net, led.people) gr = greedy(net, led.people) B = led.base o = ["# Ausgleichsplan", "", "Basiswährung: %s Personen: %d Zeilen: %d Gesamtausgaben: %s" % ( B, len(led.people), len(led.lines), fmt(sum(l["total"] for l in led.lines if l["split"] != "payment"), B))] others = sorted(c for c in led.rates if c != B) if others: o.append("Verwendete Kurse: " + ", ".join("1 %s = %s %s" % (c, led.rates[c].normalize(), B) for c in others)) o += ["", "## Ausgaben", "", "| # | Datum | Was | Gezahlt von | Betrag | In %s | Aufteilung | Unter |" % B, "|---|---|---|---|---|---|---|---|"] for l in led.lines: payer = ", ".join("%s %s" % (p, fmt(c)) if len(l["paid"]) > 1 else p for p, c in l["paid"].items()) among = "all" if len(l["among"]) == len(led.people) and l["split"] != "payment" else ", ".join(l["among"]) split = l["split"] + (" (+%.1f%% Steuer/Trinkgeld)" % l["extra_pct"] if l["split"] == "itemized" else "") if l["split"] == "payment": among = "an " + among o.append("| %d | %s | %s | %s | %s %s | %s | %s | %s |" % (l["n"], l["date"], l["desc"].replace("|", "/"), payer, fmt(to_cents(l["amount"])), l["currency"], fmt(l["total"]), split, among)) o += ["", "## Salden", "", "| Person | Gezahlt | Anteil | Gesendet | Erhalten | Saldo |", "|---|---|---|---|---|---|"] for p in led.people: x = b[p] state = "bekommt zurück" if x["net"] > 0 else ("schuldet" if x["net"] < 0 else "ausgeglichen") o.append("| %s | %s | %s | %s | %s | %s (%s) |" % (p, fmt(x["paid"]), fmt(x["share"]), fmt(x["sent"]), fmt(x["received"]), fmt(x["net"]), state)) o.append("") o.append("Prüfung: Salden ergeben %s (gezahlt %s = Anteile %s)." % (fmt(sum(net.values())), fmt(sum(x["paid"] for x in b.values())), fmt(sum(x["share"] for x in b.values())))) nz = sum(1 for v in net.values() if v) o += ["", "## Überweisungen (%d)" % len(tr), ""] if not tr: o.append("Alle sind ausgeglichen. Nichts zu zahlen.") else: for i, (d, c, x) in enumerate(tr, 1): o.append("%d. %s zahlt %s **%s**" % (i, d, c, fmt(x, B))) o.append("") if exact: if len(groups) > 1: o.append("Minimum möglich: %d Überweisungen. Die Gruppe teilt sich in %d Mengen, die untereinander abrechnen (%s), also brauchen %d Personen nur %d Überweisungen; die größte Schuld an die größte Forderung zu zahlen würde %d brauchen." % ( len(tr), len(groups), "; ".join(" + ".join(g) for g in groups), nz, len(tr), len(gr))) else: o.append("Minimum möglich: %d Überweisungen für %d Personen mit einem Saldo (keine kleinere Untergruppe gleicht sich von selbst aus)." % (len(tr), nz)) else: o.append("%d Personen haben einen Saldo; exakte Minimumsuche übersprungen (Limit %d), gieriger Plan verwendet höchstens %d Überweisungen." % (nz, MAX_EXACT, nz - 1)) if detail: p = led._person(detail) o += ["", "## Detail: %s" % p, "", "| # | Was | Gezahlt | Anteil | Laufender Saldo |", "|---|---|---|---|---|"] run = 0 for l in led.lines: pd, sh = l["paid"].get(p, 0), l["share"].get(p, 0) if not pd and not sh: continue run += pd - sh o.append("| %d | %s | %s | %s | %s |" % (l["n"], l["desc"], fmt(pd), fmt(sh), fmt(run))) if led.warnings: o += ["", "## Warnungen", ""] + ["- " + w for w in led.warnings] o += ["", "## Nachricht für den Gruppenchat", "", "```"] msg = ["Ausgleich (%s, %d Zeilen, Kurse: %s):" % (B, len(led.lines), ", ".join("%s %s" % (c, led.rates[c].normalize()) for c in others) or "keine")] msg += ["- %s -> %s: %s" % (d, c, fmt(x, B)) for d, c, x in tr] or ["- alle sind ausgeglichen"] msg.append("Vollständige Tabelle im gemeinsamen Blatt. Meldet euch innerhalb von 2 Tagen, wenn eine Zeile falsch ist.") o += msg + ["```"] return "\n".join(o) + "\n" def as_json(led): b = led.balances() net = {p: b[p]["net"] for p in led.people} tr, groups, exact = minimal(net, led.people) return {"base": led.base, "people": led.people, "balances_cents": b, "transfers": [{"from": d, "to": c, "cents": x} for d, c, x in tr], "groups": groups, "exact_minimum": exact, "warnings": led.warnings} # ----------------------------------------------------------------------------- Selbsttest def self_test(): import random cases = [] def case(name, fn): try: ok, err = bool(fn()), "" except Exception as e: # noqa ok, err = False, repr(e) cases.append((name, ok, err)) H = "date,description,paid_by,amount,currency,split,participants,details\n" def L(rows, **kw): return Ledger(H + rows, **kw) def nets(led): b = led.balances() return {p: b[p]["net"] for p in led.people} def raises(fn): try: fn() except LedgerError: return True return False case("gleichmäßige Aufteilung auf den Cent", lambda: nets(L(",Taxi,Ana,10.00,,equal,Ana;Ben;Cem,\n")) == {"Ana": 666, "Ben": -333, "Cem": -333}) case("Rest-Cent geht an die zuerst aufgeführte Person", lambda: L(",X,Ana,0.10,,equal,Ana;Ben;Cem,\n").lines[0]["share"] == {"Ana": 4, "Ben": 3, "Cem": 3}) case("alle minus Ausschluss", lambda: Ledger("# people: Ana, Ben, Cem\n" + H + ",X,Ana,30,,equal,all-Cem,\n").lines[0]["among"] == ["Ana", "Ben"]) case("alle außer Wörter", lambda: Ledger("# people: Ana, Ben, Cem\n" + H + ",X,Ana,30,,equal,all except Ben,\n").lines[0]["among"] == ["Ana", "Cem"]) case("Anteilsgewichte", lambda: L(",Room,Ana,100,,shares,,Ana:3;Ben:1\n").lines[0]["share"] == {"Ana": 7500, "Ben": 2500}) case("Anteile Standard 1 für nicht aufgeführte Teilnehmer", lambda: L(",Room,Ana,90,,shares,Ana;Ben;Cem,Ana:2;Ben:0\n").lines[0]["share"] == {"Ana": 6000, "Cem": 3000}) case("exakte Beträge", lambda: L(",Tickets,Ana,75,,exact,,Ana:30;Ben:45\n").lines[0]["share"] == {"Ana": 3000, "Ben": 4500}) case("exakt mit Rest gleichmäßig aufgeteilt", lambda: L(",T,Ana,100,,exact,Ana;Ben;Cem,Ana:40\n").lines[0]["share"] == {"Ana": 4000, "Ben": 3000, "Cem": 3000}) case("exakte Nichtübereinstimmung abgelehnt", lambda: raises(lambda: L(",T,Ana,80,,exact,,Ana:30;Ben:45\n"))) case("Prozent", lambda: L(",Wine,Ana,36,,percent,,Ana:25;Ben:25;Cem:50\n").lines[0]["share"] == {"Ana": 900, "Ben": 900, "Cem": 1800}) case("Prozent nicht 100 abgelehnt", lambda: raises(lambda: L(",W,Ana,36,,percent,,Ana:25;Ben:25\n"))) case("Einzelposten mit geteilt und Steuer/Trinkgeld", lambda: L(",Dinner,Ana,66,,itemized,Ana;Ben,Ana:20;Ben:30;shared:10\n").lines[0]["share"] == {"Ana": 2750, "Ben": 3850}) case("Einzelposten über Rechnung abgelehnt", lambda: raises(lambda: L(",D,Ana,40,,itemized,Ana;Ben,Ana:20;Ben:30\n"))) case("Zahlungszeile", lambda: nets(L(",Food,Ana,20,,equal,Ana;Ben,\n,Paid back,Ben,10,,payment,Ana,\n")) == {"Ana": 0, "Ben": 0}) case("Zahlung braucht einen Empfänger", lambda: raises(lambda: L(",P,Ben,10,,payment,Ana;Cem,\n"))) case("mehrere Zahler", lambda: L(",Train,Ana:40;Ben:20,60,,equal,Ana;Ben;Cem,\n").lines[0]["paid"] == {"Ana": 4000, "Ben": 2000}) case("mehrere Zahler müssen aufgehen", lambda: raises(lambda: L(",Train,Ana:40;Ben:10,60,,equal,Ana;Ben,\n"))) case("Rückerstattung (negativer Betrag)", lambda: nets(L(",Museum refund,Ben,-24,,equal,Ben;Cem,\n")) == {"Ben": -1200, "Cem": 1200}) case("Währungsumrechnung", lambda: L(",Surf,Ana,100,USD,equal,Ana;Ben,\n", rates="USD=0.92").lines[0]["total"] == 9200) case("Kurse aus Kommentarzeile", lambda: Ledger("# base: EUR\n# rates: USD=0.92, GBP=1.16\n" + H + ",S,Ana,10,GBP,equal,Ana;Ben,\n").lines[0]["total"] == 1160) case("fehlender Kurs abgelehnt", lambda: raises(lambda: L(",S,Ana,10,CHF,equal,Ana;Ben,\n"))) case("unbekannte Aufteilung abgelehnt", lambda: raises(lambda: L(",S,Ana,10,,halves,Ana;Ben,\n"))) case("strikte Personenliste lehnt Tippfehler ab", lambda: raises(lambda: Ledger("# people: Ana, Ben\n" + H + ",S,Anna,10,,equal,all,\n"))) case("Namen ohne Groß-/Kleinschreibung zusammengeführt", lambda: L(",A,Ana,10,,equal,ana;Ben,\n").people == ["Ana", "Ben"]) case("Duplikatzeilen-Warnung", lambda: any("Duplikat" in w for w in L("1,Taxi,Ana,10,,equal,Ana;Ben,\n1,Taxi,Ana,10,,equal,Ana;Ben,\n").warnings)) case("fehlende Spalten abgelehnt", lambda: raises(lambda: Ledger("what,who\nx,y\n"))) case("schlechte Zahl abgelehnt", lambda: raises(lambda: L(",S,Ana,ten,,equal,Ana;Ben,\n"))) # Mindestüberweisungen case("Nullsummen-Paare gefunden (4 Personen -> 2 Überweisungen)", lambda: len(minimal({"A": 500, "B": -500, "C": 300, "D": -300}, list("ABCD"))[0]) == 2) case("keine Nullsummen-Untergruppe -> Personen - 1 Überweisungen", lambda: len(greedy({"A": 600, "B": 400, "C": -500, "D": -500}, list("ABCD"))) == 3 and len(minimal({"A": 600, "B": 400, "C": -500, "D": -500}, list("ABCD"))[0]) == 3) case("Minimum schlägt gierig bei 6 Personen", lambda: (lambda n: len(minimal(n, list("ABCDEF"))[0]) == 4 and len(greedy(n, list("ABCDEF"))) == 5)({"A": 700, "B": 300, "C": 250, "D": -500, "E": -450, "F": -300})) case("alle ausgeglichen -> keine Überweisungen", lambda: minimal({"A": 0, "B": 0}, ["A", "B"])[0] == []) def brute_min(net): ps = [p for p in net if net[p]] best = len(ps) - 1 if ps else 0 for parts in _partitions(ps): if all(sum(net[p] for p in g) == 0 for g in parts): best = min(best, len(ps) - len(parts)) return best def check_random(): rnd = random.Random(7) for _ in range(60): k = rnd.randint(2, 7) vals = [rnd.choice([-1, 1]) * rnd.choice([100, 200, 300, 500, 250, 50]) for _ in range(k - 1)] vals.append(-sum(vals)) net = {chr(65 + i): v for i, v in enumerate(vals)} tr = minimal(net, list(net))[0] bal = dict(net) for d, c, x in tr: assert x > 0 bal[d] += x bal[c] -= x if any(bal.values()) or len(tr) != brute_min(net): return False return True case("minimal == Brute-Force bei 60 zufälligen Gruppen und gleicht alle aus", check_random) case("Überweisungen gleichen das beispielähnliche Kassenbuch aus", lambda: _settles(L(",Flat,Ana,840,,shares,,Ana:3;Ben:3;Cem:2\n,Food,Cem,63.75,,equal,all,\n,Wine,Ben,36,,percent,,Ana:25;Ben:25;Cem:50\n"))) case("Render hat Überweisungen und Chat-Nachricht", lambda: "Nachricht für den Gruppenchat" in render(L(",Taxi,Ana,10,,equal,Ana;Ben,\n"))) case("Detailansicht", lambda: "Detail: Ben" in render(L(",Taxi,Ana,10,,equal,Ana;Ben,\n"), "ben")) case("JSON-Ausgabe", lambda: as_json(L(",Taxi,Ana,10,,equal,Ana;Ben,\n"))["transfers"] == [{"from": "Ben", "to": "Ana", "cents": 500}]) case("Tausenderformat", lambda: fmt(123456789, "EUR") == "1,234,567.89 EUR" and fmt(-5) == "-0.05") passed = sum(1 for _, ok, _ in cases if ok) for name, ok, err in cases: print(("PASS " if ok else "FAIL ") + name + ((" " + err) if err else "")) print("%d/%d bestanden" % (passed, len(cases))) return 0 if passed == len(cases) else 1 def _partitions(items): if not items: yield [] return first, rest = items[0], items[1:] for p in _partitions(rest): for i in range(len(p)): yield p[:i] + [[first] + p[i]] + p[i + 1:] yield [[first]] + p def _settles(led): b = led.balances() net = {p: b[p]["net"] for p in led.people} for d, c, x in minimal(net, led.people)[0]: net[d] += x net[c] -= x return not any(net.values()) def main(argv=None): ap = argparse.ArgumentParser(description="Gemeinsame Ausgaben aufteilen und die wenigsten Ausgleichsüberweisungen planen.") ap.add_argument("file", nargs="?", help="CSV-Kassenbuch ('-' = stdin)") ap.add_argument("--base", default=None, help="Basiswährung (Standard: '# base:'-Zeile oder EUR)") ap.add_argument("--rates", default=None, help="USD=0.92,GBP=1.16 (1 Einheit = Kurs Einheiten der Basis)") ap.add_argument("--people", default=None, help="durch Kommas getrennte Gruppenmitglieder (strikt: Tippfehler sind Fehler)") ap.add_argument("--detail", default=None, help="zeigt die zeilenweise Aufschlüsselung für eine Person") ap.add_argument("--json", action="store_true") ap.add_argument("--self-test", action="store_true") a = ap.parse_args(argv) if a.self_test: return self_test() if not a.file: ap.error("gib ein CSV-Kassenbuch oder --self-test an") try: text = sys.stdin.read() if a.file == "-" else open(a.file, encoding="utf-8-sig").read() people = [p.strip() for p in a.people.split(",")] if a.people else None led = Ledger(text, a.base, a.rates, people) out = json.dumps(as_json(led), indent=2) + "\n" if a.json else render(led, a.detail) except (OSError, LedgerError) as e: print("Fehler: %s" % e, file=sys.stderr) return 2 sys.stdout.write(out) return 0 if __name__ == "__main__": sys.exit(main())