euler !! 4


For this problem we're going to string together the longest chain of functions we've seen yet. Don't be intimidated though, it's pretty straightforward.

Problem 8:
Find the greatest product of five consecutive digits in the 1000-digit number: 73167176531330624919225119674426574742355349194934...

Our strategy is this: make a list that contains the digits of this number. Then make four more copies of this list, each missing the head of the previous list. Then multiply all the lists together and take the maximum result as our answer.
If that's a bit confusing, no worries. It will make more sense when we go through an example.
First though, we need a way of creating a list of digits out of one big number. To do this, we first convert the number to a string using show. Since a string is just a list of chars, we can then map read onto each value to change it back to an int.

digits n = map convertToInt $ show n where
    convertToInt x = read [x] :: Int

That new syntax after read just signifies that we are casting the char to an int, and not something else.
There is a better way to write this function, however. Instead of making a separate convertToInt function, we can use a lambda instead. A lambda is an unnamed (anonymous) function that we can use once and then forget about. To declare a lambda we use \, since it kinda looks like a lambda (some Haskell IDEs actually replace the \ with a λ).

digits n = map (\x -> read [x] :: Int) $ show n

As you can see, it's almost identical to the function definition before, except that we replaced the = with ->.
Lambdas are so cool that there's actually an entire domain of mathematics called Lambda Calculus that deals with them. If that sort of thing interests you, there's a good primer here.
Anyway, now we can actually implement our algorithm. We'll start by introducing a new function, iterate, that creates an infinite list by repeatedly applying a function to its argument. For example, if your function was (+2) and your argument was 1, iterate would generate the infinite list [1,3..]. Here, our function of choice is tail. Thus, if our number was 123456789, our new list would be:

[123456789,
  23456789,
   3456789,
    456789,
       ...]

(Okay, technically the result is a list of lists, with each list containing one digit per element, but you get the idea). Of course, in this case the list is not infinite, since eventually the list will be empty; asking for any subsequent values will cause an error, since the tail of an empty list is undefined. Fortunately, we only need the first five results, and Haskell's lazy nature allows us to avoid the error:

take 5 . iterate tail . digits number

Now, we just need to multiply the resulting lists together. This can be accomplished using a fold and zipWith. zipWith lets us multiply together the corresponding indices of two lists, and foldr1 (or foldl1) lets us apply this to operation to all five lists. Here's a nice visualization:

  1,2,3,4,5,6,7,8,9 -> 2,6,12,20,30,42,56,72 -> 6,24,60,120,210,336,504 ...
* 2,3,4,5,6,7,8,9    * 3,4, 5, 6, 7, 8, 9     * 4, 5, 6,  7,  8,  9
  3,4,5,6,7,8,9        4,5, 6, 7, 8, 9          5, 6, 7,  8,  9
  4,5,6,7,8,9          5,6, 7, 8, 9
  5,6,7,8,9

Highlighted in yellow are all the possible sequences that we could multiply together (you should read it vertically, although it also works horizontally in this case). The other numbers are dropped because zipWith truncates the result to match the shorter list.
We can then simply apply maximum to obtain our final result:

problem8 = maximum . foldr1 (zipWith (*)) $ take 5 . iterate tail . digits $ number where
    number = 73167176531330624919225119674426...

That's a lot of composition! The trick is to just read it right to left and think about what the intermediate results will look like.

Leave a Reply

Theme: Esquire by Matthew Buchanan.