Geeks With Blogs
Mark Pearl

 

Well after a hectic week of work and studying I eventually had some me time… today I thought I would attempt Euler Problem 16.

The Problem

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 21000?

The Solution

So I thought I would get to concerned about length of code, but rather focus on implementing several practices that I have learnt in the last couple of weeks, namely tail recursive functions and composite functions…

I initially broke the solution up into two parts, a function that calculated the power and then a function that parsed that result and added the numbers together (sum them).

let PowerN n:bigint =
    let rec innerPowerN(n:bigint, act:bigint) =
        match n with
        | v when v<1I -> act
        | _ -> innerPowerN((n-1I), act*2I)
    innerPowerN (n, 1I)

When I came to summing the digits, I hit a bit of a road block, but then saw a nice implementation of Stack Overflow for converting a character to an value.

///
/// Converts a value to a bigint digit
///
let Value c =  
    let table = [ 
        '1', 1I ; '2', 2I ; '3', 3I
        '4', 4I ; '5', 5I ; '6', 6I 
        '7', 7I ; '8', 8I ; '9', 9I 
        '0', 0I ] 
    let dictionary = dict table 

    match dictionary.TryGetValue(c) with 
    | true, v -> v 
    | _ -> failwith (sprintf "letter '%c' was not in lookup table" c) 

//
// Sum all the digits in a bigint
//
let SumDigits(x:bigint) =            
    x.ToString().ToCharArray() |> Seq.sumBy Value

 

Finally using composite functions I put it all together…

let Euler16 = PowerN >> SumDigits

The entire code looked like the following…

///
/// Converts a value to a bigint digit
///
let Value c =  
    let table = [ 
        '1', 1I ; '2', 2I ; '3', 3I
        '4', 4I ; '5', 5I ; '6', 6I 
        '7', 7I ; '8', 8I ; '9', 9I 
        '0', 0I ] 
    let dictionary = dict table 

    match dictionary.TryGetValue(c) with 
    | true, v -> v 
    | _ -> failwith (sprintf "letter '%c' was not in lookup table" c) 

//
// Sum all the digits in a bigint
//
let SumDigits(x:bigint) =            
    x.ToString().ToCharArray() |> Seq.sumBy Value
        
let PowerN n:bigint =
    let rec innerPowerN(n:bigint, act:bigint) =
        match n with
        | v when v<1I -> act
        | _ -> innerPowerN((n-1I), act*2I)
    innerPowerN (n, 1I)

let Euler16 = PowerN >> SumDigits

 

While I am pretty sure there is a nicer way to implement “Value”, other than that I am pretty happy with the solution although I am sure this can be solved in a one liner as well…

Posted on Thursday, August 19, 2010 9:42 PM F# , Euler | Back to top


Comments on this post: F# Euler Problem 16

# re: F# Euler Problem 16
Requesting Gravatar...
I came up with this

let SumDigits(x:bigint) =
x.ToString().ToCharArray() |> Seq.fold ( fun acc e -> acc + System.Int32.Parse(e.ToString())) 0;;

Graham Hutton's paper on the expressiveness of folds causes me to use it constantly :)
I have not benchmarked the above so I don't know which is faster. Are you posting your solutions on a public repository as well?
Left by Nikhil Sarda on Sep 07, 2010 3:19 PM

# re: F# Euler Problem 16
Requesting Gravatar...
And here is the one-liner
(2I ** 1000).ToString().ToCharArray() |> Seq.fold ( fun acc e -> acc + System.Int32.Parse(e.ToString())) 0;;
Left by Nikhil Sarda on Sep 07, 2010 3:22 PM

Your comment:
 (will show your gravatar)


Copyright © MarkPearl | Powered by: GeeksWithBlogs.net