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?
In [1]:
from __future__ import print_function
In [2]:
import string
import operator
from functools import reduce
In [3]:
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
Out[3]:
In [4]:
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
In [5]:
foo(s, 4)
Out[5]:
In [6]:
n = 13
%timeit foo(s, n)
foo(s, n)
Out[6]:
In [7]:
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)
In [8]:
n = 13
%timeit foo(s, n)
foo(s, n)
Out[8]:
In [9]:
def foo(s, n):
return max(
reduce(operator.mul, map(int, s[i:i+n]))
for i in range(len(s) - n + 1))
In [10]:
n = 13
%timeit foo(s, n)
foo(s, n)
Out[10]:
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.
In [11]:
s = list(map(int, s))
In [12]:
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
In [13]:
foo(s, 4)
Out[13]:
In [14]:
n = 13
%timeit foo(s, n)
foo(s, n)
Out[14]:
In [15]:
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)
In [16]:
n = 13
%timeit foo(s, n)
foo(s, n)
Out[16]:
In [17]:
def foo(s, n):
return max(
reduce(operator.mul, s[i:i+n])
for i in range(len(s) - n + 1))
In [18]:
n = 13
%timeit foo(s, n)
foo(s, n)
Out[18]:
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.
In [19]:
# 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
In [20]:
n = 13
%timeit foo(s, n)
foo(s, n)
Out[20]:
In [21]:
# 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
In [22]:
n = 13
%timeit foo(s, n)
foo(s, n)
Out[22]:
In [23]:
# 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
In [24]:
n = 13
%timeit foo(s, n)
foo(s, n)
Out[24]:
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.
In [25]:
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
In [26]:
n = 13
%timeit foo(s, n)
foo(s, n)
Out[26]:
In [27]:
# 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
In [28]:
n = 13
%timeit foo(s, n)
foo(s, n)
Out[28]:
For readability, I like cell #17 the best.
For speed, cells #23 and #27 are the fastest, but very ugly.