Project Euler: Problem 8

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

  1. #!/usr/bin/python3
  2. """
  3. code solution for Euler Project #8
  4. """
  5. import operator
  6. from functools import reduce
  7.  
  8. if __name__ == "__main__":
  9. index = 0
  10. high_score = 0
  11. investigate_this = 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450
  12.  
  13.  
  14. digit_list = [int(x) for x in str(investigate_this)]
  15. digit_list_length = len(digit_list)
  16.  
  17. while index < digit_list_length:
  18. if index == 0:
  19. temp_product = reduce(operator.mul, digit_list[index: index +5])
  20. elif index == 1:
  21. temp_product = reduce(operator.mul, digit_list[index - 1: index + 4])
  22. elif index == digit_list_length - 1:
  23. temp_product = reduce(operator.mul, digit_list[index - 4: index + 1])
  24. elif index == digit_list_length - 2:
  25. temp_product = reduce(operator.mul, digit_list[index - 3: index + 2])
  26. else:
  27. temp_product = reduce(operator.mul, digit_list[index -2 : index + 3])
  28.  
  29. if temp_product > high_score:
  30. high_score = temp_product
  31.  
  32. index += 1
  33.  
  34. 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

  1. module Main where
  2.  
  3. import Data.Char
  4.  
  5. investigate_this = map digitToInt $ show 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450
  6.  
  7. investigate_length = length investigate_this
  8.  
  9. productof5 index
  10. | index >= investigate_length - 4 = []
  11. | otherwise = prod5 : productof5 (index + 1)
  12. where prod5 = product [ investigate_this !! y | y <- [index..(index + 4)]]
  13.  
  14. main :: IO()
  15. main = print . maximum $ productof5 0

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.

  1. index = 0
  2. largest = 0
  3. long_number = """73167176531330624919225119674426574742355349194934
  4. 96983520312774506326239578318016984801869478851843
  5. 85861560789112949495459501737958331952853208805511
  6. 12540698747158523863050715693290963295227443043557
  7. 66896648950445244523161731856403098711121722383113
  8. 62229893423380308135336276614282806444486645238749
  9. 30358907296290491560440772390713810515859307960866
  10. 70172427121883998797908792274921901699720888093776
  11. 65727333001053367881220235421809751254540594752243
  12. 52584907711670556013604839586446706324415722155397
  13. 53697817977846174064955149290862569321978468622482
  14. 83972241375657056057490261407972968652414535100474
  15. 82166370484403199890008895243450658541227588666881
  16. 16427171479924442928230863465674813919123162824586
  17. 17866458359124566529476545682848912883142607690042
  18. 24219022671055626321111109370544217506941658960408
  19. 07198403850962455444362981230987879927244284909188
  20. 84580156166097919133875499200524063689912560717606
  21. 05886116467109405077541002256983155200055935729725
  22. 71636269561882670428252483600823257530420752963450""".replace("\n", "")
  23.  
  24. while index + 4 < len(long_number):
  25. product = 1
  26. section = long_number[index:index + 5]
  27. for i in section:
  28. product *= int(i)
  29. if product > largest:
  30. largest = product
  31. index += 1
  32.  
  33. print "answer: ", largest

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:

  1. fix = [int(x) for x in long_number]
  2.  
  3. while index + 4 < len(fix):
  4. product = 1
  5. section = fix[index:index + 5]
  6. for i in section:
  7. product *= i
  8. if product > largest:
  9. largest = product
  10. index += 1

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 :

  1. main = do str <- readFile "pb8_data.txt"
  2. let digits = map ((read::String->Int) . (\c -> [c])) $ concat $ lines str
  3. print $ maximum $ foldr (zipWith (*)) (repeat 1) $ take 5 $ iterate tail digits

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

  1. #!/usr/bin/perl
  2. use strict;
  3. use warnings;
  4. use feature 'say';
  5. use syntax 'gather';
  6. use List::Util qw(max reduce);
  7.  
  8. say max gather {
  9. my @nums;
  10. while (<DATA>) {
  11. while (/(\d)/g) {
  12. push @nums, $1;
  13. shift @nums if @nums > 5;
  14. take reduce { $a * $b } @nums if @nums == 5;
  15. }
  16. }
  17. }
  18.  
  19. __DATA__
  20. 73167176531330624919225119674426574742355349194934
  21. ...

ObfuPerl

Micheal Peters went with the obvious perl implementation. That leaves the least obvious implementation:

  1. use List::Util qw(max);
  2.  
  3. my $max = 0;
  4. $input =~ /(.)(.)(.)(.)(.)(?{ $max = max( $max, $1 * $2 * $3 * $4 * $5) })(*FAIL)/;
  5.  
  6. say $max;

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:

  1. use List::Util qw(max reduce);
  2.  
  3. my $max = 0;
  4. multimatch { $max = max( $max, reduce { $a * $b } @_ ) } qr/(.)(.)(.)(.)(.)/, $input;
  5. say $max;

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

  1. seq = '''73167176531330624919225119674426574742355349194934
  2. 96983520312774506326239578318016984801869478851843
  3. 85861560789112949495459501737958331952853208805511
  4. 12540698747158523863050715693290963295227443043557
  5. 66896648950445244523161731856403098711121722383113
  6. 62229893423380308135336276614282806444486645238749
  7. 30358907296290491560440772390713810515859307960866
  8. 70172427121883998797908792274921901699720888093776
  9. 65727333001053367881220235421809751254540594752243
  10. 52584907711670556013604839586446706324415722155397
  11. 53697817977846174064955149290862569321978468622482
  12. 83972241375657056057490261407972968652414535100474
  13. 82166370484403199890008895243450658541227588666881
  14. 16427171479924442928230863465674813919123162824586
  15. 17866458359124566529476545682848912883142607690042
  16. 24219022671055626321111109370544217506941658960408
  17. 07198403850962455444362981230987879927244284909188
  18. 84580156166097919133875499200524063689912560717606
  19. 05886116467109405077541002256983155200055935729725
  20. 71636269561882670428252483600823257530420752963450
  21. '''.split('\n')[:-1]
  22.  
  23. seq = [ int(x) for x in list(''.join(seq))]
  24.  
  25. products = [ reduce( lambda a,b: a*b, seq[i:i+5]) for i in range(0,len(seq)-4)]
  26. print max(products)

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.

  1. module Main where
  2.  
  3. import Data.Char
  4. import Data.List
  5.  
  6. investigateThis :: [Int]
  7. investigateThis = map digitToInt $ show 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450
  8.  
  9. largestProductOfN :: (Num a, Ord a) => Int -> [a] -> a
  10. largestProductOfN n = maximum . map (product .take n) . tails
  11.  
  12. main :: IO()
  13. main = print $ largestProductOfN 5 investigateThis

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.

  1. from collections import deque
  2. from operator import mul
  3.  
  4. #your code for getting the integer list
  5. deq = deque([], 5)
  6. m = None
  7.  
  8. for num in digit_list:
  9. deq.append(num)
  10. m= max(reduce(mul, deq), m)

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 just range(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.

  1. import operator
  2. x = [int(c) for c in string_of_1000_digits]
  3. print max(reduce(operator.mul, x[n:n+5]) for n in range(len(x)))

Functional solution in clojure

  1. (defn euler008 [s]
  2. (apply max (map (partial reduce *)
  3. (partition 5 1 (map #(Character/getNumericValue %) s)))))
  4.  
  5. (time (println (euler008 *test-string*)))

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:

  1. #!/usr/bin/perl
  2.  
  3. my $input =
  4. "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
  5.  
  6. my $length = length $input;
  7. my $max = 0;
  8. for my $i (0 .. $length) {
  9. if ($i <= ($length - 5)) {
  10. my $product = substr($input, $i, 1);
  11. next if $product == 0;
  12. $product *= substr($input, $i+$_, 1) for (1 .. 4);
  13. $max = $product if $product > $max;
  14. }
  15. }
  16.  
  17. print "$max\n";

Hey Michael, Thanks for the

Hey Michael,

Thanks for the Perl submission, now I don't have to write one up myself. ;)

If you made it this far down into the article, hopefully you liked it enough to share it with your friends. Thanks if you do, I appreciate it.

Bookmark and Share