haskell: maximum product consecutive digits in a number

Question

I'm trying to write a function that finds the highest product of k consecutive digits of a given z number with n digits.

For example:

z = 1240313 -- number entered
n = 7 -- number of digits

k = 2 => 2*4 => 8 -- example if k = 2
k = 3 => 3*1*3 => 9
k = 4 => 0

If k > n I'm suppoused to get back an error.

My idea until now is to get all the digits one by one from the given number z and insert them on a list. Then I could probably work with this list but I don't know exactly how.

I managed to handle the error (I think) here is my code until now:

myList 0 = []
myList x = (x `mod` 10 : myList (x `div` 10))

myReverse x = reverse (myList x)

maxConProduct :: Integer -> Integer -> Integer
maxConProduct z k | k > length(myReverse) = error "more consecutive digits entered as required"

I'm new in Haskell and in the programming world. I would appreciate any help I can get on this matter.

Answer 1

TL;DR:

maximum . map product . takeWhile ((==n).length) . map (take n) . tails

Compose functions

You can do this very cleanly by composing functions:

import Data.List (tails)
import Data.Char (isDigit)

maxProd :: (Num a, Ord a) => Int -> [a] -> a
maxProd n = maximum                      -- biggest
          . map product                  -- product in the list
          . takeWhile ((== n) . length)  -- once the too-short ones have gone
          . map (take n)                 -- when you take the first n of each
          . tails                        -- of the tails of the original

Note that

((== n) . length) :: [a] -> Bool

first finds the length of the list, then gives True if that length matches n.

How does it work?

By way of illustration, let's track that through on your example. Notice how the tails have all lengths, but then when we map (take 3) it just keeps the first three of each. Also notice there are three lists that are too short ([1,3],[3],[]), so that's why we takeWhile ((==3).length).

ghci> tails $ [1,2,4,0,3,1,3]
[[1,2,4,0,3,1,3],[2,4,0,3,1,3],[4,0,3,1,3],[0,3,1,3],[3,1,3],[1,3],[3],[]]
ghci> map (take 3) . tails $ [1,2,4,0,3,1,3] 
[[1,2,4],[2,4,0],[4,0,3],[0,3,1],[3,1,3],[1,3],[3],[]]
ghci> takeWhile ((==3).length) . map (take 3) . tails $ [1,2,4,0,3,1,3]
[[1,2,4],[2,4,0],[4,0,3],[0,3,1],[3,1,3]]
ghci> map product . takeWhile ((==3).length) . map (take 3) . tails $ [1,2,4,0,3,1,3]
[8,0,0,0,9]
ghci> maximum . map product . takeWhile ((==3).length) . map (take 3) . tails $ [1,2,4,0,3,1,3]
9

Making it less unhelpful

Now this gives an error when n is more than the original list's length because the takeWhile will filter out all of the lists, and you'll be taking the maximum of an empty list, but it'll be more helpful with a clearer message. It's also handy to convert from a single Int:

digits :: Int -> [Int]
digits = map (read . (:"")) . show

That works by turning each character of the shown String into a String itself by putting it in front of the empty String with (:""), then reading each. Originally I had it taking from a String, because I erroneously thought that's what you had. Never mind.

findMaxProd :: Int -> Int -> Int
findMaxProd n i
          | n > length (show i) = error "findMaxProd: product length exceeds number length"
          | otherwise = maxProd n . digits $ i

In action, that gives:

ghci> findMaxProd 10 1240313
*** Exception: findMaxProd: product length exceeds number length
ghci> findMaxProd 3 1240313
9

Answer 2

Another solution would be like this:

maxConProduct z k | k > length (myReverse z) = error "more consecutive digits entered as required"
maxConProduct z k = solve (myReverse z) [] k
  where solve :: (Num a, Ord a) => [a] -> [a] -> Int -> a
        solve [] acc _ = head $ reverse $ sort acc
        solve x'@(x:xs) acc k = if k > length x'
                                then solve [] acc k
                                else solve xs (product (take k x'):acc) k

Demo in ghci:

λ> maxConProduct 1240313 2
8
λ> maxConProduct 1240313 3
9
λ> maxConProduct 1240313 4
0
λ> maxConProduct 1240313 8
*** Exception: more consecutive digits entered as required

You can see in the solve function, that I'm taking product of all the first k numbers and accumulating them in the list acc. Once the input list is empty, then I just sort the acc and give out the highest element in it.

Answer 3

Try this:

maxProduct number k 
  | length (show number) < k = error "more consecutive digits entered as required"
  | otherwise = maxProductHelp (transform number) k
    where
      transform 0 = []
      transform number = mod number 10 : transform (div number 10) -- returns digits
      maxProductHelp digits k = maximum $ products digits k -- gets maximum
        where
          products d k -- returns a list of products of consecutive groups of length k 
            | length d < k = []
            | otherwise = (product $ take k d) : products (tail d) k

Your maxConProduct is implemented as maximum $ products digits k

Lets look at this solution:

• maxProduct calls maxProductHelp, with the number somehow changed.
• transform just returns the digits of the specified number.
• maxProductHelp now gets the maximum of a list that products returned.
• products returns a list of the product of consecutive sublists of length k.

The most important function is products which is relatively easy to understand:

Well we want products to return a list of products of k consecutive digits, so we just cons the product of k consecutive digits into the next product of k consecutive digits. If our list of remaining digits is shorter than our specified k then we return an empty list on which everything is consed back.

Here just a small example of products:

products [3,1,3,0,4,2,1] 3 = (product [3,1,3]) : products [1,3,0,4,2,1]
products [1,3,0,2,4,2,1] 3 = (product [1,3,0]) : products [3,0,4,2,1]
products [3,0,4,2,1] 3 = (product [3,0,4]) : products [0,4,2,1]
products [0,4,2,1] 3 = (product [0,4,2]]) : products [4,2,1]
products [4,2,1] 3 = (product [4,2,1]]) : products [2,1]
products [2,1] = []

This is all just a list:

9 : 0 : 0 : 0 : 8 : [] == [9,0,0,0,8]