F# – Euler Problem 8

Today I had some more spare time to give Euler a go and thought I would try my luck on problem 8.

The Problem

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

The Solution

I decided to make my solution a bit more generic instead of limiting it to just five consecutive digits I made this user defined. Looking at the data, I could not see a way of halting halfway through parsing it unless I reached the maximum possible x digit number, and so decided not to even worry about this occurring – instead the reality was that I would need every number and have to find the max one.

The crux of the code is in the get portion section. Basically what I do here is with the Seq.unfold method I generate a sequence of just x numbers, and then refold those into the product using the accumulator.

/// /// Gets a portion of a string and returns the product of it /// let GetPortion (s:string, pos:int) = if (IsInRange(s, pos)) then
(s.Substring(pos),ConsNums) |> Seq.unfold(fun(x,y) -> match (y>0) with | true -> Some(x.[0].ToString() |> Convert.ToInt32, (x.Substring(1),y-1)) | false -> None) |> (Seq.fold(fun acc x -> acc*x) 1) else 0

Once I had this working, to make the actual generator was really simple. Using the Seq.unfold function again, I parse every valid element in the data until I fall outside the range, and generate a sequence. The I just return the max value.

// // Create a sequence of all the consecutive numbers // in the data of length ConsNums // let SeqNumbers = (data,0)
|> Seq.unfold(fun(x,y)-> match IsInRange(x,y) with | true -> Some(GetPortion(x,y),(x,y+1)) | false -> None)

The entire solution looks like this…

open System

let data = “73167176531330624919225119674426574742355349194934” + “96983520312774506326239578318016984801869478851843” + “85861560789112949495459501737958331952853208805511” + “12540698747158523863050715693290963295227443043557” + “66896648950445244523161731856403098711121722383113” + “62229893423380308135336276614282806444486645238749” + “30358907296290491560440772390713810515859307960866” + “70172427121883998797908792274921901699720888093776” + “65727333001053367881220235421809751254540594752243” + “52584907711670556013604839586446706324415722155397” + “53697817977846174064955149290862569321978468622482” + “83972241375657056057490261407972968652414535100474” + “82166370484403199890008895243450658541227588666881” + “16427171479924442928230863465674813919123162824586” + “17866458359124566529476545682848912883142607690042” + “24219022671055626321111109370544217506941658960408” + “07198403850962455444362981230987879927244284909188” + “84580156166097919133875499200524063689912560717606” + “05886116467109405077541002256983155200055935729725” + “71636269561882670428252483600823257530420752963450”

let ConsNums = 5 // The consecutive number

// // Returns true if the position is within the range of the string // let IsInRange (s:string, pos:int) = pos < s.Length-ConsNums

/// /// Gets a portion of a string and returns the product of it /// let GetPortion (s:string, pos:int) = if (IsInRange(s, pos)) then
(s.Substring(pos),ConsNums) |> Seq.unfold(fun(x,y) -> match (y>0) with | true -> Some(x.[0].ToString() |> Convert.ToInt32, (x.Substring(1),y-1)) | false -> None) |> (Seq.fold(fun acc x -> acc*x) 1) else 0

// // Create a sequence of all the consecutive numbers // in the data of length ConsNums // let SeqNumbers = (data,0)
|> Seq.unfold(fun(x,y)-> match IsInRange(x,y) with | true -> Some(GetPortion(x,y),(x,y+1)) | false -> None)

Nothing to fancy, I would be interested to see other approaches, or if I could phrase this code better – any feedback from the F# community would once again be much appreciated.