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)
prod([2 3 4]) = (4/2)*prod([2 2 3])
trick if your data contains zeros. \$\endgroup\$