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


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)
  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 are closed.