Geeks With Blogs

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..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..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)

printfn "%d" (SeqNumbers |> Seq.max)```

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.

Related Posts on Geeks With Blogs Matching Categories

Comments on this post: F# – Euler Problem 8

# re: F# – Euler Problem 8 wanted to try the windowed function so came up with this:
let data = "7316717..."
let c = 5
// get to seq<int>
let intArray = data.ToCharArray() |> Seq.map (fun a -> (string >> int) <| a)

let highest =
Seq.windowed c intArray
|> Seq.map (fun (i:int[]) -> (i |> Seq.fold (fun acc x -> acc * x) 1 ))
|> Seq.max
printfn "%A" highest
Left by JD on Aug 14, 2010 3:11 AM