Mainly Tech projects on Python and Electronic Design Automation.

Saturday, October 05, 2013

Project Euler #8 solution

Someone asked some innocuous question related to a Project Euler question where you had to find the largest number that is produced by multiplying five consecutive digits of a thousand digit number.

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.

2 comments:

  1. There is an off-by-one bug in the final output - it shows five characters, but shifted left by one.
    Try 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

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

    ReplyDelete

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us

Blog Archive