In deze oefening beschouwen we een reeks personen die schulden of tegoeden aan elkaar hebben. We proberen vervolgens een 2-tal algoritmen uit om deze schulden met een beperkt aantal transacties (betalingen van schuldenaars aan personen die een tegoed hebben) te vereffenen. De groep personen is niet vast en kan te allen tijde wijzigen.

We bouwen 3 klassen in deze opgave, namelijk:

• Schulden: basisklasse die een een algoritme bevat om het probleem wat te vereenvoudigen, transacties uit te voeren en ook een triviaal vereffeningsalgoritme bevat
• SchuldenCentralePot: deze klasse erft over van Schulden en implementeert een wat intelligenter algoritme
• SchuldenPaar: ook deze klasse erft over van Schulden, en realiseert een alternatief vereffeningsalgoritme

In deze oefening worden personen door strings voorgesteld (hun naam). Deze strings zijn uniek (er zijn geen 2 verschillende personen met dezelfde naam).

Opmerking: bij de opsomming van methoden in een klasse, wordt het argument self in de opgave nooit expliciet vermeld. Wanneer er dus aangegeven wordt dat een methode geen argumenten heeft, wordt eigenlijk bedoeld dat de methode enkel self als argument heeft. Wanneer vermeld wordt dat een methode 2 argumenten heeft, wordt bedoeld dat de methode naast het self-argument nog 2 bijkomende argumenten heeft.

Klasse Schulden

LET OP: Bij aanmaak van een object, gebruiken we een lijst van triplets (een tuple met drie elementen). Elk triplet bestaat uit:

• de naam van de schuldenaar (type str)
• de naam van de schuldeiser (type str)
• de grootte van de schuld (geheel, strikt positief, type int)

Je mag aannemen dat een persoon geen schulden bij zichzef aangaat. Bij de aanmaak van een schuldobject, geeft het triplet ('A', 'B', 20) aan dat persoon A een schuld heeft van 20 aan persoon B.

Een betaling wordt eveneens door een triplet vastgelegd, namelijk:

• de naam van de betaler (type str)
• de naam van diegene aan betaald wordt (type str)
• de grootte van de betaling (geheel, strikt positief, type int)

Je mag hierbij aannemen dat een persoon geen betalingen aan zichzelf uitvoert. Bij het uitvoeren van een betaling, geeft het triplet ('C', 'D', 50) aan dat persoon C het bedrag 50 betaalt aan persoon D.

Programmeer in deze klasse:

• een constructor met 1 argument, namelijk een lijst van triplets die de schulden voorstellen van de groep personen (let erop dat een personenpaar meerdere keren kan voorkomen in deze lijst).
• tegoed(): (zonder argumenten) Deze methode levert een woordenboek met als sleutel alle personen die in het probleem voorkomen. De bijhorende waarde is het bezit van die persoon. Het bezit kan je als volgt uitrekenen:
  • bereken $$S \ge 0$$, de totale schuld die de persoon heeft
  • bereken $$T \ge 0$$, het totale tegoed (m.a.w. de som van alle schulden van anderen aan die persoon)
  • het bezit is dan gelijk aan $$T - S$$
  Een persoon die als bezit 0 heeft, komt niet voor in het woordenboek. De som van alle waarden in het woordenboek bedraagt 0, omdat elke schuld ook aanleiding geeft tot een tegoed.
• __str__(): levert als stringgedaante de standaardgesorteerde versie van de huidige lijst van triplets op.
• vereenvoudig(): (zonder argumenten) Deze methode heeft als effect dat de lijst van opgeslagen triplets vereenvoudigd wordt, namelijk:
  • vervang alle triplets met identieke schuldenaar EN identieke persoon aan wie de schuld verschuldigd is, door 1 enkel triplet (namelijk de som van alle schulden aan die persoon)
  • vervolgens: indien in de resulterende lijst van triplets een triplet voorkomt (a, b, x) en ook een triplet (b, a, y), dan wordt dit paar vervangen door hoogstens 1 enkel triplet (indien a een schuld van x heeft aan b, en b een schuld van x aan a, dan verdwijnen beide triplets uit de lijst).
  • vervolgens: zorg ervoor dat er geen triplets meer voorkomen met als derde component de waarde 0 (verwijder deze triplets)
  Enkel strikt positieve waarden voor de schuld (3de element van elk triplet) zijn toegelaten. Deze bewerkingen wijzigen het bezit van elke persoon (gedefinieerd als het verschil tussen tegoeden en schulden) uiteraard NIET. De methode heeft geen returnwaarde.
• operator +=: deze operator heeft het volgende gedrag:
  • indien het rechteroperand GEEN lijst is, mag je veronderstellen dat het om een triplet gaat dat een betaling voorstelt (let op de volgorde van de elementen in dit triplet!). Het uitvoeren van de betaling heeft als effect dat het tegoed $$T$$ van diegene die betaalt stijgt, en het tegoed $$T$$ van de ontvanger daalt. Je mag aannemen dat het triplet een correcte betaling voorstelt.
  • indien het rechteroperand WEL een lijst is, mag je veronderstellen dat het om een lijst van betalingstriplets gaat. Je voert dan alle betalingen uit deze lijst uit, zoals in vorig puntje aangegeven.
• transacties(): oproepen van deze methode levert een set van betalingstriplets op, die de schulden zouden vereffenen mocht je ze doorvoeren (voer ze niet door in de methode zelf !). Deze methode heeft geen argumenten en kan je heel eenvoudig implementeren.

Voorbeeld

s = Schulden([('D', 'B', 50), ('B', 'D', 40), ('B', 'A', 80), ('A', 'C', 100), ('A', 'C', 40)])
print(s) #[('A', 'C', 40), ('A', 'C', 100), ('B', 'A', 80), ('B', 'D', 40), ('D', 'B', 50)]
print(s.tegoed()) #{'B': -70, 'A': -60, 'D': -10, 'C': 140}
s.vereenvoudig()
print(s) #[('A', 'C', 140), ('B', 'A', 80), ('D', 'B', 10)]
s += ('B', 'A', 20)
print(s.tegoed()) #{'B': -50, 'A': -80, 'D': -10, 'C': 140}
s += ('D', 'B', 60)
print(s.tegoed()) #{'B': -110, 'A': -80, 'D': 50, 'C': 140}
s += [('B', 'D', 10), ('C', 'A', 30), ('B', 'D', 100)]
print(s.tegoed())
{'A': -110, 'D': -60, 'C': 170}
t = s.transacties()
s += list(t)
print(s.tegoed()) #{}

Klasse SchuldenCentralePot

Deze klasse erft over van de klasse Schulden en implementeert een beter algoritme om de schulden te vereffenen, namelijk

• zoek de persoon A met het grootste tegoed, indien er meerdere personen hiervoor in aanmerking komen, neem dan de persoon die via standaardsortering eerst komt in een lijst van personen met dit zelfde grootste tegoed
• alle personen met openstaande schuld betalen hun volledige schuld aan A
• persoon A (die nu zelf een schuldenaar zou zijn), betaalt iedereen met een tegoed uit

Programmeer dit algoritme in de methode transacties() (zonder argumenten). Voer de betalingen NIET uit in deze methode, maar geef een verzameling van transactietriplets conform met deze aanpak.

Voorbeeld

s = SchuldenCentralePot([('D', 'B', 50), ('B', 'D', 40), ('B', 'A', 80), ('A', 'C', 100), ('A', 'C', 40)])
print(isinstance(s, Schulden)) #True
print(s.tegoed()) #{'B': -70, 'A': -60, 'D': -10, 'C': 140}
t = s.transacties()
print(t) #{('B', 'C', 70), ('D', 'C', 10), ('A', 'C', 60)}
s += list(t)
print(s.tegoed()) #{}

Klasse SchuldenPaar

Ook deze klasse erft over van de klasse Schulden. We programmeren hier een vereffening tussen koppels personen (en niet met een centrale persoon). Ga als volgt tewerk:

Herhaal tot alle schulden betaald
        Bepaal A, de persoon met de grootste schuld S
        Bepaal B, de persoon met het grootste tegoed V
        Indien S ≤ V: A betaalt S aan B
        Indien S > V: A betaalt V aan B

Indien je bij het bepalen van persoon A meerdere personen zou vinden, neem dan de persoon die eerst komt in de standaardsortering. Analoog voor persoon B.

Programmeer dit algoritme in de methode transacties() (zonder argumenten). Voer de betalingen NIET uit in deze methode, maar geef een verzameling van transactietriplets conform met deze aanpak.

Voorbeeld

s = SchuldenPaar([('D', 'B', 50), ('B', 'D', 40), ('B', 'A', 80), ('A', 'C', 100), ('A', 'C', 40)])
print(isinstance(s, Schulden)) #True
print(s.tegoed()) #{'D': -10, 'B': -70, 'A': -60, 'C': 140}
t = s.transacties()
print(t) #{('B', 'C', 70), ('D', 'C', 10), ('A', 'C', 60)}
s += list(t)
print(s.tegoed()) #{}

s = SchuldenPaar([('I', 'G', 90), ('C', 'G', 40), ('B', 'H', 80), ('A', 'F', 100), ('I', 'H', 100)])
print(isinstance(s, Schulden)) #True
print(s.tegoed()) #{'B': -80, 'C': -40, 'I': -190, 'H': 180, 'F': 100, 'A': -100, 'G': 130}
t = s.transacties()
print(t) #{('B', 'F', 80), ('I', 'F', 10), ('A', 'G', 100), ('C', 'F', 10), ('C', 'G', 30), ('I', 'H', 180)}
s += list(t)
print(s.tegoed()) #{}