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.