# Project Euler 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?

My first solution seems to perform comparably to those found in the related question, though I don't know how it fares in the time complexity department.

pe8.py:

#!/usr/bin/env python3

input_digits = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
greatest_product = 0

blocks_without_zeroes = tuple(filter(None, input_digits.split('0')))
for block in blocks_without_zeroes:
for shift in range(len(block) - adjacent_number + 1):
product = 1
product *= int(block[i + shift])
if product > greatest_product:
greatest_product = product

print(greatest_product)


I've cheated a bit on the benchmark by not defining any function, and indeed running it through cProfile shows that I've only used 92 function calls. But then it becomes difficult to do unit testing, so I've upped the program a bit and now it has functions, unit tests and can read command line arguments.

euler8.py:

#!/usr/bin/env python3.6

import argparse
import random

def is_digit(string):
if not string.isdigit():
raise argparse.ArgumentTypeError("{} is not comprised of digits".format(string))
return string

"""It is the end user's responsibility to guard against illegal input
that is not a combination of a string of digits and a whole number.
"""
blocks_without_zeroes = tuple(filter(None, input_digits.split('0')))
for block in blocks_without_zeroes:
for shift in range(len(block) - adjacent_number + 1):
product = 1
product *= int(block[i + shift])
if product > greatest_product:
greatest_product = product

if __name__ == '__main__':

parser = argparse.ArgumentParser(description="Project Euler Problem 8")
parser.add_argument('-n', '--number', nargs=1, type=is_digit, default=[''.join(random.choices('0123456789', k=1000))])
args = parser.parse_args()

input_digits = vars(args)['number'].pop()

print("Q: Find the", adjacent_number, "adjacent digits in", input_digits, "that have the greatest product.")
print("A:", ' × '.join(adjacent_digits), "=", str(greatest_product))


test_euler8.py:

#!/usr/bin/env python3.6

import unittest

def test_ordinary_inputs(self):
self.assertEqual(adgp('91935150686511566951', 4), ('5669', 5 * 6 * 6 * 9))

def test_input_digits_all_zeroes(self):
self.assertEqual(adgp('0' * 7, 3), ('0' * 3, 0))

def test_input_digits_all_ones(self):
self.assertEqual(adgp('1' * 7, 4), ('1' * 4, 1))

def test_nil_zero(self):

if __name__ == '__main__':
unittest.main()


I have little experience with writing unit tests, so I will be glad to receive some input on this. Otherwise, clean code, performance, and anything else you want to throw at me!

I basically took the same approach as the OP of the related question and implemented both a naive search, which is shown in the question, and an improved search, as shown below:

def adjacent_digits_with_greatest_product(input_digits, adjacent_number):
"""It is the end user's responsibility to guard against illegal input
that is not a combination of a string of digits and a whole number.
"""
blocks_without_zeroes = tuple(filter(None, input_digits.split('0')))
for block in blocks_without_zeroes:
product = 1
product *= int(block[i])
for shift in range(-1, len(block) - adjacent_number):
if shift >= 0:
product = product // int(block[shift]) * int(block[shift + adjacent_number])
if product > greatest_product:
greatest_product = product


I run the following code to compare the performance of my naive and improved solutions as well as the accepted answer in the other question:

#!/usr/bin/env python3.6

from functools import reduce

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

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

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)

def filter_slices(num_list, length):
for start, stop in get_slices(num_list):
if stop - start > length:
yield start, stop

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

def slice_string_search(num_list, length):
num_list = [int(i) for i in num_list]
return int(max(
max(get_products(num_list[start: stop], length))
for start, stop in filter_slices(num_list, length)
))

if __name__ == '__main__':

import cProfile
import random
import euler8naive
import euler8

n = ''.join(random.choices('0123456789', k=100000))
for a in range(1, 21):
print("a =", a)
cProfile.run("slice_string_search(n, a)")


I'm on Windows, so I run it in PowerShell:

python .\test.py | where { \$_ | select-string -pattern "(a =)|(seconds)" }


which outputs

a = 1
9050 function calls in 0.053 seconds
18096 function calls in 0.052 seconds
166169 function calls (158023 primitive calls) in 0.073 seconds
a = 2
9050 function calls in 0.069 seconds
17197 function calls in 0.048 seconds
158753 function calls (151431 primitive calls) in 0.071 seconds
a = 3
9050 function calls in 0.079 seconds
16373 function calls in 0.045 seconds
151133 function calls (144573 primitive calls) in 0.069 seconds
a = 4
9050 function calls in 0.088 seconds
15611 function calls in 0.047 seconds
143862 function calls (137963 primitive calls) in 0.069 seconds
a = 5
9050 function calls in 0.096 seconds
14950 function calls in 0.041 seconds
136746 function calls (131440 primitive calls) in 0.066 seconds
a = 6
9050 function calls in 0.101 seconds
14357 function calls in 0.039 seconds
129687 function calls (124924 primitive calls) in 0.065 seconds
a = 7
9050 function calls in 0.104 seconds
13814 function calls in 0.045 seconds
122967 function calls (118684 primitive calls) in 0.063 seconds
a = 8
9050 function calls in 0.105 seconds
13334 function calls in 0.034 seconds
116502 function calls (112650 primitive calls) in 0.062 seconds
a = 9
9050 function calls in 0.106 seconds
12903 function calls in 0.031 seconds
110534 function calls (107055 primitive calls) in 0.059 seconds
a = 10
9050 function calls in 0.105 seconds
12530 function calls in 0.039 seconds
104244 function calls (101135 primitive calls) in 0.058 seconds
a = 11
9050 function calls in 0.101 seconds
12160 function calls in 0.027 seconds
98124 function calls (95355 primitive calls) in 0.055 seconds
a = 12
9050 function calls in 0.099 seconds
11820 function calls in 0.025 seconds
92785 function calls (90297 primitive calls) in 0.053 seconds
a = 13
9050 function calls in 0.096 seconds
11539 function calls in 0.032 seconds
88345 function calls (86079 primitive calls) in 0.052 seconds
a = 14
9050 function calls in 0.093 seconds
11317 function calls in 0.023 seconds
83179 function calls (81159 primitive calls) in 0.050 seconds
a = 15
9050 function calls in 0.091 seconds
11071 function calls in 0.021 seconds
78779 function calls (76959 primitive calls) in 0.050 seconds
a = 16
9050 function calls in 0.086 seconds
10871 function calls in 0.025 seconds
74524 function calls (72889 primitive calls) in 0.049 seconds
a = 17
9050 function calls in 0.083 seconds
10686 function calls in 0.018 seconds
71164 function calls (69669 primitive calls) in 0.047 seconds
a = 18
9050 function calls in 0.079 seconds
10546 function calls in 0.017 seconds
67889 function calls (66525 primitive calls) in 0.046 seconds
a = 19
9050 function calls in 0.077 seconds
10415 function calls in 0.017 seconds
64379 function calls (63150 primitive calls) in 0.053 seconds
a = 20
9050 function calls in 0.075 seconds
10280 function calls in 0.015 seconds
61139 function calls (60030 primitive calls) in 0.043 seconds


A 2–5 times speedup for typical cases. Not bad.