Project Euler - Problem 4 in F#

Largest palindrome product

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.
Find the largest palindrome made from the product of two 3-digit numbers.

For this problem, we need to iterate through all the 3 digits number and get there products. Here is the solutions

    // function to flip the existing number to reverse the digits 
    let reverseNumber n =
        // recurring function to create new number to flip the 
        // existing the number digit one at a time
        let rec loop newNum = function
            // if the new number is 0
            // return the new created number as it is
            |0 -> newNum
            // if number is not 0
            // recall the function with new number * 10 and adding modules 
            // of number dividing by 10.
            // return update old number by dividing by 10 
            |x -> loop (newNum * 10 + x % 10) (x/10)    
        loop 0 n

    // check if the number is palindrome
    let isPalindrome = function
        // if number is equal to reversed number then its palindrome, 
        // return true
        | x  when x = reverseNumber x -> true
        // else return false
        | _ -> false

    // function to get the max palindrome number of multiplication
    // of two numbers between the limits
    let maxPalindromeNumber lowerLimit upperLimit =
        // create the seq of all the palidrome numbers create 
        // by multiple two numbers between the limits
        let numbers = seq {
            // get first number from the loop
            for i = lowerLimit to upperLimit do
                // get the second number from the loop
                for j = lowerLimit to upperLimit do
                    // multiple both the numeber
                    let z = i * j
                    // and check if number is palindrome
                    if isPalindrome z then
                        // if yes, return the number to seq else 
                        // move back to new numbers in the loop
                        yield z
        }
        // return the max number from the seq
        Seq.max numbers

    // create diagnostics stopwatch
    let sw = System.Diagnostics.Stopwatch()
    // start the stopwatch
    sw.Start() 
    // call function to get max palindrome number product of two numbers 
    // between 100 and 900
    let number = maxPalindromeNumber 100 999
    // stop the stopwatch
    sw.Stop()
    
    // print number
    printfn "multple of 3 digit resulting %d  - (with processing time %A)" number sw.ElapsedMilliseconds
 

Code is pretty self explanatory with comments. The avg time of the solution is 177ms

Please feel free to leave you feedback, whats good in the blogs and where i can improve.

Thanks and Happy CODING .... :)

Project Euler - Problem 3 in F#

Largest prime factor

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Here is my Solution #1

    

    (**********************************
    Solution 1 
    ***********************************
    slow solution as it iterates through all the numbers
    **********************************)

    let theNumber = 600851475143I //13195

    let rec LargestPrimeFactorial (x: bigint) (y:bigint) = 
        match x, y with
            | u, t when u = t -> u
            | c, d when c%d = 0I -> 
                match c with
                    | m when m = theNumber -> LargestPrimeFactorial (m/d) 2I
                    | n -> LargestPrimeFactorial theNumber ((theNumber/n)+1I)
            | e, f -> LargestPrimeFactorial e (f+1I)
            | a, b when a = b -> a
            | _, _ -> failwith "not valid option"

    let sw = System.Diagnostics.Stopwatch()
    sw.Start()  
    let primeFactorNo = LargestPrimeFactorial theNumber 2I
    sw.Stop()
    printfn "%A - (with processing time %A)" primeFactorNo  sw.ElapsedMilliseconds

In this solution, i try to iterates through all the numbers which is not so great solution for the huge numbers.
LargestPrimeFactorial takes two parameters, one the number we are finding factorial for and second number we are checking is divisor or not. Here are match condition checks

• | u, t when u = t -> u: If both the numbers are same then, return the prime number
• | c, d when c%d = 0I -> : If second number is factor of first number, then we try to find the factors for the divisor to check if that's a prime number or not. we call the same function with different parameters to find is its a prime number or not.
• | e, f -> LargestPrimeFactorial e (f+1I): If number is not divisor then recall the function with new incremented number to find the largest prime number divisor.
• | _, _ -> failwith "not valid option": If no condition is matched, fail with exception.

We this process is very slow. This is a basic logic to find the largest prime factor by dividing the number with each and every number to find all the factors and then check if the factorial number is prime number of not in the same manner. This logic on avg took 59590 ms.

Here is my Solution #2

    

    

    (**********************************
    Solution 2
    ***********************************
    Better solution to find all the divisors
    if n / x = y, obviously both x and y are factors, so I don't have to probe y anymore
    If I start probing from 2 going up, I can stop probing when I have reached \sqrt n. In fact, any number bigger than \sqrt n must have been already found probing a smaller number.
    Suppose for example that we have to factor the number 36 (one of the triangle number
    **********************************)

    let theNumber = 600851475143I //13195

    let divides (x:bigint) (y:bigint) = (x % y = 0I)

    let rec GetAllFactors (num:bigint) (index:bigint) factors = 
        if (divides num index) then
            let y = num / index
            if index < y then
                GetAllFactors num (index + 1I) (index::y::factors)
            else if (y = index) then
                (index::factors)
            else 
                factors
        else if index > bigint (sqrt (float num)) then
            factors
        else 
            GetAllFactors num (index + 1I) factors

    let rec PrimeNumber = function
        | [] -> 0
        | h::t -> 
            let factors = GetAllFactors h 2I []
            if(factors.Length = 0) then
                int h
            else 
                PrimeNumber t

    let rec LargestPrimeFactorial (x: bigint) = 
        let factorList = GetAllFactors x 2I []
        let factorRevList = factorList
                                |> List.sort 
                                |> List.rev

        let largestPrimeNumber = PrimeNumber factorRevList
        largestPrimeNumber        
    
    let sw = System.Diagnostics.Stopwatch()
    sw.Start()    
    let primeFactorNo = LargestPrimeFactorial theNumber
    sw.Stop()

In this solution, i have used better solution to find all the divisors. According to new formula, if n / x = y, obviously both x and y are factors, so I don't have to probe y anymore. If I start probing from 2 going up, I can stop probing when I have reached sqrt n. In fact, any number bigger than sqrt n must have been already found probing a smaller number. Here is the explanation of the written code

• GetAllFactors: Gets all the factors of a number in the array
• PrimeNumber: Checks if the number is prime or not
• LargestPrimeFactorial: Get the largest number from the factors list.

This logic on avg took 2900 ms.

Please feel free to leave feedback ... whats good in the post and where i can improve.

Thanks and happy coding

JavaScript Crash Course

Here is a small JavaScript crash course which i wrote while going thru one of JavaScript's online open courses. This PDf has been very helpful to quick refresh my Javascript fundamentals whenever needed.

Hope this will be helpful to you all too. Please click here to download this PDF file.

Angular Directive VS Service usage

Angular is built from ground up keeping separation of concern, modularity and testing in mind. One of the frequently asked question in AngularJS is where to use Directives and Services.

Directives 
Directives are a way to teach HTML new tricks. During DOM compilation directives are matched against the HTML and executed. This allows directives to register behavior, or transform the DOM - (angularjs.org/guide/directive)

As mentioned in the definition, Directives are strictly for the DOM manipulation only. Directives are genius way to make DOM more intelligent e.g. we can create a directive which creates new element with node name as "tab" which angular at run time which resolve as HTML. This gives HTML a new meaning by creating new reusable tags and also gives us one code place to explain what tag "tab" are and easy to maintain. 

Services
A service is any functionality which can be abstracted and then called by different functions e.g. $http, $routeProvider, etc. These services are needed to be injected in the controllers or other services using them to avoid direct reference to the functions. On injecting, these services are initialized and then can be used in the code without be directly object of the function. This is good code practice as we can mock the services for the test.

Ideally, directives should be strictly used for any UI view manipulation and services are abstracted functionalities which can be mocked for unit tests. Service should not be used for any DOM manipulation or event binding.

Project Euler - Problem 2 in F#

Even Fibonacci numbers

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Here is my solution

    // Create a mutable list, so that we can add elements 
    // (this corresponds to standard .NET 'List<T>' type)
    let l = new ResizeArray<_>([1;2])
 
    let rec fabonacci a b upperLimit = 
        match a, b with
            | _, _ when a + b <= upperLimit -> 
                let c = a + b
                l.Add(c)
                fabonacci b c upperLimit
            | _ -> l
 
    let sumOfEven =
        (fabonacci 1 2 4000000)
            |> List.ofSeq
            |> Seq.filter (fun x -> x % 2 = 0) 
            |> Seq.sum 

Since its dynamic seq we are creating which depends on the last two numbers, we need a mutable list which we can populate according to our need and logic. For Fibonacci, we need to have access to previous two numbers in the list to generate new one.

This solution is flexible too with the upper limit, so this logic can be used anywhere to create the Fibonacci sequence with any upper bound. First step is to create Fibonacci sequence with the upper bound and initial number to kick start the sequence.Once seq is created up to desired upper bound, we are left with filtering of the sequence for even numbers only and get their sum.

Please leave your feedback and happy coding. 

Project Euler - Problem 1 in F#

Multiples of 3 and 5

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

Here is my solution

    // Option 1
    let sumOfNoDivisbleBy3or5UnderN n = 
        [for i in 1 .. n-1 -> i]
            |> Seq.filter (fun x -> x%3 = 0 || x%5 = 0)
            |> Seq.sum
 
    let sumOfNoDivisbleBy3or5Under10 = sumOfNoDivisbleBy3or5UnderN 10
 
    let sumOfNoDivisbleBy3or5Under1000 = sumOfNoDivisbleBy3or5UnderN 1000
 
    printfn "The sum of all the multiples of 3 or 5 is %d" sumOfNoDivisbleBy3or5Under1000
 
    // Option 2
    let sumOfFilteredSeq filterCri n = 
        seq { for i in 1 .. n-1 -> if filterCri i then i else 0 }
            |> Seq.sum
 
    let filteredSeqOf3or5 = sumOfFilteredSeq (fun x -> x%3 = 0 || x%5 = 0)
 
    let sumOfNoUnder10 = filteredSeqOf3or5 10
 
    let sumOfNoUnder1000 = filteredSeqOf3or5 1000
 
    printfn "The sum of all the multiples of 3 or 5 is %d" sumOfNoUnder1000

Here i have specified two solutions. 

Options 1 is hard coded with the filter criteria and is only flexible  in changing the upper bound of the List where as option 2 is flexible in both upper bound as well as the filter criteria

Partial View Vs. Display/Editor Templates

ASP.net MVC provides two different options to create re-usable components

• Partial Views
• Display/Editor Templates

But whats the different between both of them and what advantage one has got over the other.

Difference between Display and Editor Templates: 

Display templates and Editor templates are model driven templates but only differ by the convention that display should only render read only html like divs, labels or spans etc where are editor should render editable html with forms, input controls, etc. Developers are the one whole create these templates and there is no validation which prevent us to create templates in the opposite order. It is the convention over configuration policy which drives MVC to follow a specific standardize pattern and sticking to this will ensure that no matter what you pass into Display helper method(s) will always render the same result as expected. Once we specify UIHint on any property, we instructor MVC view engine to render the respective property using given template specified either under DisplayTemplates folder or EditorTemplates folder under shared folder depending whether we want readonly mode (Html.Display) or editable mode (Html.Editor).

Sample ViewModel for the same to demonstrate how we ViewModel can be decorated with attributes to leverage templates rendering thru ViewModels in MVC

using System;

using System.Collections.Generic;
using System.Linq;
using System.Web;
using System.ComponentModel.DataAnnotations;
using ReferenceImplementation.ViewModels;
 
namespace ReferenceImplementation.ViewModels
{
    public class PersonViewModel
    {
        public string FirstName { get; set; }
 
        public string LastName { get; set; }
 
        [UIHint("Int")]
        public int Age { get; set; }
 
        [UIHint("Date")]
        public DatetimeViewModel DateOfBirth { get; set; }
 
        [UIHint("Phone")]
        public PhoneViewModel MobileNumber { get; set; }
    }
}

By specifying the UIHint attribute on properties in ViewModel, we are instructing MVC to render these properties with the respective templates (depending on its display or editor reference) from the respective folder instead of using standard MVC editor.

For the view code like the one given below

<div class="readonly">@Html.DisplayFor(m => m.DateOfBirth)</div>

Since we are using Display helper method, MVC will look for the Date template under DisplayTemplates folder and  for the view code given below

<div class="editale">@Html.EditorFor(m => m.Phone)</div>

MVC will look for template under EditorTemplates folder for the Editor helper method.

Difference between Partial View and Display/Editor Templates

By convention, Partial Views are considered to be View Centeric and MVC Templates are considered to be Model Centeric. This means that templates are more dependent on the view model and way they are rendered depends a lot on their properties but same is not true for the partial view as you are more concerned in choosing the correct partial view.

Partial View differs from Templates in the way they render Id's from the ViewModels. Partial view render the element name as it is but MVC Templates adhere to model hierarchies when rendering HTML helpers. e.g if you have a "Bar" object on your "Foo" model, the HTML elements for "Bar" will be rendered with "Foo.Bar.ElementName", whilst a partial will have "ElementName".

MVC Templates are more robust and smart. If you had a List<T> of something in your ViewModel, you could use @Html.DisplayFor(m => m.CollectionOfFoo), MVC templates are smart enough to see it as a collection and render out the single display for each item as opposed to a Partial, which would require an explicit for loop.

Templates are passed with additional information that partial views are not, in particular you receive ModelMetadata, such as that created by attributes. ModelMetadata are part of ViewData which is also accessible in partial view but are null as its only populated in templates ().

Note: Templates are partials which adhere to a specific convention. The situations which make templates better or worse than old partials are almost strictly dependent on whether or not the convention is worth adherence in your application