De bitcoin¹ is een digitale munteenheid waarvan de koers van dag tot dag sterk kan fluctueren. Van een goede vriend met voorspellende gaven heb je een tabel gekregen met de koers van de bitcoin (in euro) voor de komende $$n \in \mathbb{N}_0$$ dagen. Je vriend daagt je uit om met deze informatie zoveel mogelijk winst te proberen maken met het verhandelen van bitcoins tijdens deze periode. Daarbij gelden de volgende regels:

• aan het begin van de periode heb je geen bitcoin

• aan het einde van de periode heb je ook geen bitcoin

• je mag nooit meer dan één bitcoin tegelijkertijd in je bezit hebben

• elke dag van de periode kan je ofwel één bitcoin kopen als je er geen in je bezit hebt, of de bitcoin die je in bezit hebt verkopen, of helemaal niets doen (op dezelfde dag mag je dus niet én de bitcoin die je hebt verkopen én een nieuwe bitcoin kopen)

Het doel is om op het einde van de periode zoveel mogelijk winst te maken. Voor grote waarden van $$n$$ wordt het al snel onmogelijk om alle mogelijkheden voor het verhandelen van bitcoins te evalueren, om te zien welke van deze mogelijkheden de maximale winst oplevert. We kunnen de maximale winst echter op een veel snellere manier bepalen door bitcoins te kopen als die lokaal het goedkoopst zijn, en terug te verkopen als die lokaal het duurst zijn. Deze strategie wordt grafisch voorgesteld in onderstaande figuur.

Concreet bestaat deze gretige strategie erin om op elke dag — behalve de laatste dag — de volgende beslissingen te nemen:

• als je geen bitcoin hebt en morgen worden bitcoins duurder, koop dan vandaag een bitcoin

• als je wel een bitcoin hebt en morgen worden bitcoins goedkoper, verkoop dan vandaag je bitcoin

• in alle andere gevallen verhandel je vandaag geen bitcoins

De laatste dag verkoop je je bitcoin als je er één hebt, om zo nog wat extra winst op te strijken.

Als we deze strategie toepassen op het voorbeeld in bovenstaande figuur, dan kopen we de eerste dag een bitcoin aan €5 omdat bitcoins op dag 2 duurder zullen worden (€11) en we nog geen bitcoin hadden bij de start van de periode. Op de tweede dag verkopen we onze bitcoin terug aan €11 omdat bitcoins op dag 3 goedkoper zullen worden (€4). Op de derde dag kopen we geen bitcoin omdat bitcoins op dag 4 nog goedkoper zullen worden (€2). Als we op die manier verdergaan, dan maken we uiteindelijk €17 winst met het verhandelen van bitcoins.

Opgave

De koers van de bitcoin (in euro) doorheen een periode van $$n \in \mathbb{N}_0$$ opeenvolgende dagen stellen we voor als een reeks (list of tuple) met $$n$$ positieve getallen (int).

De acties die we uitvoeren tijdens zo een periode waarin we bitcoins verhandelen, stellen we voor als een string (str) van $$n$$ karakters. Hierbij kunnen enkel de volgende karakters voorkomen:

• een hoofdletter K stelt voor dat we op die dag één bitcoin kopen

• een hoofdletter V stelt voor dat we op die dag één bitcoin verkopen

• een koppelteken (-) stelt voor dat we op die dag geen bitcoins verhandelen

Uiteraard moeten deze acties voldoen aan de regels rond het kopen en verkopen van bitcoins zoals gesteld in de inleiding. Gevraagd wordt:

• Schrijf een functie winst waaraan twee argumenten moeten doorgegeven worden: i) de koers $$k$$ van de bitcoin (in euro) doorheen een periode van $$n \in \mathbb{N}_0$$ opeenvolgende dagen en ii) de acties $$a$$ die we uitvoeren tijdens die periode van $$n$$ dagen. De functie moet de winst (int; in euro) teruggeven die we opstrijken als we tijdens die periode van $$n$$ dagen bitcoins verhandelen volgens de gegeven acties, rekening houdend met de gegeven koers van de bitcoin tijdens die periode. Voor de acties $$a$$ die aan de functie doorgegeven worden moet de functie expliciet controleren dat:

  • $$a$$ een string (str) is

  • $$a$$ evenveel karakters telt als het aantal elementen van $$k$$

  • $$a$$ enkel geldige karakters bevat (K, V of -)

  • $$a$$ geen ongeldige acties uitvoert: een bitcoin kopen als je er al één hebt, een bitcoin verkopen als je er geen hebt of op het einde van de periode nog een bitcoin overhouden

  Als aan minstens één van deze voorwaarden niet voldaan is, dan moet een AssertionError opgeworpen worden met de boodschap ongeldige acties.

• Schrijf een functie maximale_winst waaraan de koers van de bitcoin (in euro) doorheen een periode van $$n \in \mathbb{N}_0$$ opeenvolgende dagen moet doorgegeven worden. De functie moet de maximale winst (int; in euro) teruggeven die je kunt bekomen door het verhandelen van bitcoins tijdens deze periode, rekening houdend met de regels voor het verhandelen van bitcoins en op basis van de gretige strategie zoals omschreven in de inleiding. Merk op dat deze winst eventueel €0 kan zijn, aangezien je überhaupt niet verplicht bent om binnen de periode ook maar één bitcoin aan te kopen of verkopen.

• Schrijf een functie optimale_acties waaraan de koers van de bitcoin (in euro) doorheen een periode van $$n \in \mathbb{N}_0$$ opeenvolgende dagen moet doorgegeven worden. De functie moet de acties (str) teruggeven die we tijdens deze periode moeten uitvoeren om maximale winst op te strijken bij het verhandelen van bitcoins, rekening houdend met de regels voor het verhandelen van bitcoins en op basis van de gretige strategie zoals omschreven in de inleiding.

Deze functies mogen ervan uitgaan dat het eerste argument dat wordt doorgegeven een geldige voorstelling is van de koers van de bitcoin (in euro) doorheen een periode van $$n \in \mathbb{N}_0$$ opeenvolgende dagen, zonder dat dit expliciet moet gecontroleerd worden.

Voorbeeld

>>> winst([5, 11, 4, 2, 8, 10, 7, 4, 3, 6], 'KV-K-V--KV')
17
>>> winst((4, 2, 5, 11, 10, 4, 11, 7, 4, 11, 3, 11), '-K-V-KV-KVKV')
31
>>> winst([10, 9, 9, 10, 10, 9, 1, 4, 9, 3, 5, 6, 10], '-K-V--K-VK--V')
16
>>> winst((12, 4, 9, 5, 6, 7, 9, 9, 11, 7, 10), '-KVK----VKV')
14
>>> winst([10, 9, 8, 7, 6, 5, 4, 3, 2, 1], '----------')
0
>>> winst((10, 4, 2, 4, 8, 12), 'K---VV')
Traceback (most recent call last):
AssertionError: ongeldige acties

>>> maximale_winst([5, 11, 4, 2, 8, 10, 7, 4, 3, 6])
17
>>> maximale_winst((4, 2, 5, 11, 10, 4, 11, 7, 4, 11, 3, 11))
31
>>> maximale_winst([10, 9, 9, 10, 10, 9, 1, 4, 9, 3, 5, 6, 10])
16
>>> maximale_winst((12, 4, 9, 5, 6, 7, 9, 9, 11, 7, 10))
14
>>> maximale_winst([10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
0
>>> maximale_winst((10, 4, 2, 4, 8, 12))
10

>>> optimale_acties([5, 11, 4, 2, 8, 10, 7, 4, 3, 6])
'KV-K-V--KV'
>>> optimale_acties((4, 2, 5, 11, 10, 4, 11, 7, 4, 11, 3, 11))
'-K-V-KV-KVKV'
>>> optimale_acties([10, 9, 9, 10, 10, 9, 1, 4, 9, 3, 5, 6, 10])
'--K-V-K-VK--V'
>>> optimale_acties((12, 4, 9, 5, 6, 7, 9, 9, 11, 7, 10))
'-KVK----VKV'
>>> optimale_acties([10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
'----------'
>>> optimale_acties((10, 4, 2, 4, 8, 12))
'--K--V'