Project Euler #8 - Largest product in series

Question

The problem

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

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

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

Solving this problem seemed almost trivial to me: Since the number is so small one can easily just iterate through all the values.

def naive_str_search(num_list, length):
    num_list_length = len(num_list)
    product_max = 1
    for k in range(num_list_length-length+1):
        product = 1
        for i in range(length):
            product *= int(num_list[k+i])
        if product > product_max:
            product_max = product
    return product_max

quick q: Should one use product_max = max(product,product max) instead of the if-sentence?

I wanted to be a bit fancy and see if I could improve the performance of my code. My idea is that since we are dealing with products and finding the largest one, any zeroes will break the product.

Firstly, I found all the zeroes:

num_length = len(num_list)
break_points = [0]

for i in range(num_length):
    if num_list[i] == 0:
        break_points.append(i)

Then I tried to find all the valid intervals. These will be between two zeros and have a length greater than the number of adjacent digits.

for i in range(len(break_points)):
    if i == 0: 
        start = 0
        stop = break_points[1]  
    elif i == len(break_points)-1: 
        start = break_points[-1]
        stop = num_length
    else:
        start = break_points[i]+1
        stop = break_points[i+1]
    if stop - start >= length:
        interval = num_list[start:stop]

Here num_list is the list of all the numbers in the series. Now for each of these valid intervals I again tried to get clever. If the next element in the product is greater than the first; then the product will increase.

Say num_list = [2 2 3 4 2] and length = 3 then prod([2 2 3]) < prod([2 3 4]) because 2 < 4. Given we have calculated prod([2 2 3]) one can calculate the next by doing prod([2 3 4]) = (4/2)*prod([2 2 3]).

In the opposite case one can ignore to calculate the product because the last value is smaller. Note if we ignore to calculate the product one can not use the trick above, since we are missing the previous product. All together I tried the following code:

def substring_search(num_list_sub,length):
    combo = True
    product_max = 1
    for i in range(length-1,len(num_list_sub)):
        # If we are at the start, the end, or have just found 
        # a lower value we calculate the whole product
        if i == length-1 or i == len(num_list_sub):
            product = prod(num_list_sub[i-length+1:i+1]) 
            product_max = max(product,product_max)
        # If the next element is greater than the first element
        # then the product is larger. Calculate the new product
        elif num_list_sub[i] > num_list_sub[i-length]:
            if combo:
                product *= float(num_list_sub[i])/max(num_list_sub[i-length],1)
            else:
                product = prod(num_list_sub[i-length+1:i+1])
            product_max = max(product, product_max)
            combo = True
        else:
            combo = False
        # If the next element is not greater than the first element
        # set combo to zero and calculate the whole product in the next loop
    return int(product_max)

quick q:

My code only employs the multiplication trick once, can one extend it further (if num_list_sub[i] < num_list_sub[i-length] then test num_list_sub[i:i+1] > num_list_sub[i-length:i-length+1]?

I tried doing this for an arbitary k, but I had problems figuring out when the cost of doing this exceeded the cost of just calculating the sum.

Tl;DR

• Are there any further optimizations I could do?
• Are there other ways to solve this problem faster?

Running speed

                 ---------------------------------
                 |    n     |   time   |  avg/ms |
|--------------------------------------|---------|
|naive_search    |  5*10^4  |  184.02  |  3.681  |
|improved_search |  5*10^4  |   27.27  |  0.545  |
--------------------------------------------------

magnitude = 6.748

I used the following code to test the efficiency of my code, in comparison to the naive approach:

n = 20000
t0 = time.time()
for i in range(n): naive_str_search(num_list,13)
t1 = time.time()
total_n1 = t1-t0
print "naive_str_search =", total_n1

t0 = time.time()
for i in range(n): improved_str_search(num_list,13)
t1 = time.time()
total_n2 = t1-t0
print "improved_str_search =", total_n2
print "magnitude =", total_n1/total_n2

---

The whole code

import math
import time


def naive_str_search(num_list, length):
    num_list_length = len(num_list)
    product_max = 1
    for k in range(num_list_length-length+1):
        product = 1
        for i in range(length):
            product *= int(num_list[k+i])
        if product > product_max:
            product_max = product
    return product_max


def prod(list):
    return reduce(lambda x, y: int(x) * int(y), list)


def improved_str_search(num_list, length):
    num_length = len(num_list)
    product_max = 0
    break_points = [0]
    # Finds all the zeroes in the list
    for i in range(num_length):
        if num_list[i] == 0:
            break_points.append(i)
    # Iterates over all the intervals between the zeroes
    for i in range(len(break_points)):
        if i == 0:
            start = 0
            stop = break_points[1]
        elif i == len(break_points)-1:
            start = break_points[-1]
            stop = num_length
        else:
            start = break_points[i]+1
            stop = break_points[i+1]
        if stop - start >= length:
            interval = num_list[start: stop]
            product = substring_search(interval, length)
            product_max = max(product, product_max)
    return product_max


def substring_search(num_list_sub, length):
    combo = True
    product_max = 1
    for i in range(length-1, len(num_list_sub)):
        # If we are at the start, the end, or have just found
        # a lower value we calculate the whole product
        if i == length-1 or i == len(num_list_sub):
            product = prod(num_list_sub[i-length+1:i+1])
            product_max = max(product, product_max)
        # If the next element is greater than the first element
        # then the product is larger. Calculate the new product
        elif num_list_sub[i] > num_list_sub[i-length]:
            if combo:
                product *= float(num_list_sub[i])/max(num_list_sub[i-length], 1)
            else:
                product = prod(num_list_sub[i-length+1:i+1])
            product_max = max(product, product_max)
            combo = True
        else:
            combo = False
        # If the next element is not greater than the first element
        # set combo to zero and calculate the whole product in the next loop
    return int(product_max)


if __name__ == "__main__":

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

    num_list = [int(i) for i in n]

    print improved_str_search(num_list, 13)
    print naive_str_search(num_list, 13)

Answer 1

I initially read your algorithm wrong. No wonder your code seemed so strange. Turns out i != 0 is not i == 0.

---

You should also try using enumerate. It will remove the num_list[i] part. It's good to use features that produce more understandable code. Personally I think that making a generator is better than a list. And performs marginally faster compared to list comprehensions when you use all the results.

def get_indexes(num_list):
    for index, item in enumerate(num_list):
        if item == 0:
            yield index

This is the same as building the list before. It's cleaner this way, and you don't have to have everything in memory.

Next you should try not to have redundant if statements. One way to do this is to use a function to handle the slicing. Or another generator.

Also your code looks at all the zeros, despite not wanting to, '01230'[0:4] #0123, '01230'[0 + 1:4] #123

def get_slices(num_list):
    start = 0
    stop = 0
    for item in get_indexes(num_list):
        start, stop = stop, item
        yield start + 1, stop
    yield stop + 1, len(num_list)

# Don't want complex code
def filter_slices(num_list, length):
    for start, stop in get_slices(num_list):
        if stop - start > length:
            yield start, stop

This quite simply removes the first group of ifs. You could have put filter_slices in get_slices, and when exiting the for loop called the if start - stop >= length again. However personally I think this way is nicer, and more understandable. You could say, there are too many generators, and I would agree. But at least then you could reuse them...

We can now find out what your code is doing in little to no time.

Now you can change the first function into a for loop, or a generator comprehension feeding into max. Both are viable options, as there are no longer any if statements at this level.

return max(
    substring_search(num_list[start: stop], length)
    for start, stop in filter_slices(num_list, length)
)

This removes waisted CPU cycles on the hard to understand ifs. And makes your code much clearer. with the ability to change it to allow re-use of filters. This can be done by changing the for loop to loop through a passed iterable, rather than making one.

# Current way, not as reusable
def get_indexes(num_list):
    for index, item in enumerate(num_list):
        if item == 0:
            yield index

get_indexes([0, 1, 2, 3, 0])

# Alternate way, verbose when creating.
def get_indexes(num_list):
    for index, item in num_list:
        if item == 0:
            yield index

get_indexes(enumerate([0, 1, 2, 3, 0]))

Now time to change substring_search. So let's make more generators. If you were to not use generators, store common function outputs in a variable. length - 1, there should be spaces around the minus, as per PEP8. And len(num_list_sub) as you don't change the array. And you should also make another function, to simplify calls.

So first off I would make a generator to loop thorough, like get_slices.

def get_filtered_products(num_list, length):
    combo = True
    # Remove the first if. And,
    # Explicitly state the creation of product.
    product = prod(num_list[0:length])
    yield product
    for index in range(length, len(num_list)):
        if num_list[index] > num_list[index - length]:
            if combo:
                # You could use `from __future__ import division`
                # That would allow you to remove explicit conversion.
                product *= float(num_list[index]) / num_list[index - length]
            else:
                product = prod(num_list[index - length + 1:index + 1])
            yield product
            combo = True
        else:
            combo = False

Also if you changed it so that you only use num_list_sub[i] / num_list_sub[i - length] it would be faster. This would also make it simpler.

def get_products(num_list, length):
    product = float(prod(num_list[0:length]))
    yield product
    for index in range(length, len(num_list)):
        product *= num_list[index] / num_list[index - length]
        yield product

So personally I think your if statements hindered both the readability and the performance.

Due to the change in get_products and get_filtered_products to change them to generators. You will need to change the main generator comprehension.

# PS you have to do change `num_list` to `list<int>`, instead of it being `str`.
return int(max(
    max(get_products(num_list[start: stop], length))
    for start, stop in filter_slices(num_list, length)
))

This is probably as fast as you are going to get it, without using numpy. I tried a variety of solutions, and I couldn't get them faster than this. And when I tried juvian's solution it was slower than the above. I did change theirs to take a string, rather than an list of integers however.

---

Results:

filtered_string_search uses get_filtered_products.
slice_string_search uses get_products.

I also put the type conversion into the function. As you are given a string, not a list of integers.

naive_str_search = 94.60598158836365
improved_str_search = 20.996577262878418
str_search = 15.884466171264648
filtered_str_search = 13.688666105270386
sliced_str_search = 10.223053693771362
linearSearch = 12.361925840377808 (Juvian's answer)

---

Original answer's code:

def prod(a, b): return a * b

def get_indexes(num_list, length):
    cutoff_index = length - 1
    for index, item in enumerate(num_list):
        if index > cutoff_index and num_list[index - 1] > num_list[index - length - 1]:
            yield index
        if item == 0:
            cutoff_index = index + length

def str_search(num_list, length):
    num_list = [int(i) for i in num_list]

    return max(
        reduce(prod, num_list[large_index - length: large_index])
        for large_index in get_indexes(num_list, length)
    )

Answer 2

Given even the naive solution finishes in ms, is this one test you care about optimising?

It can be done in one line which would be in the order of the naive solution:

max(reduce(mul, (int(a) for a in num[x:x+13])) for x in range(len(num)-12))

But I used a simple generator using a deque to hold the 13 digits, setting the maxlen means it automatically bumps off the earlier digits:

from collections import deque
from functools import reduce
from operator import mul

def prod_series(n, d):
    q = deque(maxlen=d)
    for _ in range(d-1):   # Prime the deque
        q.append(next(n))
    for i in n:
        q.append(i)
        if 0 in q:
            continue
        yield reduce(mul, q)

%%timeit
max(prod_series((int(i) for i in n), 13))
1000 loops, best of 3: 746 µs per loop

Which isn't the fastest but would argue it is quite readable. It is also space efficient in that it never creates another list except the 13 len deque. You could also add n = iter(n) at the beginning if you wanted to handle lists. I had some further optimisations, e.g. handling the 0's directly if i == 0: ignored = 13; if ignored: ignored -= 1 continue, which shaves off 100 µs. And then handling the multiply directly: v //= old; v *= i; yield v, but the code started looking ugly so I ditched it all in favour of readibility.

For reference:

naive_str_search: 100 loops, best of 3: 3.42 ms per loop
improved_str_search: 1000 loops, best of 3: 893 µs per loop
linear_search: 1000 loops, best of 3: 484 µs per loop

Okay adding the optimisation above doesn't look too bad. Extending the deque to 14, so that q[0] is always the number exiting the 13 numbers:

from collections import deque

def gen(n, d):
    q = deque([1], maxlen=d+1)
    m, p = 1, d
    for c in n:
        if c == 0:
            m, p = 1, d
            continue
        q.append(c)
        m *= c
        if p:        # Prime the deque
            p -= 1
            continue
        m //= q[0]
        yield m

%%timeit
max(gen(map(int, n), 13))    # Note: Python3
1000 loops, best of 3: 383 µs per loop

Answer 3

Tried both solutions you used, the one posted by @ErikR and my own:

naive_str_search = 4.78699994087

improved_str_search = 0.906000137329

numpySolver = 7.0 # either it is slow or its because I have mingw

linearSearch = 0.343999862671 # my solution

My solution runs in linear time:

def linearSearch(digits, k):
    l = 0; #non 0 digits from last 0 we found
    prod = 1

    maxProd = 0

    for i in range(0,len(digits)): # for each index of digits
        prod*=digits[i] # we multiply the accumulative product by the digit at position i
        l+=1 # we add 1 to consecutive non 0
        if digits[i] == 0: # if its actually a 0, we reset both length and prod
            l=0
            prod = 1
        if l >= k: # we have found at least k non 0 consecutive digits
            maxProd = max(maxProd,prod) # store max between maxValue and newValue
            prod/=digits[i-k+1] # we remove the last digit from the product with division, so prod now has k-1 digits multiplications

    return maxProd

For example with 234567881 and k = 7, 2*3*4*5*6*7*8 = 40320. We store that as new max. Then we remove last digit from the product --> in this case, the 2: 40320/2 = 20160. Now 20160*8 = 161280 and this is our new max. 161280/3 = 53760. 53760*1 = 53760. Its not higher than before. So the max in all cases was 161280

Answer 4

I think you really should look at this guy's solution which employs numpy:

http://pythonwise.blogspot.com/2015/04/solving-project-euler-problem-8-with.html

The advantages are:

• the code is simpler
• it is easier to understand ...
• which increases your confidence that it doesn't have any bugs

Since it uses numpy it probably is also faster. It does more multiplies, but it also can take advantage of your CPU's vector pipeline.

More importantly, though, due to the way the code is structured it is much easily parallelizable. It breaks up the problem into a number of independent computations which can be evaluated on multiple cores. Even if numpy doesn't do that for you right now, that capability could be added to numpy in the future and your code would automatically run faster. Additionally the numexpr package can also detect common parallelization situations and automatically run your code on multiple cores for you.

So there are a lot of good reasons to structure your code the way this guy has done it.