// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (15 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 8 Solution

Project Euler 8 Solution

Project Euler 8: Find the largest product of 13 consecutive digits.


Project Euler 8 Solution Problem Description

Project Euler 8: Find the greatest product of 13 consecutive digits for a large number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
… {continued}

Analysis

We begin by opening and reading the file “pe8.txt” (the second tab next to the main.py tab in the Trinket window) and concatenate each line into one long string by stripping (rstrip) whitespace (which includes the new line character, \n) from the end of the lines. Finally, each character is separated, converted to an integer, and added to a list named d.

d = map(int, ''.join(line.rstrip() for line in open('pe8.txt')))

If you can be assured that a group product greater than zero exists, you could map individual zeros and move the search pointer forward. But, hey, this same algorithm solved the much more aggressive HackerRank version just fine.

Next a length (L) is set defining the search length, 13 for this exercise, and we make sure there are enough digits to search. If not we exit printing “None.”

If there are enough digits, we consider each 13-digit set, starting from index (i) 0 until we reach the end, taking into account the search length: 1000-13+1 = 988. The reduce function runs each 13-digit set through a multiplier and we capture the maximum of all the sets calculated.

L = 13
print 'Greatest product of', L, 'consecutive \ndigits =', 
print "None."  if L>len(d) else  \
            max(reduce(mul, d[i:i+L]) for i in xrange(len(d)-L+1))

80% of the Python solutions listed in the Project Euler forum are wrong as they don’t consider the last digit in the search space. Because the solution to this problem lies in the middle somewhere, these programs calculate a correct response in this instance. If you were to run them with the following parameters they would fail by erroneously producing a zero instead of 18:
d = [0,0,0,1,9,2]
L = 3

Further, many of these same erroneous programs would return an error or zero (a distinct possibility) which could be misleading; it’s better to return some indication that an answer cannot be calculated, such as “None,” to indicate an undefined condition:
d = [0,0,0,1,9,2]
L = 13

h_mark_sm-05bceb881aa02b72d688d21db01df5d8
This program and method
solves all test cases
on HackerRank for Project Euler 8


Project Euler 8 Solution

Runs < 0.002 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 8 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|23514624000|

Afterthoughts

  • PEP 8 is the style guide for Python. It describes the preferred methods for formatting Python source code for a consistent appearance. We do our best to follow those guidelines to make the code as readable as possible.
Project Euler 8 Solution last updated

Discussion

No comments yet.

Post a comment