Voor een slalomwedstrijd wordt de skipiste opgedeeld in een rechthoekig rooster. Verspreid over dit rooster zijn een aantal poortjes gestoken, waaraan telkens een score $$s \in \mathbb{N}_0$$ (int) wordt toegekend. De rijen van het rooster worden van boven naar onder genummerd, en de kolommen van links naar rechts, telkens vanaf nul. Hierdoor kunnen we de positie van een poortje voorstellen als een tuple $$(r, k)$$, waarbij het rijnummer $$r \in \mathbb{N}$$ (int) en het kolomnummer $$k \in \mathbb{N}$$ (int) aangeven waar het poortje zich bevindt.

Een skiër vertrekt bovenaan (boven rij 0 van het rooster) en kan de positie (kolom) waar hij vertrekt vrij kiezen. Bij elke stap verplaatst de skiër zich altijd

• één rij naar beneden

• maximaal één kolom naar links of naar rechts

De bewegingsvrijheden van de skiër kunnen dus als volgt weergegeven worden.

Door zijn beperkte bewegingsvrijheid kan de skiër dus niet altijd een parcours afleggen dat langs alle poortjes van de skipiste loopt. Door zijn vrije keuze van de startpositie is elk poortje wel bereikbaar vanaf de start, maar hij kan niet noodzakelijk van elk poortje naar elk ander poortje skiën. In de linker figuur hieronder zie je bijvoorbeeld dat het poortje op positie $$(3, 3)$$ bereikbaar is vanaf twee hoger gelegen poortjes op posities $$(0, 3)$$ en $$(1, 4)$$, en dat vanaf dit poortje maar twee van de lager gelegen poortjes op posities $$(6, 0)$$ en $$(8, 4)$$ kunnen bereikt worden.

De som van de scores van alle poortjes langs het parcours dat een skiër heeft afgelegd, noemen we de totaalscore van het parcours. Voor een gegeven configuratie van een skipiste kunnen we ons dus afvragen wat de maximale totaalscore is die een skiër kan behalen. Voor de skipiste die we hierboven als voorbeeld gebruikt hebben, is de maximale totaalscore gelijk aan 14. In de rechter figuur hierboven zie je het parcours dat de skiër moet afleggen om die totaalscore te behalen.

Opgave

Stel dat we een rechthoekige skipiste met $$m$$ rijen en $$n$$ kolommen hebben, waarop een aantal poortjes gestoken zijn. Dan kan het volgende algoritme gebruikt worden om de maximale totaalscore te vinden die een skiër op deze skipiste kan behalen:

1. Initialiseer een rij $$[0, 0, \ldots, 0]$$ met $$n$$ nullen. Deze rij bevat de maximale scores in de $$n$$ kolommen bij de start (in rij $$-1$$, de rij boven rij $$0$$).

2. Bereken de maximale scores in de $$n$$ kolommen op rij $$i$$ ($$i = 0, 1, \ldots, m - 1$$) op basis van de maximale scores in de $$n$$ kolommen op de vorige rij (rij $$i - 1$$). De maximale score op rij $$i$$ en kolom $$j$$ ($$j = 0, 1, \ldots, m - 1$$) is de som van

   • de score van het poortje op positie $$(i, j)$$ als er op die positie een poortje staat, anders $$0$$

   • het maximum van drie maximale scores op de vorige rij (rij $$i -  1$$), namelijk in de kolom links van de huidige kolom (kolom $$j - 1$$), in de huidige kolom (kolom $$j$$) en in de kolom rechts van de huidige kolom (kolom $$j + 1$$); merk op dat we aan de rand van de skipiste niet noodzakelijk nog een kolom links of een kolom rechts hebben; in dat geval nemen we het maximum over twee maximale scores

3. De maximale totaalscore is gelijk aan het maximum van de maximale scores in de onderste rij (rij $$m  - 1$$).

De volgende animatie toont hoe dit algoritme wordt toegepast op de skipiste die we hierboven als voorbeeld gebruikt hebben.

Gevraagd wordt:

• Schrijf een functie lees_poortjes waaraan de locatie (str) van een tekstbestand moet doorgegeven worden dat de posities van de poortjes op een skipiste beschrijft. Elke regel van het bestand beschrijft één poortje aan de hand van drie natuurlijke getallen $$r$$, $$k$$ en $$s$$, die telkens van elkaar gescheiden worden door één spatie. Daarbij geven het rijnummer $$r$$ en het kolomnummer $$k$$ aan waar het poortje zich bevindt, en geeft $$s$$ de score van het poortje aan. De functie moet een dictionary (dict) teruggeven die de posities $$(r, k)$$ van alle poortjes op de skipiste afbeeldt op hun score $$s$$ (int).

• Schrijf een functie volgende_rij die de maximale scores in de $$n$$ kolommen op rij $$i$$ berekent en teruggeeft, volgens het algoritme dat we hierboven beschreven hebben. Aan deze functie moeten drie argumenten doorgegeven worden: i) het rijnummer $$i$$ (int), ii) de maximale scores in de $$n$$ kolommen op de vorige rij (rij $$i - 1$$) en iii) een dictionary (dict) met de posities en de scores van alle poortjes op de skipiste (opgemaakt zoals de dictionaries die door de functie lees_poortjes teruggegeven worden). De maximale scores (int) in de $$n$$ kolommen op een rij worden als een lijst (list) voorgesteld.

• Schrijf een functie max_totaalscore die de maximale totaalscore (int) teruggeeft die een skiër op een skipiste kan behalen. Aan deze functie moeten drie argumenten doorgegeven worden: i) het aantal rijen (int) van de skipiste, ii) het aantal kolommen (int) van de skipiste en iii) de locatie (str) van een tekstbestand dat de posities van de poortjes op de skipiste beschrijft (zelfde opmaak als het bestand dat aan de functie lees_poortjes wordt doorgegeven).

Voorbeeld

Bij onderstaande voorbeeldsessie gaan we ervan uit dat het tekstbestand skipiste.txt¹ zich in de huidige directory bevindt.

>>> poortjes = lees_poortjes('skipiste.txt2')
>>> poortjes
{(0, 3): 2, (1, 0): 6, (1, 4): 3, (3, 3): 4, (4, 1): 2, (6, 0): 5, (8, 4): 1}
>>> volgende_rij(0, [0, 0, 0, 0, 0], poortjes)
[0, 0, 0, 2, 0]
>>> volgende_rij(1, [0, 0, 0, 2, 0], poortjes)
[6, 0, 2, 2, 5]
>>> volgende_rij(2, [6, 0, 2, 2, 5], poortjes)
[6, 6, 2, 5, 5]
>>> volgende_rij(3, [6, 6, 2, 5, 5], poortjes)
[6, 6, 6, 9, 5]
>>> volgende_rij(4, [6, 6, 6, 9, 5], poortjes)
[6, 8, 9, 9, 9]
>>> volgende_rij(5, [6, 8, 9, 9, 9], poortjes)
[8, 9, 9, 9, 9]
>>> volgende_rij(6, [8, 9, 9, 9, 9], poortjes)
[14, 9, 9, 9, 9]
>>> volgende_rij(7, [14, 9, 9, 9, 9], poortjes)
[14, 14, 9, 9, 9]
>>> volgende_rij(8, [14, 14, 9, 9, 9], poortjes)
[14, 14, 14, 9, 10]
>>> max_totaalscore(8, 5, 'skipiste.txt'3)
14