Python Find the N adjacent digits in the 1000-digit number that have the greatest product

Question

This question was presented to me, adapted from Project Euler #8. The goal is to find the N adjacent digits in the 1000-digit number that have the greatest product. Range of N: 10 <= N <= 50. Not only I have to find the max product of 13 consecutive digits in a sequence, I also had to find the max product of 19, 35, 46. This is really no biggie, just scaling up from the previous 13. Anyway, I set out to code two solutions, one which is done by a generator ( I love these efficient things, so useful in Project Euler) and another which I would describe it as code I written before I knew about generators.

Code 1 (Generator):

number=7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450

def largestproduct(adjdigit):
    x=0
    y=adjdigit
    z=str(number)[x:y]
    product=1
    count=0
    while y<=1000:
        for i in z:
            if count==adjdigit:
                yield product
                product=1
                count=0
                x+=1
                y+=1
                z=str(number)[x:y]
            product*=int(i)
            count+=1
print(max(largestproduct(13)))

Code 2 (Non-generator):

number=7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450

def largestproduct(adjdigit):
    x=0
    y=adjdigit
    z=str(number)[x:y]
    product=1
    count=0
    control=0
    while y<=1000:
        for i in z:
            if count==adjdigit:
                if product>control:
                    control=product
                product=1
                count=0
                x+=1
                y+=1
                z=str(number)[x:y]

            product*=int(i)
            count+=1
    return control
print(largestproduct(19))

Which one would be better and more efficient to use? To me, generators are always the best due to them lacking the need to occupy tons of space in memory when processing large amounts of data. Oh and please suggest improvements, and cool functions and tools that can be useful from other Python packages.

Answer 1

Review

Yes the first option would be better as memory might become an issue with really long numbers (say you have a 10 million length number). But that implementation could be improved as well

• Your first solution does not return the max product but rather a list generator of products. This is confusing!
• Chop up your code into functions, as it makes it easier to test/change things

The problem can be divided into to 3 seperate functions:

1. Cut a big number into evenly sized chunks of adjacent digits
2. Sum the product of the chunks
3. A main function that returns the largest adjecent product

Alternative Code

from functools import reduce
import operator

def cut_adj_chunks(iterable, chunk_size):
    for i in range(len(iterable) - chunk_size):
        yield iterable[i:i+chunk_size]

def sum_prod(num_str):
    num_list = map(int, num_str)
    return reduce(operator.mul, num_list, 1)

def largest_prod(adj_digits, big_num):
    return max(sum_prod(chunk) for chunk in cut_adj_chunks(str(big_num), adj_digits))

Answer 2

Coding style

There is a well-established coding style for Python, the PEP8 coding style, and conformance to that style can be checked online at PEP8 online.

In your case it reports “missing space around operator” in almost every code line.

Variable names

x, y, z are meaningless variable names, and adjdigit isn't self-explaining either.

Magic numbers

The number 1000 in

while y<=1000:

is the string length – which might not be obvious to the reader, and is error-prone if you change the given number. It should be computed from the string instead.

Global variables

You pass the number of adjacent digits as an argument to the function, but the big number itself is a global variable. Passing both parameters to the function makes it easier to add unit tests.

Simplify the program logic

You reset count, product, and z each time after a product is computed, this seems unnecessary complicated to me.

    z = str(number)[x:y]
    product = 0
    for i in z:
        product *= int(i)
    yield product

would be easier to understand and also makes the count variable obsolete.

The iteration over all possible start/end positions is better done with a for loop.

Avoid unnecessary conversions

In your code, the big number is converted to a string repeatedly, it would be sufficient to convert it only once. You could even provide the given number as a string directly.

The substring z is also not needed because we can access a character from the original string directly.

Putting it together

Summarizing the suggested changes so far, the generator-based version could look like this:

def products(number, num_digits):
    for start_index in range(0, len(number) - num_digits):
        product = 1
        for i in range(start_index, start_index + num_digits):
            product *= int(number[i])
        yield product


def max_product(number, num_digits):
    return max(products(number, num_digits))


if __name__ == "__main__":
    large_number = "73167176531330624919225119674426574742355349194934969" \
        "8352031277450632623957831801698480186947885184385861560789112949" \
        "4954595017379583319528532088055111254069874715852386305071569329" \
        "0963295227443043557668966489504452445231617318564030987111217223" \
        "8311362229893423380308135336276614282806444486645238749303589072" \
        "9629049156044077239071381051585930796086670172427121883998797908" \
        "7922749219016997208880937766572733300105336788122023542180975125" \
        "4540594752243525849077116705560136048395864467063244157221553975" \
        "3697817977846174064955149290862569321978468622482839722413756570" \
        "5605749026140797296865241453510047482166370484403199890008895243" \
        "4506585412275886668811642717147992444292823086346567481391912316" \
        "2824586178664583591245665294765456828489128831426076900422421902" \
        "2671055626321111109370544217506941658960408071984038509624554443" \
        "6298123098787992724428490918884580156166097919133875499200524063" \
        "6899125607176060588611646710940507754100225698315520005593572972" \
        "571636269561882670428252483600823257530420752963450"
    print(max(products(large_number, 13)))

To generate or not to generate ...

I don't think there is much difference with respect to efficiency. Your second “non-generator” version does not occupy more space because each product is immediately compared against the current maximum, and not stored in a list.

The advantage of the generator-based version is that the two tasks

• generating all possible products,
• determining the maximum

are clearly separated.

Performance improvements

Every substring is converted to a number by iterating over all of its characters. This can be improved by updating the product instead, this “sliding windows technique” is described for example in

• Efficiency on Project Euler Problem #8
• Project Euler #8