Project Euler 008 – Grootste product in een reeks

Probleemstelling

In het gegeven getal van 1000 cijfers hebben de vier opeenvolgende cijfers met het grootste product het product $9\cdot9\cdot8\cdot9=5832$ .

Bepaal het grootste product van dertien opeenvolgende cijfers in dat getal.

Eerste analyse

Een string van 1000 cijfers bevat $1000-13+1=988$ delen van dertien opeenvolgende cijfers. We bekijken elk deel en bewaren het grootste product. Er is voor deze opgave geen aparte wiskundige formule nodig.

We vergelijken een rechtstreekse aanpak met een variant die een deel overslaat zodra het een nul bevat. Een product met een factor nul kan immers nooit groter worden dan een reeds gevonden positief product.

Een stringdeel omzetten

Met slicing halen we dertien tekens uit de string:

deel = getal[begin : begin + 13]

int(deel) zou van bijvoorbeeld "7316" het getal 7316 maken. Wij willen echter $7\cdot3\cdot1\cdot6$ berekenen. Daarom doorlopen we het deel teken per teken:

product = 1

for teken in deel:
    product *= int(teken)

Een afzonderlijk teken zoals "7" is aanvankelijk tekst. int(teken) zet het om in het gehele getal 7, waarna het kan worden vermenigvuldigd. Het product begint bij 1, het neutrale element van de vermenigvuldiging.

Vergelijking van de methoden

De eerste methode zet voor ieder deel alle dertien tekens om en vermenigvuldigt ze. De tweede methode gebruikt eerst:

if "0" in deel:
    continue

Een deel met een nul wordt dan onmiddellijk overgeslagen. Van de 988 delen bevatten er 731 een nul; in deze invoer kan de tweede methode dus veel werk vermijden. Daar staat tegenover dat de nultest zelf ook tijd kost en dat delen zonder nul tweemaal worden doorlopen.

Om toevallige schommelingen bij zo’n kort programma te beperken, voert het programma elke methode 1.000 keer uit en rapporteert het de gemiddelde uitvoeringstijd. De precieze verhouding is afhankelijk van de computer en Python-versie.

Gemeenschappelijke gegevens

Beide programma’s gebruiken dezelfde variabele getal, die de 1000 cijfers als één aaneengesloten string bevat. In Python worden opeenvolgende strings tussen haakjes automatisch samengevoegd. De volledige invoer hoeft daardoor niet op één onleesbaar lange regel te staan.

getal = (
    "73167176531330624919225119674426574742355349194934"
    "96983520312774506326239578318016984801869478851843"
    "85861560789112949495459501737958331952853208805511"
    "12540698747158523863050715693290963295227443043557"
    "66896648950445244523161731856403098711121722383113"
    "62229893423380308135336276614282806444486645238749"
    "30358907296290491560440772390713810515859307960866"
    "70172427121883998797908792274921901699720888093776"
    "65727333001053367881220235421809751254540594752243"
    "52584907711670556013604839586446706324415722155397"
    "53697817977846174064955149290862569321978468622482"
    "83972241375657056057490261407972968652414535100474"
    "82166370484403199890008895243450658541227588666881"
    "16427171479924442928230863465674813919123162824586"
    "17866458359124566529476545682848912883142607690042"
    "24219022671055626321111109370544217506941658960408"
    "07198403850962455444362981230987879927244284909188"
    "84580156166097919133875499200524063689912560717606"
    "05886116467109405077541002256983155200055935729725"
    "71636269561882670428252483600823257530420752963450"
)

Programma 1 – Altijd dertien cijfers vermenigvuldigen

Dit eerste programma berekent voor elk van de 988 delen het volledige product, ook wanneer een van de cijfers nul is.

import time


def grootste_product(reeks, lengte):
    grootste = 0

    for begin in range(len(reeks) - lengte + 1):
        deel = reeks[begin : begin + lengte]
        product = 1

        for teken in deel:
            product *= int(teken)

        if product > grootste:
            grootste = product

    return grootste


# Meet 1.000 uitvoeringen en bereken het gemiddelde
starttijd = time.perf_counter()

for _ in range(1_000):
    antwoord = grootste_product(getal, 13)

gemiddelde_tijd = (time.perf_counter() - starttijd) / 1_000

print(f"Het grootste product is: {antwoord}")
print(f"Gemiddelde uitvoeringstijd: {gemiddelde_tijd:.8f} seconden")

Programma 2 – Delen met een nul overslaan

Het tweede programma controleert elk deel eerst op een nul. Alleen wanneer er geen nul aanwezig is, worden de dertien cijfers naar gehele getallen omgezet en vermenigvuldigd.

import time


def grootste_product_zonder_nul(reeks, lengte):
    grootste = 0

    for begin in range(len(reeks) - lengte + 1):
        deel = reeks[begin : begin + lengte]

        if "0" in deel:
            continue

        product = 1
        for teken in deel:
            product *= int(teken)

        if product > grootste:
            grootste = product

    return grootste


# Meet 1.000 uitvoeringen en bereken het gemiddelde
starttijd = time.perf_counter()

for _ in range(1_000):
    antwoord = grootste_product_zonder_nul(getal, 13)

gemiddelde_tijd = (time.perf_counter() - starttijd) / 1_000

print(f"Het grootste product is: {antwoord}")
print(f"Gemiddelde uitvoeringstijd: {gemiddelde_tijd:.8f} seconden")

Beide methoden hebben tijdscomplexiteit $O(nk)$ voor een reeks van $n$ cijfers en delen van lengte $k$ . Voor de vaste waarde $k=13$ is dit $O(n)$ . De nultest verbetert niet de theoretische grootteorde, maar kan wel de werkelijke uitvoeringstijd verkorten.

Concrete tijdsvergelijking

Op dezelfde computer en met telkens 1.000 uitvoeringen werden de volgende gemiddelde tijden gemeten:

Methode	Gemiddelde tijd per uitvoering
Altijd dertien cijfers vermenigvuldigen	0,00116562 seconden
Eerst controleren op een nul	0,00039123 seconden

De verhouding is

$\frac{0{,}00116562}{0{,}00039123}\approx 2{,}98.$

De methode met nultest was bij deze meting dus ongeveer 2,98 keer zo snel. Anders uitgedrukt: de gemiddelde uitvoeringstijd daalde met ongeveer

$\left(1-\frac{0{,}00039123}{0{,}00116562}\right)\cdot100\%\approx66{,}4\%.$

De precieze tijden kunnen bij een volgende uitvoering verschillen door de computer, de Python-versie en andere actieve processen. De vergelijking blijft hier inhoudelijk zinvol omdat beide methoden onder dezelfde omstandigheden en even vaak werden uitgevoerd.

Resultaat

Beide programma’s geven als grootste product

$\boxed{23514624000}.$

Besluit

De rechtstreekse methode is het eenvoudigst, maar voert ook veel overbodige omzettingen en vermenigvuldigingen uit. De nultest is een kleine, duidelijke optimalisatie die gebruikmaakt van de eigenschap dat een product met nul altijd nul is. Omdat 731 van de 988 delen een nul bevatten, leverde deze aanpak in de concrete meting een snelheidswinst van ongeveer factor 2,98 op.