Project Euler: getallenroosters

Er zijn enkele opgaven in Project Euler waarin je een rooster met getallen krijgt voorgeschoteld. Daarin moet je dan iets uitrekenen en er zijn dus allerlei bewerkingen nodig, maar hoe pak je dat aan? Hoe 'werkt' een 'vierkant' getallenrooster en bestaan er ook driehoekige? Ongeacht welke vorm je in de uitdagingen tegenkomt, er is altijd een oplossing als je maar weet hoe en waar je moet beginnen.

Inhoudsopgave

• Wat is een getallenrooster?
• Voorbeeld door middel van een assenstelsel
• Andere vormen

Wat is een getallenrooster?

Definitie

Allereerst de definitie van een 'getallenrooster' in Project Euler: een verzameling kolommen en rijen die een bepaalde rangschikking hebben en waarin getallen staan. Dit kan in de vorm van een 'normaal' vierkant zijn, maar ook een driehoek en wie weet in de toekomst zelfs een vijf- of een zeshoek!

Laten we eens kijken naar een simpel voorbeeld van vier kolommen en vier rijen.

Richtingen

Als ik je nu zou vragen om vier getallen te vinden in dezelfde richting, die rechtstreeks met elkaar verbonden zijn, welke mogelijkheden zijn er dan?

Ten eerste de vier horizontale rijen: reeksen '1 2 3 4', '5 6 7 8', '9 1 2 3', '4 5 6 7'.
Ten tweede de vier verticale kolommen: reeksen '1 5 9 4', '2 6 1 5', '3 7 2 6', '4 8 3 7'.
Ten derde de twee diagonalen: '1 6 2 7' en '4 1 7 4'.

Je zoekt dus van boven naar beneden, van links naar rechts en diagonaal. Het is net een woordzoeker! Deze regels veranderen niet als het rooster groter wordt. Zo heeft Project Euler probleem 11: largest product in a grid, een veld van twintig bij twintig getallen. Dat wordt een stuk lastiger om met de hand uit te rekenen, nietwaar?

Voorbeeld door middel van een assenstelsel

Transformatie van getallenrooster naar coördinaten

Tijd om dat getallenrooster nog nauwkeuriger te bekijken. Wat zou er gebeuren als je het probleem zou voorstellen als een assenstelsel met coördinaten? Dan wordt de vier linksonder punt (0,0), de één linksboven punt (0,3), de zeven rechtsonder punt (3,3) en de vier rechtsboven punt (3,3).


Het is handig om een datastructuur (array, vector, enzovoort) toe te passen om de getallen in op te slaan. Bedenk zelf welke voor- en nadelen dat biedt met het oog op grotere getallenroosters. Nu hoef je alleen nog maar de waarde van een coördinaat toe te kennen aan het opgeslagen getal.

Van coördinaten naar code

Hoe gebruik je deze nieuwe informatie? Zodra je een bewerking wilt uitvoeren (vermenigvuldiging, in het geval van Euler probleem 11) op een aantal getallen in dezelfde richting, heb je alleen nog de coördinaten nodig.

Het werkt bijvoorbeeld als volgt:

Horizontaal
Punt linksonder tot en met het vierde getal naar rechts.
(x, y) * (x+1, y) * (x+2, y) * (x+3, y)


Verticaal
Punt linksboven tot en met het vierde getal naar beneden.
(x, y+3) * (x, y+2) * (x, y+1) * (x, y)


Diagonaal linksboven naar rechtsonder
(x,y+3) * (x+1, y+2) * (x+2, y+1) * (x+3, y)


Diagonaal linksonder naar rechtsboven
(x,y) * (x+1, y+1) * (x+2, y+2) * (x+3, y+3)


En zo doorzoek je het hele getallenrooster van links naar rechts, van boven naar beneden en diagonaal totdat je alles hebt uitgerekend.

Andere vormen

Euler probleem 18 heeft de vorm van een driehoek. Dat doet denken aan de driehoek van Pascal! Daarin zijn de getallen op de volgende rij de som van de getallen op de rij daarboven. Toegegeven, het is niet identiek, maar de logica die er inzit kun je toepassen op het driehoekige getallenrooster.

Bijvoorbeeld:

Stel dat ik wil weten welke route in deze 'piramide' de hoogste uitkomst heeft, dan is dat snel gevonden: 2 van de eerste rij, plus 2 van de tweede rij, plus 4 van de derde rij is 2+2+4 = 8.

Echter, wat als het driehoekige getallenrooster niet uit drie rijen met getallen bestaat, maar uit meer dan duizend? Zou het niet makkelijker zijn om de rijen zodanig te bewerken dat hun aantal vermindert? Door de hoogste getallen uit elke rij bij elkaar op te tellen krijg je het volgende:

We beginnen bij de tweede en de derde rij:

Het maximum van alle getallen in de derde rij is vier. Het maximum van de getallen in de tweede rij is (in dit geval) twee. Tel de gevonden getallen op bij het maximum van rij één (er is maar een getal aanwezig) en je komt ook uit op acht. Zo heb je drie rijen gereduceerd tot één. Herhaal het proces totdat je de laatste rij van de piramide hebt uitgerekend.