008 - paths across grid

See Problem 8: Find the greatest product of five consecutive digits in a 1000-digit number.

This is fairly straightforward. First we define the number, using Python's implicit string continuation:

numstr = '73167176531330624919225119674426574742355349194934'
'96983520312774506326239578318016984801869478851843'
'85861560789112949495459501737958331952853208805511'
'12540698747158523863050715693290963295227443043557'
'66896648950445244523161731856403098711121722383113'
'62229893423380308135336276614282806444486645238749'
'30358907296290491560440772390713810515859307960866'
'70172427121883998797908792274921901699720888093776'
'65727333001053367881220235421809751254540594752243'
'52584907711670556013604839586446706324415722155397'
'53697817977846174064955149290862569321978468622482'
'83972241375657056057490261407972968652414535100474'
'82166370484403199890008895243450658541227588666881'
'16427171479924442928230863465674813919123162824586'
'17866458359124566529476545682848912883142607690042'
'24219022671055626321111109370544217506941658960408'
'07198403850962455444362981230987879927244284909188'
'84580156166097919133875499200524063689912560717606'
'05886116467109405077541002256983155200055935729725'
'71636269561882670428252483600823257530420752963450'

To avoid converting each number 5 times as the search moves over it, we use a functional programming construct:

numlist = map (int, numstr)

Then we move along the the length of the number and calculate for each frame (i.e. set of 5 consecutive numbers):

max_product = 0
max_frame = None
frame_size = 5
from operator import mul
for i in xrange (len (numlist) - frame_size):
   curr_frame = numlist[i:i+frame_size]
   if 0 in curr_frame:
      continue
   curr_product = reduce (mul, curr_frame)
   if (max_product < curr_product):
      max_product = curr_product
      max_frame = curr_frame
print max_product, max_frame

The import mul / reduce code is just a simple trick pinched from Python Idioms to calculate the product of a sequence. There some attempted efficiency here, where we abort calculations if a 0 appears in the frame, but it may not save much time. For interest, we also print out the maximum frame, but without these two features, a more compact version would be:

for i in xrange (len (numlist) - frame_size):
   curr_frame = numlist[i:i+frame_size]
   curr_product = reduce (mul, curr_frame)
   max_product = max (max_product, curr_product)
print max_product

Computation time is negligible.

My initial solution for this problem tried to reduce the number of multiplications involved, by calculating the product for the initial frame and then shifting it along one. The product of the new frame would be that of the old one, multiplied by the value of the new position and divided by the position that has just dropped off:

[2 4 1 2 5] # product is 2*4*1*2*5=80
[4 1 2 5 3] # product is 80*3/2=120

However, this fails utterly when 0s appear in the sequence.