Nov

25

Project Euler: Largest product of consecutive digits

Filed Under hisabati, project euler by  

For Problem 8 in Project Euler, you are required to find the largest product of 5 consecutive digits in a 1000 digit integer.

7316717653133062491922511967442657474235534919493496983520
3127745063262395783180169848018694788518438586156078911294
9495459501737958331952853208805511125406987471585238630507
1569329096329522744304355766896648950445244523161731856403
0987111217223831136222989342338030813533627661428280644448
6645238749303589072962904915604407723907138105158593079608
6670172427121883998797908792274921901699720888093776657273
3300105336788122023542180975125454059475224352584907711670
5560136048395864467063244157221553975369781797784617406495
5149290862569321978468622482839722413756570560574902614079
7296865241453510047482166370484403199890008895243450658541
2275886668811642717147992444292823086346567481391912316282
4586178664583591245665294765456828489128831426076900422421
9022671055626321111109370544217506941658960408071984038509
6245544436298123098787992724428490918884580156166097919133
8754992005240636899125607176060588611646710940507754100225
6983155200055935729725716362695618826704282524836008232575
30420752963450

My implementation for this proceeds as follows:

  1: def window_slice_product(num,windowSize):
  2:     digits = [int(x) for x in str(num)]
  3:     sequencewindowSize = len(digits)
  4:     if(sequencewindowSize <= windowSize):
  5:         return prod(digits)
  6:
  7:     products =[]
  8:     curr_product = prod(digits[:windowSize])
  9:     max_product = curr_product
 10:     for i in range(1, sequencewindowSize - windowSize + 1):
 11:         stopPosition = i + (windowSize - 1)
 12:         outItem = digits[i - 1]
 13:         inItem = digits[stopPosition]
 14:         if(outItem == 0):
 15:             curr_product = prod(digits[i:stopPosition + 1])
 16:         else:
 17:             curr_product = (curr_product / outItem) * inItem
 18:         if(curr_product > max_product):
 19:             max_product = curr_product
 20:     return max_product

Given the digits in the input number, we create a list with all the integers in sequence. To calculate the required product, we create a sliding window of length 5, which serves as a snapshot of the list. In each iteration of the loop starting on line 10, we ‘slide’ the window down the list (we start with the window’s first element at index 0 and consider 5 consecutive items; move the window to have first item at index 1 and consider 5 items etc until we get to the point where the window’s starting element is at index 995). We take the product of each window and check if it’s higher than the maximal product seen so far. At the end, we report the max product.

We achieve some performance gain by taking advantage of the overlap between adjacent windows. If the window has length 5, then adjacent windows have 3 elements in common. The overlap elements contribute the same value to the product computed for the two adjacent windows. Therefore, the difference between the product computed for a window starting at index i and one starting at i+1 is due to elements at the end of the windows. Specifically, the product of the window rooted at i+1 is given by the dividing the value of the product of the window rooted at i by the value of the ith element (undoing the effect of the element we’re removing) multiplied by the value of the element at position i+(windowSize – 1) (adding the effect of the new element). This is achieved in lines 11 to 17 of the algorithm posted.

In the cases where we remove a zero, its necessary to compute the product for the new window by multiplying all items in the window – otherwise we would end up dividing by zero.

Comments

Comments are closed.