Project Euler - Problem 1 in C#

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

For this problem, either we can create list of int or array of int values up to 1000 like this

// generate the list of numbers from lower bound to upper down
private static IList<int> GenerateNumberList(int upperBound, int lowerBound = 0)
{
 var numberList = new List<int>();

 for (var i = lowerBound; i < upperBound; i++)
 {
  numberList.Add(i);
 }

 return numberList;
}

// generate the array of numbers from lower bound to upper down
private static int[] GenerateNumberArray(int upperBound, int lowerBound = 0)
{
 var arrLength = upperBound - lowerBound;

 var numberArr = new int[arrLength];

 for (var i = 0; i < arrLength; i++)
 {
  numberArr[i] = lowerBound + i;
 }

 return numberArr;
}

Using LINQ for the declarative approach to find the sum of all the numbers either divisible by 3 or 5

// OPTION 1
stopwatch.Start();

var listSum = GenerateNumberList(1000)
   .Where(x => x % 3 == 0 || x % 5 == 0)
   .Sum();

stopwatch.Stop();

Console.WriteLine (listSum);

// OPTION 2
stopwatch.Reset ();
stopwatch.Start ();

var arrSum = GenerateNumberArray (1000)
   .Where (x => x % 3 == 0 || x % 5 == 0)
   .Sum ();

stopwatch.Stop();

Console.WriteLine (arrSum);

With imperative way of programming without using LINQ, we can run the for loop from 0 to 1000 and keep adding all number which meet the criteria.

// OPTION 3
stopwatch.Reset ();
stopwatch.Start ();

var sum = 0;

for(var i = 0; i < 1000000; i++) {
 if (i % 3 == 0 || i % 5 == 0) {
  sum += i;
 }
}

stopwatch.Stop ();

Console.WriteLine (sum);

Click here to next problem

Have fun solving problems ...

What is AngularJS? ... And why AngularJS?

What is AngularJS?
AngularJS is a modern JavaScript framework to build SPA (Single-Page Applications). It is a hybrid of MVC (Model-View-Controller) and MVVM (Model View ViewModel) architecture. They (AngularJS team) sometimes proudly call themselves as MV* (Model View Whatever) framework. Before we go in depth about Angular, lets understand what is SPA?

What is SPA?
Single Page Application (aka SPA) is taking the web application world by the storm. The goal of the SPA is to provide user with a very responsive and user friendly UI interface.  These applications uses web page as a shell and content of the page is refreshed completely or partially without causing complete reload of the page. The three building blocks of the SPA are HTML, CSS and JavaScript on the client side and any server language of desire.

Challenges of creating SPA?
In SPA applications, updating the content of the page through AJAX calls and not reloading complete page causes its own issues. Here are the some of the issues

• JavaScript Heavy application: SPA application uses lot of JavaScript to manipulate HTML DOM on the client side. Normally all SPA are heavy client side applications. This means, writing lot of JavaScript. With the traditional way of writing JavaScript code, we (and not all of us) normally bind everything to the global namespace when we declare variables which can result lot of conflicts and hard to manage code as it is not modularized. Defects become hard to be traced at the compile time as all variables share the same namespace and might conflict with each other. With growing application, JavaScript code becomes bigger and harder to manage. 
• Lot of DOM manipulation: SPA heavily rely on JavaScript to manipulate DOM tree to update the content of the page. This brings its own challenges as jQuery has really made selecting and manipulating DOM tree very easy but failed to convey the message that probably the re painting HTML page is the most expensive task. Developer tend to read directly from the DOM tree and make changes back to it in the increments. This, probably is not the most efficient way of doing it as in one event, we might read and update the same element several times.
• Read and Update: JavaScript code is used to set the values in the HTML controls and save the changes back to server by reading back the values from the controls introduces lots of JavaScript code lines. In vanilla JavaScript there are always two or more lines of code associated with each HTML control for the same action and if the number of controls are more, it increases the JavaScript code making it harder to manage the code base.
• Testability: One of the easy way of managing code base is by dividing the code into small manageable modules by functionality and test it thoroughly. But it is difficult to unit test modules if they have any dependencies on any other modules. Since JavaScript by default does not support dependency injection and we use concrete objects, it means they should be up and running too. Also dependencies like AJAX calls are hard to mock. This causes lot of untested code in the main app. This also reduces our traceability with no way to track any changes in the code blocks. 
•  Browser Navigation: For SPA, AJAX calls are used to interact with the server, which does not trigger any URL change. This way user can change the main content of the HTML application using AJAX and pretend that next section is loaded with responsive behavior. But this causes issue as it breaks the traditional behavior of the browser navigation. Ajax calls don't update the URL history, so in attempt to go back to last page using browser navigation, this might take user to previous register page in browser history which might not what user is expecting. To over come this issue, "#" are used in the URL to depict URL change ( as any change in the URL after "#" does not trigger browser to reload the page. but it gets registered in the browser history) and design some pattern to make AJAX call on/with/after URL change. This is also know as deep linking, but to master deep linking and make it in all browser, its very difficult. Also hard to test all types of scenarios.

There are many good libraries which have changed the way applications are written using JavaScript like

• jQuery (famous for DOM manipulation)
• KnockOut (famous for MVVM pattern)
• RequireJS (famous for module loading and dependencies injection)
• etc 

which solves one particular problem of building web application in a excellent way but not as one framework. They all can be clubbed together to work with each other but they were not designed to do so. And there is always duplicate functionality b/w there libraries as they all try to go little extra mile to sell themselves.

Why AngularJS?
Like I described earlier, Angular is complete framework which takes care of all the features required for the development of the SPA application, plus its extendable. Here are the feature list

• Directives: In AngularJS terms, directives are making HTML smarter. Directives can be specified as tags, attributes or classes like ng-view, ng-repeact etc which makes HTML declarative. It also makes HTML code reusable. We can extend default set directives provided in core Angular for our application. During compile time, it looks for directive keys and executes the code to update the HTML as specified in the link function. This will update the specified HTML in template as required by the directive. This helps the keep the DOM manipulation separated from business rules.
• Supports DI: This is one of the biggest selling point of the AngularJS, supporting Dependency Injection. In Angular, we can create small modules aka services, which can be injected in the controllers, directives or other services. This allows us to mock the services during unit testing and test the actual unit of work without any dependency. By creating services, code can be reused in different modules and it does not interfere with the main business logic of the application.
• Supports MVC: Angular supports MVC pattern in the development of the application. We need to register controllers either in the config associated with the URL (which is appended after "#" in URL) or we can specify it in the HTML with supported attribute (called directives) i.e. "ng-controller". Controller is the place where we set the scope which is the view model angular uses to update the HTML template to create the view. By this approach we separate the business logic in the controller or service (which can be injected in the controller and then consumed) and DOM manipulation. Angular updates the view for us in the end with the final value of the object after all business rules implemented which avoids continuous redrawing caused by frequent changes.
• Supports Routing: AngularJS route module helps in browser navigation. It manages the deep linking for us. We can pull the values like id etc from the URL and use in our code.
• Testability: Since angular uses DI to inject different services in the controller to be used along the business logic, this approach helps us to keep the code mode testable as we can mock these services to test our business logic behavior. 

The best part of AngularJS is that all these feature are extendable based on our project requirements. We can choose which module to be used in the application. This helps us to keep the 3rd party code light weight and to only include pieces we need for development.

Happy coding ...

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.