Project Euler - Problem 4 in C#

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.

Sounds like pretty simple problem ... right.

For all the three digit numbers, find the product between them and check if the product of numbers is palindrome or not. And if yes, find the greatest product.

Like explained in the problem, a palindrome is a word, phrase, or number, whose meaning may be interpreted the same way in either forward or reverse direction. To test a palindrome number, we need to reverse the digits of the number. And for that, we iterate using formula ((y*10) + (x%10)) where y is new reversed number starting from 0 and x is original number to be reversed. Here is the example below to understand it better

Iteration	Formula	New Number (y)	Actual Number (x)
0	0	0	98743
1	(0*10) + (98743%10)	3	9874
2	(3*10) + (9874%10)	34	987
3	(34*10) + (987%10)	347	98
4	(347*10) + (98%10)	3478	9
5	(3478*10) + (9%10)	34789	0

Method to reverse digits and test if number is palindrome or not ....

// Check is number is palindrome
public static bool IsPalindrome(this int number)
{
    // store the actual number for check
    var actualNumber = number;
    // initialize new palindrome number
    var palindromeNumber = 0;

    // to reverse the number e.g. 98743 and set new palindrome number to 0
    // multiple new palindrome number with 10, and add modulus when number is divide by 10 and set it back in the new number
    // iteration 1 -> newPalindromeNumber: (0*10 + 98743%10) -> 3; number -> 9874
    // iteration 2 -> newPalindromeNumber: (3*10 + 9874%10) -> 34; number -> 987
    // iteration 3 -> newPalindromeNumber: (34*10 + 987%10) -> 347; number -> 98
    // iteration 4 -> newPalindromeNumber: (347*10 + 98%10) -> 3478; number -> 9
    // iteration 5 -> newPalindromeNumber: (3478*10 + 9%10) -> 34789; number -> 0
    // loops till number is not equal to 0
    // and now we have reversed number to check if its palindrome
    while (number != 0)
    {
        palindromeNumber = (palindromeNumber * 10) + (number % 10);
        number = number / 10;
    }
    //if actual number and new expected palindrome numbers are same
    return (actualNumber == palindromeNumber);
}

Here is the first basic implementation to solve the problem

// basic looping
public static IEnumerable<int> ListOfThreeDigitNumbersProduct()
{
    // looping for the first 3 digit numbers
    for (var i = 999; i > 99; i--)
    {
        // looping for the second 3 digit numbers
        for (var j = 999; j > 99; j--)
        {
            // find the product b/w the numbers
            var product = i*j;

            // check if the number is palindome
            if (product.IsPalindrome())
            {
                yield return product;
            }
        }
    }
}

Whats happening in this solution

• Number x and y iterate from 100 to 999 to find product of x with all the 3 digits y number.
• Every product is verified for palindrome test and if successful, added to the list of palindrome products of 3 digit number
• Max number is picked from the list of palindrome numbers from the list.

var maxProduct = ListOfThreeDigitNumbersProduct().Max();

Note: We don't need to create the list of palindrome numbers.We can put conditions to always compare and get the largest palindrome number.

This solution works but there is room for improvement .... :) . Here are my observation for improvement for faster solution ...

• Product of x*y is equal to y*x. So we don't need check the product of x with y and again for x = y and y = x. This can be avoided by setting upper bound y to x.
• If the new product is greater then the previously stored palindrome number, only then we should run palindrome test on the current number. This way we can avoid palindrome test processing time on many numbers, hence making solution faster.

// intelligent faster solution
public static int LargestThreeDigitNumbersProduct()
{
    // initialize largest palindrome number variabel
    var largestPalindromeNumber = 0; 

    // loopping thru all 3 digit numbers
    for (var i = 999; i > 99; i--)
    {
        // PERFORMACE BOOST
        // looping thru 3 digits number from 100 to first number
        // anything greater then first number has been already calculated
        // as (a*b) = (b*a)
        for (var j = 100; j <= i; j++)
        {
            // product of nunmbers
            var product = i*j;

            // PERFORMACE BOOST
            // if current product is greated then the previous saved palindrome product
            // only then check for number is palindrome else we can avoid extra checking task
            if (product > largestPalindromeNumber) 
            {
                // check number is palindrome
                if (product.IsPalindrome())
                {
                    // if is palindrome, save it as largest palindrome number 
                    largestPalindromeNumber = product;
                }
            }
        }
    }

    return largestPalindromeNumber;
}

Link to Problem #3

If you have a better solution, please don't hide it from us .... share your knowledge ... :) .... till then, enjoy solving problems.

Project Euler - Problem 3 in C#

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 ?

To find the largest prime factor of a number x, we can do it in couple of ways. One way is the start dividing the number x by y = 2, 3, 4 ... For each factor y of x, this will remove all the smaller factors before moving to the next y till y is less then x. This will work but there is room for improvement over here.

Let improve this existing solution with some facts.

• 2 is the only even prime number, so we can eliminate all the even numbers by recursively dividing the number by 2. Then we can find the prime factor of new whole number faster by incrementing divisor by 2 starting from 3.
• If we don't find the prime factor of x until y (number we are testing to be prime factorial starting from 3) is less then equal to square root of x, means we have a tested all the possible options and no more factors are present. 

Here is the function to find the largest prime factor of a given number.

public static long LargestPrimeFactorByDividingBy2InLoopsInitially(long number)
{
    // set the initial dividing number
    long dividingNumber = 2;
    // looping to divide with only even prime number to remove all possible even numbers
    while (number % 2 == 0)
    {
        number = number / 2;
    }
    // no even number is left, hence starting with 3
    dividingNumber = 3;
    // divide in loops until dividing number is less then square root of expected lpf
    while (System.Math.Sqrt(number) > dividingNumber)
    {
        if (number % dividingNumber == 0)
        {
            // if expected lpf is divisible, update the number
            number = number / dividingNumber;
        }
        else
        {
            dividingNumber += 2;
        }
    }

    return number;
}

Link to Problem #2
Link to Problem #4

If you have any better and faster way, please share it with us. Till then, enjoy solving problems .....

Word of Experience

While working in the corporate sector, we face different set challenges everyday. They might not always related to our work but sometimes with our attitude towards our work (which might be intentionally or unintentionally).

DISCLAIMER:
I am very firm believer of doing things as if i won't do it, someone else will.

Experience:

Being too much technical is also problem sometimes. You start understanding all the business requirements/problems more by technical implementation (virtually creating solution in head at the very same instance) rather then understanding it as something user will like to have in a product which helps them to complete the task.
Recently we created a small app in my current engagement. It was almost complete (with couple of defects ... :) ). While trying to understand a defect, my manager came up with all together new requirement which potentially changes the complete or major portion of the JavaScript architecture. We developers (my colleague and myself) resisted back for that change in front of higher management. It was big change, potentially forcing us to go back to drawing board and redesign the whole thing again.

My intentions were good because we have completed our application and more over it was never part of the requirements. I was not afraid of the change but somehow resisted because timeline does not look good with release date. 

And soon it was time to have a word with my friend (who happens to be my manager too). He made me realize that changes are inevitable in the cycle of software development (which i knew) and may be what i was saying was right too, bring such big changes in the last minute was not a good idea too. But i was not conveying my message properly. All management could see was me trying to push back on the work and truly, that was not my intention. What i should have done was, tell them how big impact this is on the current architecture and time line required to revisit the design for new requirement. I will come out as a winner with positive attitude towards my work and also lay it down in front of management. And its their call to go ahead with change accepting new timeline, play gamble to push new changes in current timeline or put it in phase 2 of the application.

Lesson:

Its very important to understand our audience and talk in there language. Management does not care about technical issues we face while development. If business needs something, it needs it .... that's it. But what they care about is budget and are we on time for release or not. Its more important for we developers to play along and be flexible with new requirements. Always high light issues in positive attitude towards work, try to talk to management in their language, i.e. budget, time to finish task and let them take decision.

I know many of you guys already do this but this was high light of my week. And hope this helps some developer out there too ... 

Expected in C# 6.0

Mads Torgersen (Program Manager for Managed Languages) from the C# design team covered some of the new probable features in C# 6.0 in Build 2014 (Click here to view the video).

Lets drill down some of the highlighted features

Auto-Properties w/ Initializer:

Initializing a immutable class is a tedious process currently

Before

private int _x;
public int X { get { return _x; } }

public int Y { get; private set; }

With C# 6.0

public int X { get; } = _x;

public int Y { get; } = _y;

Thoughts

Instead of creating private members to set the value and return in getter or use private setter. We can initialize the property like this. Very useful for the immutable classes.

Primary Constructor:

Shorter and cleaner way to write constructor where we are just setting the values to the properties with private set without any extra validation.

Before

public class Person
{
    private string _name;

    public Person(string name, int age)
    {
        _name = name;
        Age = age;
    }

    public string Name { get { return _name; } }

    public int Age { get; private set; }

    .....
}

With C# 6.0

public class Person(string name, int age)
{
    public string Name { get; } = name;

    public int Age { get; } = age;

    .....
}

Thoughts

Combination of auto properties initializer and primary constructor will simplify C# code a lot.

Static using statement:

Now in C#6.0, we can include static classes in the scope.

Before

using System;
......
public double Distance { get { return Math.Sqrt(16); } }

With C# 6.0

using System.Math;
......
public double Distance { get { return Sqrt(16); } }

Thoughts

Nice to have feature. It can help in reducing lot of key strokes of including static class name again and again.

Property/Method Expression:

Property and method syntax simplified for short hand. Looks more like LINQ statement but has nothing to do with it.

Before

public double Distance { get { return Math.Sqrt(16); } }

public Point Move(int dx, int dy) 
{
    return new Point(x + dx, y + dy);
}

With C# 6.0

// Property expression
public double Distance => Math.Sqrt(16);

// Method expression
public Point Move(int dx, int dy) => new Point(x + dx, y + dy);

Thoughts

Nice to have feature.

Declaration Expression:

Instead of limiting variables to declaration statement, going forward we can declare them in the middle of the expression where they are need

Before

int val;

var isValid = int.TryParse ("1231", out val);

With C# 6.0

var isValid = int.TryParse ("1231", out var val);

Thoughts

Nice to have feature.

Params for Enumerable:

Now will be able to send params of enumerables instead of limiting to arrays.

Before

public void SomeMethod(params int[] vals) 
{
    .....
}

With C# 6.0

public void SomeMethod(params IEnumerable<int> vals) 
{
    .....
}

Thoughts

Again, nice to have feature. Will not have to convert enumerables into array anymore for the params.

Monadic null check:

Removes the need to check for nulls before accessing properties or methods. Known as the Safe Navigation Operator in Groovy).

Before

if (points != null) {
    var next = points.FirstOrDefault();
    if (next != null && next.X != null) return next.X;
}   
return -1;

With C# 6.0

var bestValue = points?.FirstOrDefault()?.X ?? -1;

Thoughts

Awesome. Will reduce lot of noise in the code.

Await Calls from Within a Catch Block:

With C# 6.0

try
{
    WebRequest webRequest =
        WebRequest.Create("http://IntelliTect.com");
    WebResponse response =
        await webRequest.GetResponseAsync();
    // ...
}
catch (WebException exception)
{
    await WriteErrorToLog(exception);
}

Thoughts

Have not used a lot. No Comments.

All these features look pretty interesting. Looking forward to C# 6.0

Happy Coding ...

Project Euler - Problem 2 in C#

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.

We have two options to solve this problem, declarative or imperative approach. Declarative approach has two steps

• Step 1: Generate the list of all the numbers in fibonacci series less then equal to 4 million

public static IEnumerable<int> GenerateList(int upperBound)
{
 if (upperBound < 2)
 {
  throw new Exception("Invalid upper bound");

 }

 IList<int> list = new List<int>();

 var prev1 = 1;
 list.Add(prev1);
 var prev2 = 2;
 list.Add(prev2);
 var sum = 0;

 while (sum < upperBound)
 {
  sum = prev1 + prev2;

  list.Add(sum);

                prev1 = prev2;
                prev2 = sum;
 }

 return list;
}

• Step 2: Sum all the even numbers in the list

// OPTION 1
var sum = GenerateList(4000000)
  .Where(x => x % 2 == 0)

  .Sum();

// By creating list first and reducing list to +ve numbers and finding their sum
Console.WriteLine(sum);

In the imperative approach, sum the even number while generating the fibonacci series in the loop itself.

// OPTION 2
var prev1 = 1;
var prev2 = 2;

// prev2 value is 2 which is a even number, so sum starts from 2
var sumByLooping = prev2;

while(prev2 <= 4000000) 

{
 var sumOf2Nos = prev1 + prev2;

 prev1 = prev2;
 prev2 = sumOf2Nos;

 if (sumOf2Nos % 2 == 0) 

 {
  sumByLooping += sumOf2Nos;
 }
}

// By looping thru numbers and adding only +ve numbers
Console.WriteLine(sumByLooping);

Link to Problem #1
Link to Problem #3

Have fun solving problems ....

What is Dependency Injection? And why it is so important?

Definition found on WIKI

Dependency injection is a software design pattern that implements inversion of control and allows a program design to follow the dependency inversion principle. The term was coined by Martin Fowler.

An injection is the passing of a dependency (a service) to a dependent object (a client). The service is made part of the client's state. Passing the service to the client, rather than allowing a client to build or find the service, is the fundamental requirement of the pattern.

Means: The dependency should be injected to a object which it needs to complete their unit of work. If object A needs object B to complete its unit of work, then B should be provided to A instead of A creating object B. This also means abstraction should not depend on details but instead details should depend on abstractions.

Let's drill down into this and try to make more sense out of this with examples.

NOTE: All my examples will be using C# language

Lets assume, in my application i need to send updates like email to user when a particular task is complete. So based on the requirement, i wrote a class which sends email messages to the users.

public class EmailNotifier
{
  public void Send(string message)
  {
   // code to send email to the user
  }
}

So in my code, i will be using email notifier to send email messages on complete of a task to respective users.

public class Task 
{
  // other methods for the task class

  public void OnComplete(string message)
  {
   // notify user with message
   var notifier = new EmailNotifier();
   notifier.Send(message);
  }
}

Now this is all good but we have couple of concerns over here.

Issue: Testing

Since my code has dependency on the external class, we have to make sure that its dependencies are always available, up and running for testing. Plus we cannot do unit testing of our unit of work as we will be testing notifier class and its dependencies too.

Solution:

Instead of creating the instance of the notifier class inside task object, we can pass the object as an parameter in the class. This is also known as Dependency Injection. Doing so, our code will not require to know how to build notifier object, and for testing we can pass the mocked object(s) which simulates different behavior to capture different scenarios.

public class Task 
 {
  EmailNotifier _emailNotifier;

  public Task(EmailNotifier emailNotifier)
  {
   _emailNotifier = emailNotifier;
  }

  // other methods for the task class

  public void OnComplete(string message)
  {
   // notify user with message
   _emailNotifier.Send(message);
  }
 }

With this solution, task class gets the notifier object injected as parameter. Task class is no longer responsible for creating the notifier object.

This is good but it can be still improved by making this loosely coupled. What exactly this means? To understand this, first we need to understand tight coupling.

Tight Coupling:

In computer science, tight coupling (or tightly coupled) is a type of coupling that describes a system in which hardware and software are not only linked together, but are also dependent upon each other. One of the common characteristics of tight coupling are

• A change in one module usually forces a ripple effect of changes in other modules.
• Assembly of modules might require more effort and/or time due to the increased inter-module dependency.
• A particular module might be harder to reuse and/or test because dependent modules must be included.

Loose Coupling:

In computing and systems design, a loosely coupled system is one in which each of its components has, or makes use of, little or no knowledge of the definitions of other separate components.

In the above code, even though we are injecting dependencies, still it is tightly coupled because it directly depends on concrete object. Any new requirement will cause ripple effect of changes e.g. if business comes up with new requirement of sending user notification via SMS, twitter, etc. To accommodate the new requirement, we can either change the base class to implement new notifications but that change will effect the way updates are sent where ever its being used for this service, which might not be the requirement. In another solution, we can inject all of the notification objects (like email, SMS etc) in the task class. Problem with this approach is that we will be creating instance of all notifiers even though we will be using few of them depending on requirement, we will clutter our code with if else statements and this is memory heavy too. It will work but again, its not the most desirable way of implementing a solution. Anytime new mode of notification is required, we have to change our code, including business logic.

Better solution would be to pass an abstraction/interface as a dependency. We can create a interface which describe how a Notifier class should look like. Then we will implement different ways of notifiers against this contract like this

 public interface INotifier
 {
  void Send(string message);
 }

 public class EmailNotifier : INotifier
 {
  public void Send(string message)
  {
   // code to send email to the user
  }
 }

 public class SmsNotifier : INotifier
 {
  public void Send(string message)
  {
   // code to send sms to the user
  }
 }

 public class EmailAndSmsNotifier : INotifier
 {
  public void Send(string message)
  {
   // code to send email and sms to the user
  }
 }

Now, instead of injecting concrete class, we can inject interface as dependency which promises methods or properties to be present in any class which implements it. This is how new task class will look like

public class Task 
 {
  INotifier _notifier;

  public Task(INotifier notifier)
  {
   _notifier = notifier;
  }

  // other methods for the task class

  public void OnComplete(string message)
  {
   // notify user with message
   _notifier.Send(message);
  }
 }

With new changes we can inject the different types of notifiers user want. In future, any new business need of notifications can been implemented without any major change in the code. We will need to create new class implementing the interface, test it as unit of work and inject it as dependency.
Now the bigger question is, how we inject these dependencies ...
One way is to create factory classes for resolving out dependencies but in any scenario, we will clutter our code with tight coupling.
Other solution is to use DI APIs. They are handy in registering and resolving interface/class types. Registration can been done at the application start. We can update the framework to use our DI object to resolve types in code.

Stayed tuned to my next article to learn more about how to use Unity, DI API in .net applications.

Till then, Happy coding ...

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