Project Euler Q8 Largest product in a series - Why is my code wrong?

Question

The problem is (source)...

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

I have the following F#...

let largestProduct n (s : string) =
  [ for i in [0..(s.Length - n)] do yield s.[i..(i + n - 1)]]
  |> Seq.map (fun s -> s, s |> Seq.fold (fun p c -> p * (int (string c))) 1)
  |> Seq.maxBy snd

You pass the number of digits, and the 1000 digit number as a string. The first line produces a sequence of n-character strings, which are piped into the second line where the product of the digits is calculated. This is wrapped in a tuple with the n-character string, so I can see which set of n characters produced the highest product. The last line gets the maximum product.

If I run this as follows...

largestProduct 4 nStr

...where nStr is the 1000-digit number as a string, it produces the following...

("9989", 5832)

...which is correct. However, if I change the number to 13, to solve the actual problem, it gives me...

("9781797784617", 2091059712)

...which apparently is wrong.

Anyone any idea why my code doesn't work? I've tried it for various small values of n, and it looks like it's working there. I've also tried it on shorter strings, and it seems to work fine.

Answer 1

This exercise causes an Int32 to overflow. The arbitrary-length type bigint solves this for a generally sufficient range of inputs. For example:

let digitsToProduct inp =
    inp |> Seq.map (string >> bigint.Parse)
        |> Seq.fold (*) 1I

let largestProduct n : (seq<char> -> bigint) =
    Seq.windowed n >> Seq.map digitsToProduct >> Seq.max

Edit: note that largestProduct takes a second argument: a string (or any char sequence) of the 1000 digits.

What can be learned from this?

This is a fundamental kind of problem that is worth thinking about. As a rule of thumb, a function should be correct or fail, at least for reasonable inputs. I would argue that, in any context where a developer might make such mistakes, the answer to just use a 64-bit integer is borderline incorrect. After all, it will still fail silently on inputs that are too large.

If you want to use a 32-bit or 64-bit integer for such a function, validate your inputs!

For example, a rough validation could be:

// 32b version
if n > 9 then invalidArg "n" "number of digits too large for Int32."
// 64b version
if n > 19L then invalidArg "n" "number of digits too large for Int64."

This would cause your program to fail properly instead of silently producing nonsensical results.

Answer 2

As you've figured, using int64 solves the problem.

The way I read the assignment, you don't have to return the digits that cause the largest product; only the product itself is required. With that requirement, the implementation is easy:

let largestProduct n : (string -> int64) =
    Seq.map (string >> System.Int64.Parse)
    >> Seq.windowed n
    >> Seq.map (Array.fold (*) 1L)
    >> Seq.max

If you want the sequence of digits as well, that's also easy:

let largestProductAndTheDigitsThatProduceIt n : (string -> string * int64) =
    Seq.map (string >> System.Int64.Parse)
    >> Seq.windowed n
    >> Seq.map (fun is -> System.String.Concat is , Array.fold (*) 1L is)
    >> Seq.maxBy snd

FSI:

> largestProductAndTheDigitsThatProduceIt 4 nStr;;
val it : string * int64 = ("9989", 5832L)
> largestProductAndTheDigitsThatProduceIt 13 nStr;;
val it : string * int64 = ("5576689664895", 23514624000L)

Answer 3

Whilst searching for some inspiration, I came across a question where someone had the same problem.

The answer was nothing more complex than the fact that the multiplication overflowed the capacity of a 32-bit integer. When I altered the code to use int64, it gave the right answer...

let largestProductInt64 (n : int64) (s : string) =
  [ for i in [0L..((int64 s.Length) - n)] do yield s.[(int i)..int(i + n - 1L)]]
  |> Seq.map (fun s -> s, s |> Seq.fold (fun p c -> p * (int64 (int (string c)))) 1L)
  |> Seq.maxBy snd

Shame, as the code isn't as neat and clean, but it works.

Thanks to @kvb who made the same point in a comment before I had chance to post my own findings.