<jupyter_start><jupyter_text>[Project Euler](https://projecteuler.net)[Problem 8](https://projecteuler.net/problem=8)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?<jupyter_code>from __future__ import print_function
import string
import operator
from functools import reduce
s = '''
 73167176531330624919225119674426574742355349194934
 96983520312774506326239578318016984801869478851843
 85861560789112949495459501737958331952853208805511
 12540698747158523863050715693290963295227443043557
 66896648950445244523161731856403098711121722383113
 62229893423380308135336276614282806444486645238749
 30358907296290491560440772390713810515859307960866
 70172427121883998797908792274921901699720888093776
 65727333001053367881220235421809751254540594752243
 52584907711670556013604839586446706324415722155397
 53697817977846174064955149290862569321978468622482
 83972241375657056057490261407972968652414535100474
 82166370484403199890008895243450658541227588666881
 16427171479924442928230863465674813919123162824586
 17866458359124566529476545682848912883142607690042
 24219022671055626321111109370544217506941658960408
 07198403850962455444362981230987879927244284909188
 84580156166097919133875499200524063689912560717606
 05886116467109405077541002256983155200055935729725
 71636269561882670428252483600823257530420752963450
 '''
s = ''.join(c for c in s if c in string.digits)
len(str(s)), s
def foo(s, n):
    biggest_product = 0
    for i in range(len(s) - n + 1):
        t = s[i:i+n]
        product = reduce(operator.mul, map(int, t))
        if product > biggest_product:
            biggest_product = product
    return biggest_product
foo(s, 4)
n = 13
%timeit foo(s, n)
foo(s, n)
def foo(s, n):
    adjacent_digits = (s[i:i+n] for i in range(len(s) - n + 1))
    products = (
        reduce(operator.mul, map(int, t))
        for t in adjacent_digits)
    return max(products)
n = 13
%timeit foo(s, n)
foo(s, n)
def foo(s, n):
    return max(
        reduce(operator.mul, map(int, s[i:i+n]))
        for i in range(len(s) - n + 1))
n = 13
%timeit foo(s, n)
foo(s, n)<jupyter_output>100 loops, best of 3: 6.05 ms per loop<jupyter_text>It seems that having s as a big string and repeatedly converting digits to ints is wasteful, so I convert s to be a list of ints and repeat the above adjusted for dealing with a list of ints.<jupyter_code>s = list(map(int, s))
def foo(s, n):
    biggest_product = 0
    for i in range(len(s) - n + 1):
        t = s[i:i+n]
        product = reduce(operator.mul, t)
        if product > biggest_product:
            biggest_product = product
    return biggest_product
foo(s, 4)
n = 13
%timeit foo(s, n)
foo(s, n)
def foo(s, n):
    adjacent_digits = (s[i:i+n] for i in range(len(s) - n + 1))
    products = (
        reduce(operator.mul, t)
        for t in adjacent_digits)
    return max(products)
n = 13
%timeit foo(s, n)
foo(s, n)
def foo(s, n):
    return max(
        reduce(operator.mul, s[i:i+n])
        for i in range(len(s) - n + 1))
n = 13
%timeit foo(s, n)
foo(s, n)<jupyter_output>1000 loops, best of 3: 1.88 ms per loop<jupyter_text>Having s be a list of ints made the code faster and easier to read.That's a nice combination. Below, I explore optimizing for speed.<jupyter_code># Keep a running product,
# so that one only needs to
# 1. divide out the digit that is "leaving"
# 2. multiply by the new digit.
#
# Handling zeroes makes the code complicated.

def foo(s, n):
    biggest_product = 0
    need_to_recalculate = True
    for i in range(len(s) - n + 1):
        t = s[i:i+n]
        if need_to_recalculate:
            product = reduce(operator.mul, t)
        else:
            product *= t[-1]
        if product > biggest_product:
            biggest_product = product
        if product == 0:
            need_to_recalculate = True
        else:
            product //=t[0]
    return biggest_product
n = 13
%timeit foo(s, n)
foo(s, n)
# When a zero digit is encountered,
# skip over the subsequences that would include it.

def foo(s, n):
    biggest_product = 0

    for i in range(len(s) - n + 1):
        if all(s[i:i+n]):
            break

    while i < len(s) - n + 1:
        if s[i+n-1] == 0:
            i += n
            continue

        product = reduce(operator.mul, s[i:i+n])
        if product > biggest_product:
            biggest_product = product
        i += 1

    return biggest_product
n = 13
%timeit foo(s, n)
foo(s, n)
# When a zero digit is encountered,
# skip over the subsequences that would include it.
#
# Avoid the special case code that frets over
# a zero in the initial subsequence.

def foo(s, n):
    biggest_product = 0

    i = 0
    while i < len(s) - n + 1:
        if s[i+n-1] == 0:
            i += n
            continue

        product = reduce(operator.mul, s[i:i+n])
        if product > biggest_product:
            biggest_product = product
        i += 1

    return biggest_product
n = 13
%timeit foo(s, n)
foo(s, n)<jupyter_output>1000 loops, best of 3: 1.02 ms per loop<jupyter_text>The while stuff is very un-Pythonic, but fast.Next I try using a more Pythonic iter(range(...)),but it is even uglier than the while stuff above.<jupyter_code>def foo(s, n):
    biggest_product = 0

    iter_i = iter(range(len(s) - n + 1))
    for i in iter_i:
        if s[i+n-1] == 0:
            [next(iter_i) for _ in range(n-1)]
            continue

        product = reduce(operator.mul, s[i:i+n])
        if product > biggest_product:
            biggest_product = product

    return biggest_product
n = 13
%timeit foo(s, n)
foo(s, n)
# Put the repeated next(iter_i) in a for loop
# instead of a comprehension.
#
# I am surprised that it is faster.
# It it very ugly also, although probably a little bit clearer.

def foo(s, n):
    biggest_product = 0

    iter_i = iter(range(len(s) - n + 1))
    for i in iter_i:
        if s[i+n-1] == 0:
            # Skip over the subsequences that include this zero digit.
            # Want to do i += n.
            for _ in range(n-1):
                next(iter_i)
            continue

        product = reduce(operator.mul, s[i:i+n])
        if product > biggest_product:
            biggest_product = product

    return biggest_product
n = 13
%timeit foo(s, n)
foo(s, n)<jupyter_output>1000 loops, best of 3: 1 ms per loop
{'fraction_non_alphanumeric': 0.0797245397960535, 'fraction_numerical': 0.2791683220765461, 'mean_word_length': 3.4792408066429417, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 20, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '633140', 'license': 'MIT', 'n_tokens_mistral': 4034, 'n_tokens_neox': 2762, 'n_words': 705, 'path': 'euler-008-largest-product-in-a-series-20161128.ipynb', 'repo_name': 'james-prior/euler', 'size': '7551'}