Geeks With Blogs
Mark Pearl

 

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)     

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.

Posted on Saturday, July 24, 2010 8:34 AM F# | Back to top


Comments on this post: F# – Euler Problem 8

# re: F# – Euler Problem 8
Requesting Gravatar...
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

Your comment:
 (will show your gravatar)


Copyright © MarkPearl | Powered by: GeeksWithBlogs.net