The digits were presented as twenty rows of fifty characters and the question was about how to grab the web page and extract the number.

I decided to do a straight-forward copy-paste of the digits into a string and going from there.

The algorithm I use recognises that finding a zero in the digits zeroes out any product and just traverses the digits in order performing appropriate actions based on accumulated state:

# http://projecteuler.net/problem=8#! xstring = '''73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450''' x = int(xstring.replace('\n', '')) xl = [int(ch) for ch in xstring if ch != '\n'] # current product; current maximum and index of where seen; number of digits contributing to prod prod, mx, digits = 0, (0, -1), 0 for i, digit in enumerate(xl): if digit == 0: # Need to start again at next non-zero prod = digits = 0 else: digits += 1 if digits == 1: prod = digit else: prod *= digit if digits > 5: # Remove influence of the first of six digits currently in product prod //= xl[i - 5] digits -= 1 if digits == 5 and prod > mx[0]: # New max at position i mx = (prod, i) if mx[0]: print ("The greatest product of five consecutive digits in the 1000-digit number") print ("is %i for ...%s... occurring at digits in position up to %i" % (mx[0], ''.join(str(i) for i in xl[mx[1] - 5: mx[1]]), mx[1])) else: print ("The greatest product of five consecutive digits in the 1000-digit number does not occur")

The output is:

The greatest product of five consecutive digits in the 1000-digit number

is 40824 for ...39987... occurring at digits in position up to 368

- END.

There is an off-by-one bug in the final output - it shows five characters, but shifted left by one.

ReplyDeleteTry it with xl=[9,8,7,6,5,4,3,2,1] to see what I mean.

You need this:

print ("is %i for ...%s... occurring at digits in position up to %i" % (mx[0], ''.join(str(i) for i in xl[mx[1] - 4: mx[1] + 1]), mx[1]))

Then you get this more sensible output:

is 40824 for ...99879... occurring at digits in position up to 368

Or just `x = ''' ... whatever ... '''.replace("\n", ""); print(max(eval("*".join(x[i:i+5])) for i in range(len(x)-4)))`

ReplyDelete