The website has problem eight stated as such,“Find the greatest product of five consecutive digits in the 1000-digit number.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450”
Yeah, looks pretty intimadating to me too. ;) Lucky enough for both of us this really isn't all that hard to figure out.
Python
#!/usr/bin/python3 """ code solution for Euler Project #8 """ import operator from functools import reduce if __name__ == "__main__": index = 0 high_score = 0 investigate_this = 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450 digit_list = [int(x) for x in str(investigate_this)] digit_list_length = len(digit_list) while index < digit_list_length: if index == 0: temp_product = reduce(operator.mul, digit_list[index: index +5]) elif index == 1: temp_product = reduce(operator.mul, digit_list[index - 1: index + 4]) elif index == digit_list_length - 1: temp_product = reduce(operator.mul, digit_list[index - 4: index + 1]) elif index == digit_list_length - 2: temp_product = reduce(operator.mul, digit_list[index - 3: index + 2]) else: temp_product = reduce(operator.mul, digit_list[index -2 : index + 3]) if temp_product > high_score: high_score = temp_product index += 1 print(high_score)
For my first attempt I took an approach of having a travelling index and checking both two digits before and two digits after the index. This worked out pretty well except that I needed to add four special use cases (the first two index points and the last two). Some people may say that it's not “pythonic” to use reduce, and in some ways I can agree with it. However, in this case my reduce fuctions really aren't very complicated and I think they look cleaner than using for loops in this instance. Does anyone out there have any opinions?
Haskell
module Main where investigate_this = map digitToInt $ show 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450 productof5 index | index >= investigate_length - 4 = []
In my next solution, I followed the same idea of using a traveling index, but this time I only paid attention to the index and the next four digits. The advantage to this was that I only needed to worry about one special case, and that was if the number of multipliers were less than five total. This did seem to simplify things.
Sorry to all my Perl & Java readers. Life is kind of chaotic at the moment and I only really had the energy to do these two languages. One day I hope to revisit this problem in those languages, and when I do I'll update this post with the new code additions.
I realize in the last few times I've posted project euler solution I haven't said anything so just to nail this thought home amongst the people reading this. I look forward to hearing any and all constructive comments regarding algorythms and code. Oh, and one more thing, I apologize in advance for the formatting of the rather large number.

My Python version.
My Python version is similar to yours, but instead of converting the number to a string and turning it into a list of integers, I start out with a string and index it, converting to integers as it's needed.
Yours is probably more efficient, since you only convert every digit to an integer once, and index a list, while mine has to change from string to integer five times for most of the digits.
Though I'm not sure why you need all of those special cases, mine works fine without them. Am I missing something? Even in your Haskell version, which is closer to mine, you have one special case.
Fixed version:
Shorter Haskell
Hi :)
I don't know if that's idiomatic Haskell, as I started a out about a week ago with that language,
but I notice you can have it in three lines without using any library function.
Supposing the number is stored in a multi-line text-file,
you can brutally process all combinations at once by shifting all digits at once,
one, two, three and four times, yielding five lists of digits
that you can match against each other with a "zipWith (*)".
Like so :
It certainly is more memory-hungry, but feels like an APLish magical way of doing things.
Greetings :-)
Hey Matt, thanks for your
Hey Matt, thanks for your comment.
I like how you shortened the code. You've managed to really condense it down nicely.
Also thank you for the example of using read in map. I was having a really hard time with trying to do exactly that within another script.
A totally different Perl version
ObfuPerl
Micheal Peters went with the obvious perl implementation. That leaves the least obvious implementation:
The syntax is horrible and could use some sugar coating. But I actually like the idea of iterating over all possible matches. But it could look something like:
But I'm not quite sure what a good name for multimatch would be.
Hi Bryce, Much thanks, your
Hi Bryce,
Much thanks, your post led me to the Project Euler site. I think the deque solution is much better than what I scratched together after reading the problem.
--amal
Alternative Haskell
I personally don't like writing Haskell that uses indexes. It's feels "un-hask-thonic'. This is my most succinct version. The work is all in largestProductOfN.
There is a possible bug though. If the last 5 digits of the list were [... 0, 9, 9, 9, 9] this code would calculate [... 0, 6561, 726, 81, 9].
These are spurious values and if all the other results are less than 6561 this will get picked up as the largest. This can be fixed by adding a 0 on the end of the [list], but the number given already has one.
Your index based version won't do that.
Hey Paul, thanks for the non
Hey Paul, thanks for the non index using haskell code.
I'm still to new to Haskell and trying to wrap my head around funtional programming to completely understand what is "hask-thonic" and what isn't. Hell I feel like I've accomplished an amazing feet of intellectual prowess getting Haskell to do this much. ;)
Padding
Pad the list with [1,1,1,1] at the front and back, and run from 2 to len -2.
One trick that I always
One trick that I always forget about in python is that a deque works as a "shift-register" if you initialize it with a maxlength parameter.
Hey Will, Thanks for sharing
Hey Will,
Thanks for sharing the information regarding the shift register. I will definitely have to research that one a little more.
5 digits
> the product of a subset of five digits can't be more than that of the five
Sure it can, if the range contains one or more zeros that are not included in the subset. Now imagine the range starting with zero and with a zero in every 5th position following that - then the highest product would be the multiplication of the 4 last numbers...
Anyway, the problem clearly states; "Find the greatest product of five consecutive digits", so all evaluated ranges needs to contain exactly 5 numbers and everything else must be ignored.
Using
range(len(digits)-4)for traversal index means such a subset won't be included. Using justrange(len(digits))works in this particular example string due to the simple fact that the very last digit is zero (so the final products will all be 0).Even simpler than that
There's actually no need for special cases... the product of a subset of five digits can't be more than that of the five.
Functional solution in clojure
where *test-string* is the number as a string.
Second strategy in Python short-form
Your second strategy in Python, 2 lines. Line 1 prepares the list of ints, line 2 walks it making a product of each number and 4 following numbers into a new list and prints the max() resulting value).
>>> d = [int(c) for c in '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450']
>>> print(max([d[i]*d[i+1]*d[i+2]*d[i+3]*d[i+4] for i in range(len(d)-4)]))
40824
Perl attempt
Here's a really simple Perl attempt to solve this problem. I just went with the most obvious implementation:
Hey Michael, Thanks for the
Hey Michael,
Thanks for the Perl submission, now I don't have to write one up myself. ;)