"Euler #8 : Largest Product"

by Nicolas Wu

Posted on 19 August 2010

Tags: Haskell, Euler

This week, our Project Euler puzzle is:

Discover the largest product of five consecutive digits in the 1000-digit number.

The number we’ve been given is 1000 digits long, so rather than writing this number as an Integer, it’s easier to express it as a string first (since the formatting looks better for this post), and to convert it to something more sensible afterwards.

To do that, we’ll be making use of an external module, called Data.Char, which exports a function, digitToInt, that converts between values of type Char and Int. Module imports in Haskell must come before function definitions, so we’ll put the import line right here:

> import Data.Char (digitToInt)
> import Data.List (tails)

Written as a string, the 1000 digit number we’ve been given is:

> num :: String
> num =
>   "73167176531330624919225119674426574742355349194934\
>   \96983520312774506326239578318016984801869478851843\
>   \85861560789112949495459501737958331952853208805511\
>   \12540698747158523863050715693290963295227443043557\
>   \66896648950445244523161731856403098711121722383113\
>   \62229893423380308135336276614282806444486645238749\
>   \30358907296290491560440772390713810515859307960866\
>   \70172427121883998797908792274921901699720888093776\
>   \65727333001053367881220235421809751254540594752243\
>   \52584907711670556013604839586446706324415722155397\
>   \53697817977846174064955149290862569321978468622482\
>   \83972241375657056057490261407972968652414535100474\
>   \82166370484403199890008895243450658541227588666881\
>   \16427171479924442928230863465674813919123162824586\
>   \17866458359124566529476545682848912883142607690042\
>   \24219022671055626321111109370544217506941658960408\
>   \07198403850962455444362981230987879927244284909188\
>   \84580156166097919133875499200524063689912560717606\
>   \05886116467109405077541002256983155200055935729725\
>   \71636269561882670428252483600823257530420752963450"

It really makes more sense to turn this little beast into a list of Int, rather than in its current form. We’ll do this by mapping the digitToInt function of Data.Char onto our list num:

> nums :: [Int]
> nums = map digitToInt num

Now that we have our list of integers, we can think about how we can find the product of all the sequences of consecutive digits that are 5 long.

Maybe, Just, Nothing

We’ll start by first extracting all the lists that are 5 digits long. To do this, we’ll define the function nibble, which takes a number n, and a list xs, and returns the first subsequence of xs of length n, paired up with the result of removing the first value in xs.

> nibble :: Int -> [a] -> Maybe ([a], [a])
> nibble n xs
>   | length xs < n = Nothing
>   | otherwise     = Just $ (take n xs, tail xs)

Since not every list xs has a length greater or equal to n, we use a Maybe type in conjunction with our returned pair of lists.

Values of type Maybe have the following defintion:

data Maybe a = Nothing | Just a

In other words, something of type Maybe is either Nothing, which contains no data, or Just a which contains a value of type a. In our case, the function returns Nothing when no list of length n can be extracted from xs, and otherwise returns the first list of length n, along with the nibbled rest of xs.

We can use nibble to define a function that produces all the subsets of xs that have length n. Basically, all we need is a case analysis on the result of nibbling xs. If no nibble can be taken, then we simply return the empty list. However, if a nibble can be taken, then we prepend the list ys of length n to the front of the result of nibbling zs:

> nibbles :: Int -> [a] -> [[a]]
> nibbles n xs = case nibble n xs of
>   Nothing       -> []
>   Just (ys, zs) -> ys : nibbles n zs

The solution for our problem then becomes relatively simple. First we produce all the lists of length 5, and apply the product function to each of those by using a map. We get our final result by applying the maximum function.

> euler8  = maximum . map product . nibbles 5 $ nums

Tails

Another way of obtaining the solution is to use the tails function, which returns all the suffixes of a list. The tails function is part of the Data.List module, which we imported at the beginning of this post. As an example of its use, let’s see what tails returns for the list [1..4]:

Prelude Data.List> tails [1..4]
[[1,2,3,4],[2,3,4],[3,4],[4],[]]

By using this function, we can build a different version of nibbles', where we take n elements from each of the sublists of the result of tails. Since the last n-1 elements of the list returned will have lengths shorter than n, so we reverse the list and drop those elements:

> nibbles' :: Int -> [a] -> [[a]]
> nibbles' n xs = drop n . reverse . map (take n) . tails $ xs

This function returns the reversed output of nibbles, which isn’t a problem in our case, since maximum is associative:

> euler8' = maximum . map product . nibbles' 5 $ nums

Summary

This week we’ve seen two rather different approaches to solving our problem, one using Maybe types, and another using tails.

• Maybe types capture the notion of a failed computation or an invalid result.
• Function composition can give us very succinct definitions (like in our nibbles' definition).

Comments