Problem 8 - Largest Digit Sequence Product

The four adjacent digits in the provided 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.
Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

Note: my implementation was for the original version of the problem, which asked for the greatest product of a five-digit sequence. Thankfully, almost nothing had to change in the code to adjust for the new 13-term product.

Once again, my initial implementation leaves little to improve upon in terms of efficiency.

ind = 0
greatest = 0
while ind < len(d) - 12:
    sliced = d[ind:ind+13]
    temp = 1
    for x in sliced:
        temp *= x
    if temp > greatest:
        greatest = temp
    ind += 1

# 0.00393509864807 Seconds

One change we can make immediately is to check for products that we know would result in zero. Since we are calculating products (multiplication), we know that if a zero is in the factors, that our result will be zero. Thus, we can just skip digit sequences that contain one or more zeroes.

ind = 0
greatest = 0
while ind < len(d) - 12:
    sliced = d[ind:ind+13]
    if 0 in sliced:
        ind += 1
        continue
    temp = 1
    for x in sliced:
        temp *= x
    if temp > greatest:
        greatest = temp
    ind += 1

# 0.00193285942078 seconds

This seems to reduce our computing time by a factor of two. With a larger data set, we could verify this, but that's not what we want. This is Python; We want a one-liner. List comprehensions ahoy!

First, we need to generate the slices of the input digits d:

slices = [d[x:x+13] for x in range(len(d) - 12)]

But how do we calculate the product of each slice easily? There's no product(iterable) function in the default libraries, but we can create one easily if we take advantage of the associative property of multiplication by just multiplying the first number into the second, and the result into the third, etc. until we are down to one. For this, we can use the core library's reduce() function, which performs a passed function on each pair of a list until there is only one. We only need to pass it a function that multiplies the two parameters, and we can use a simple lambda function for that:

reduce(lambda x,y:x*y, slice)

These will give us a list of products when combined thus:

products = [reduce(lambda x,y:x*y, d[x:x+13]) for x in range(len(d) - 12)]

And, since Python lists conveniently have a maximum function, we just need to apply it.

answer = max([reduce(lambda x,y:x*y, d[x:x+13]) for x in range(len(d) - 12)])

# 0.00341510772705 seconds

This is on the same time order as my original implementation (that didn't skip zero products), and we can fix that with a quick condition in our comprehension:

answer = max([reduce(lambda x,y:x*y, d[x:x+13]) for x in range(len(d) - 12) if 0 not in d[x:x+13]])

# 0.0014820098877 seconds