Thursday, October 31, 2013

Project Euler. Longest Collatz sequence. Problem 14 solution in C++

Collatz conjecture it's open mathematical problem. Still not proved.
Here is rules for generating Collatz sequence:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Problem 14  contains  a question:Which starting number, under one million, produces the longest chain?
I decided to play with  C++  little bit and  utilize  CPU cores. So my solution written using  C++ and multithreading programming.


//============================================================================
// Name        : LongestCollatzSequence.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdlib>
#include <pthread.h>
#include <sys/time.h>
#include <ctime>

using namespace std;
long maxVal=0;
long actualNumber=0;

#define NUM_THREADS     5
#define LIMIT 1000000
pthread_mutex_t lock;

typedef unsigned long long timestamp_t;
static timestamp_t
    get_timestamp ()
    {
      struct timeval now;
      gettimeofday (&now, NULL);
      return  now.tv_usec + (timestamp_t)now.tv_sec * 1000000;
    }

long calcNCount(long n) {
    long result = n;
    if (result <= 1) return 1;
    if (result % 2 == 0) return 1+calcNCount(result/2);
    return 1+calcNCount(3*result+1);
}

void* DoJob(void* num){
 long result=calcNCount((long)num);
 pthread_mutex_lock(&lock);
 if(result>maxVal){
  maxVal=result;
  actualNumber=(long)num;
 }

 pthread_mutex_unlock(&lock);

 pthread_exit(NULL);
}

int main() {

 timestamp_t t0 = get_timestamp();
 if (pthread_mutex_init(&lock, NULL) != 0)
 {
  cout<<"\n mutex init failed\n";
  return 1;
 }
 pthread_t threads[NUM_THREADS];
 pthread_attr_t attr;
 void *status;
 int rc;

 // Initialize and set thread joinable
 pthread_attr_init(&attr);
 pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
 long i=1;

 while(i<LIMIT){
  int countThreads=0;
  for(int j=0; j < NUM_THREADS; j++ ){
   i++;
   if(i<LIMIT){

    rc = pthread_create(&threads[j], NULL, DoJob, (void *)i );
    if (rc){
     cout << "Error:unable to create thread," << rc << endl;
     exit(-1);
    }
    countThreads++;
   } else break;
  }

  for( int j=0; j < countThreads; j++ ){
        rc = pthread_join(threads[j], &status);
        if (rc){
           cout << "Error:unable to join," << rc << endl;
           exit(-1);
        }
     }
  //cout<<"processed:"<<i<<endl;
 }
 pthread_mutex_destroy(&lock);
 // free attribute and wait for the other threads
 pthread_attr_destroy(&attr);

 timestamp_t t1 = get_timestamp();
 double secs = (t1 - t0) / 1000000.0L;
 cout<<"time elapsed="<<secs<<endl;
 cout<<"result:"<<actualNumber<<endl;

    pthread_exit(NULL);
}

Current    NUM_THREADS= 5 T tried  different numbers of  threads- but 5 thread -  achieved best time result.
According to  lscpu I have 6 cores only, so I'm not really sure if I understood why  5 threads  calculate result  faster then 6 threads.

Project Euler. Problem 13. Large Sum Solution in C#

What a lovely pretty solution.


   BigInteger sum=0; 
   foreach(var line in File.ReadAllLines("data"))
    sum+=(BigInteger.Parse(line));
   Console.WriteLine(sum.ToString().Substring(0,10));



Saturday, October 26, 2013

Problem 12. Highly divisible triangular number implementation in C++

Hi,

today, I going to show  solution of one more problem from http://projecteuler.net.
What is triangular numbers? A triangular number or triangle number counts the objects that can form an equilateral triangle. Please refer Wikipedia for additional information.
In general, triangular number can be calculated using formula bellow


triangleNumber=n*(n+1)/2;

So here is rough  solution. It's working, but  it will take forever to complete. :)
Sure, you can use threads to improve performance, but it's not help you too much.


//============================================================================
// Name        : HighlyDivisibleTriangularNumber.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <sys/time.h>
#include <ctime>
#include<math.h>

using namespace std;





int coutDividers(const long num){
 int tmp=1;
for(long i=1; i<num; i++)
 if(num% i==0)tmp++;
return tmp++;
}

typedef unsigned long long timestamp_t;

static timestamp_t
   get_timestamp ()
   {
     struct timeval now;
     gettimeofday (&now, NULL);
     return  now.tv_usec + (timestamp_t)now.tv_sec * 1000000;
   }

int main() {
 timestamp_t t0 = get_timestamp();
 //n(n+1) /2
 int counter=1;
 long triangleNumber=1l;
 int dividers=0;
 while (dividers<=500){
  triangleNumber=counter*(counter+1)/2;
  dividers=coutDividers(triangleNumber);
  //cout<<triangleNumber<<"="<<dividers<<endl;
  counter++;
 }
 cout<<triangleNumber<<"="<<dividers<<endl;

 timestamp_t t1 = get_timestamp();
 double secs = (t1 - t0) / 1000000.0L;
  cout<<"time elased="<<secs<<endl;

 return 0;
}

We shouldn't calculate and count prime numbers for required number, we can simplify by using square root .


//============================================================================
// Name        : HighlyDivisibleTriangularNumber.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <sys/time.h>
#include <ctime>
#include<math.h>

using namespace std;



int coutDividers(const long num){
 int tmp=1;
for(long i=1; i<sqrt(num); i++)
 if(num% i==0)tmp++;
return (tmp++)*2;
}

typedef unsigned long long timestamp_t;

static timestamp_t
   get_timestamp ()
   {
     struct timeval now;
     gettimeofday (&now, NULL);
     return  now.tv_usec + (timestamp_t)now.tv_sec * 1000000;
   }





int main() {
 timestamp_t t0 = get_timestamp();
 //n(n+1) /2
 int counter=1;
 long triangleNumber=1l;
 int dividers=0;
 while (dividers<=500){
  triangleNumber=counter*(counter+1)/2;
  dividers=coutDividers(triangleNumber);
  //cout<<triangleNumber<<"="<<dividers<<endl;
  counter++;
 }
 cout<<triangleNumber<<"="<<dividers<<endl;

 timestamp_t t1 = get_timestamp();
 double secs = (t1 - t0) / 1000000.0L;
  cout<<"time elased="<<secs<<endl;

 return 0;
}

This solution works so fast, comparing to previous, brute force solution.


Less then 1 second- incredible performance.

How can we improve it even more?
Lets try to rewrite all this things using  thread.


//============================================================================
// Name        : HighlyDivisibleTriangularNumberMultithreaded.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdlib>
#include <pthread.h>
#include <unistd.h>
#include <sys/time.h>
#include <ctime>
#include<math.h>

using namespace std;

#define NUM_THREADS     6
pthread_mutex_t lock;
long searchResult=0l;
long searchDividers=0l;

typedef unsigned long long timestamp_t;
static timestamp_t
    get_timestamp ()
    {
      struct timeval now;
      gettimeofday (&now, NULL);
      return  now.tv_usec + (timestamp_t)now.tv_sec * 1000000;
    }

void* coutDividers(void* num){
 int tmp=1;
 long dest=(long)num;
for(long i=1; i<sqrt(dest); i++)
 if(dest% i==0)tmp++;

 pthread_mutex_lock(&lock);
  if(searchResult==0l){
   if(tmp*2>=500){
    searchResult=dest;
    searchDividers=tmp*2;
   }
  }
 pthread_mutex_unlock(&lock);


pthread_exit(NULL);
}


int main ()
{
  timestamp_t t0 = get_timestamp();
 if (pthread_mutex_init(&lock, NULL) != 0)
     {
         cout<<"\n mutex init failed\n";
         return 1;
     }
 int counter=1;
  long triangleNumber=1l;

  while (true){


   int rc;
   int i;
   pthread_t threads[NUM_THREADS];
   pthread_attr_t attr;
   void *status;

   // Initialize and set thread joinable
   pthread_attr_init(&attr);
   pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);

   for( i=0; i < NUM_THREADS; i++ ){
      triangleNumber=counter*(counter+1)/2;
      counter++;
      rc = pthread_create(&threads[i], NULL, coutDividers, (void *)triangleNumber );
      if (rc){
         cout << "Error:unable to create thread," << rc << endl;
         exit(-1);
      }
   }

   // free attribute and wait for the other threads
   pthread_attr_destroy(&attr);
   for( i=0; i < NUM_THREADS; i++ ){
      rc = pthread_join(threads[i], &status);
      if (rc){
         cout << "Error:unable to join," << rc << endl;
         exit(-1);
      }

   }

   pthread_mutex_lock(&lock);
     if(searchResult>0l){
      cout<<"searchResult="<<searchResult<<endl<<"searchDividers="<<searchDividers<<endl;
      timestamp_t t1 = get_timestamp();
         double secs = (t1 - t0) / 1000000.0L;
         cout<<"time elapsed="<<secs<<endl;

   pthread_exit(NULL);
      pthread_mutex_destroy(&lock);
      }
   pthread_mutex_unlock(&lock);

  }
     cout << "Main: program exiting." << endl;
     pthread_exit(NULL);
}

Because of a task solving time cost relative  small,  threads wouldn't help you  here.

In my case time execution even increased, because of a lot of  threads handling routines.
I've did several tests, and  result  still  not so good as without threads.

But anyway- its  a good experience.








Monday, October 21, 2013

Largest product in a grid algorithm implementation in C#

Hi,
A few days ago I started practicing in  problem solving. I've picked projecteuler for this purpose.
I think it would be great to share some interesting solutions in my blog.

Problem 11. Largest product in a grid
Nothing special, just a good example   to show you a complex "for" loop, nothing else.
So here is algorithm:

  • Do loop through matrix, for each cell
    • Calculate horizontal product and check if it's largest product for now
    • Calculate vertical product and check if it's largest product for now
    • Calculate Right diagonal and check if it's largest product for now
    • Calculate left diagonal and check if it's largest product for now



using System;

namespace LargestProductInGrid
{
 public class Solver
 {
  private int largestProduct=Int32.MinValue;
  private const int SIZE=20;
  private const int COUNT=4;
  private int[,] m=new int[SIZE,SIZE]
{{08, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91, 08},
{49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 04, 56, 62, 00},
{81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 03, 49, 13, 36, 65},
{52, 70, 95, 23, 04, 60, 11, 42, 69, 24, 68, 56, 01, 32, 56, 71, 37, 02, 36, 91},
{22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80},
{24, 47, 32, 60, 99, 03, 45, 02, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50},
{32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70},
{67, 26, 20, 68, 02, 62, 12, 20, 95, 63, 94, 39, 63, 08, 40, 91, 66, 49, 94, 21},
{24, 55, 58, 05, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
{21, 36, 23, 09, 75, 00, 76, 44, 20, 45, 35, 14, 00, 61, 33, 97, 34, 31, 33, 95},
{78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 03, 80, 04, 62, 16, 14, 09, 53, 56, 92},
{16, 39, 05, 42, 96, 35, 31, 47, 55, 58, 88, 24, 00, 17, 54, 24, 36, 29, 85, 57},
{86, 56, 00, 48, 35, 71, 89, 07, 05, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
{19, 80, 81, 68, 05, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 04, 89, 55, 40},
{04, 52, 08, 83, 97, 35, 99, 16, 07, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
{88, 36, 68, 87, 57, 62, 20, 72, 03, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
{04, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 08, 46, 29, 32, 40, 62, 76, 36},
{20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 04, 36, 16},
{20, 73, 35, 29, 78, 31, 90, 01, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 05, 54},
{01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48}};
  
  
  public Solver ()
  {
  }
  
  public int GetLargestProductInGrid()
  {
   int tmp=0;
   for(int i=0; i<SIZE; i++)
    for(int j=0; j<SIZE; j++)
    {
    tmp=this.HorizontalProduct(i,j);
    if(tmp>this.largestProduct)
     this.largestProduct=tmp;
    
    
    tmp=this.VerticalProduct(i,j);
    if(tmp>this.largestProduct)
     this.largestProduct=tmp;
    
    
    tmp=this.DiagonalRight(i,j);
    if(tmp>this.largestProduct)
     this.largestProduct=tmp;
    
    
    tmp=this.DiagonalLeft(i,j);
    if(tmp>this.largestProduct)
     this.largestProduct=tmp;
    
    
    }
   
   return this.largestProduct; 
  }
  
  private int HorizontalProduct(int i, int j)
  {
   int result=1;
   for(int k=i; (k<i+COUNT &&k<SIZE); k++)
    result=result*m[j,k];
   
   return result;
  }
  
  //[column, row]
  private int DiagonalRight(int i, int j)
  {
   int result=1;
   for (int n=i, k=j;  (n<i+COUNT &&n<SIZE && k<j+COUNT &&k<SIZE); n++, k++)
    result=result*m[n,k];
   return result;
  }
  
  //[column, row]
  private int DiagonalLeft(int i, int j)
  {
   int result=1;
   for (int n=i, k=j;  (n>i-COUNT &&n<SIZE && n>0 && k<j+COUNT &&k<SIZE); n--, k++)
    result=result*m[n,k];
   return result;
  }
  
  private int VerticalProduct(int i, int j)
  {
   int result=1;
   for(int k=i; (k<i+COUNT &&k<SIZE); k++)
    result=result*m[k,j];
   return result;
  }
 }
}


That's all, feel free  post your comments.





Sunday, October 20, 2013

Set Collection data structure implementation using C#

Hi,
today I'm going to show you how to implement own set collection type with some commonly associate algorithms
We will start by first learning what is set is? Next, I'll show you have it can be translated in class. After that I'll show four algorithms commonly associated with a sets
  • Union
  • Intersections
  • SetDifference
  • SymmetricDifference
At the end of the topic, I'll show you how to use it sample application.

Let's start from the defining what is Set is? -set is collection of objects. Any type of the object can be stored in the set, as long as object comparable
Let's looks some examples of Sets:
  • Neutrals={0}
  • Positives={1, 2, 3, 4.....}
  • Negative ={....,-4, -3, -2, -1}
  • Evens ={..., -4, -2, 0, 2, 4, …}
  • Odds={..., -3, -1, 1, 3, …}

Before we dive into individual methods, let's carefully look a class.



First- you can see this class is Generic class, and it take an argument “T” and we are make sure that T implements IComparable interface. This insure us that we can compare instance of “T” using compare method. We can also see, that class contains Ienumerable Interface, this will allow us to use this class in context as enumerable as needed. For example in foreach loop. Let start by looking class construction.

Since we are storing objects in the set, we need to have a place to put them. This could be any basic data structures. This time I chose Microsoft .Net List class. Of course it will be possible to use array instead of list. But doing so it will require adding logic to the class the is not relevant to Set class and will require additional time to showing.

private readonly List _items=new List();

So first we have empty constructor.

public Set (){ }

And we also have constructor that accepts IEnumerable, that allow us easy create a Sets from any IEnumerables such as from other sets.

  /// <summary>
  /// If the items already exists in the Set- exception will be thrown
  /// This is because our class doe not allow dublicate items
  /// </summary>
  /// <param name='item'>
  /// Item.
  /// </param>
  /// <exception cref='InvalidOperationException'>
  /// Is thrown when an operation cannot be performed.
  /// </exception>
  public void Add(T item)
  {
   if(this.Contains(item))
    throw new InvalidOperationException("Item already exists in Set");
   this._items.Add(item);
  }

We can also add several items using AddRange method


  public void AddRange(IEnumerable<T> items)
  {
   foreach(T item in items)
    this.Add(item);   
  }    


Just as important add adding items is removing them. My Set class will support single remove method. This will takes item to remove an return value that indicates if the item found and removed.


  public bool Remove(T item)
  {
   return this._items.Remove(item);
  }

I would to determine if the item already exists in the Set or to get the Cardinality of the set


  public int Count 
  {
   get
   {
    return this._items.Count;
   }
  }

  public bool Contains(T item)
  {
   return this._items.Contains(item);   
  }

The last non Set specific methods I going to show you  is Enumeration method


  #region IEnumerable[T] implementation
  public IEnumerator<T> GetEnumerator ()
  {
   return this._items.GetEnumerator();
  }
  #endregion

  #region IEnumerable implementation
  System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator ()
  {
   return this._items.GetEnumerator();
  }
  #endregion

The first Set algorithm I'm going to look at - is the Union algorithm. The Union algorithm compare two Sets and produce third Set all of the unique items in both Sets


  /// <summary>
  /// Union two Sets.
  /// <example>The union of {1,2,3} and {3,4,5} is {1,2,3,4,5}</example>
  /// </summary>
  /// <param name='other'>
  /// New Set, that contains unique itemsin both sets
  /// </param>
  public Set<T> Union(Set<T> other)
  {
   Set<T> result =new Set<T>(_items);
   result.AddRangeSkipDublicates(other._items);
   return resut;                             
  }

As you can see - a new method I'm using here- AddTRangeSkipDublicates. That's because, I don't want to throw exception if the item already present in the Set. This  method is for internal purpose only, that's mean it can be marked as private. The loginc of this method is quite simple:

  • We are loading all items from first Set
  • Do loop through second list 
  • on each item check if the item already exists in the Set.
  • If the item is not Exist- then  current item should be added to the result Set.

The second algorithm of Sets I'm going to  show you is -Intersection. Intersection algorithm  compare two Sets and produce third Set that contains all of the intersecting, or matching members of both Sets. 
Lets take  look an example



  /// <summary>
  /// Intersection of two Sets
  /// <example>The intersection of{1,2,3} and {2,3,4} is{2,3}</example>
  /// </summary>
  /// <param name='other'>
  /// Other.
  /// </param>
  public Set<T> Intersection(Set<T> other)
  {
   Set<T> result =new Set<T>();
   foreach(T item in this._items)
   {
    if(other._items.Contains(item))
     result.Add(item);
   }
   return result;
  }

The SetDifference algorithm is the third set algorithm I'm  going to  show you. Set difference works by taking two different sets and returning all of the items of first Set that not members of second Set.
Lets take a look an example


  /// <summary>
  /// Difference of two Sets
  /// <example>The Set Difference of {2,3,4} and {3,4,5} is {2}</example>
  /// </summary>
  /// <param name='other'>
  /// Other.
  /// </param>
  public Set<T> Difference(Set<T> other)
  {
   Set<T> result=new Set<T>(this._items);   
   foreach(T item in other._items)
    result.Remove(item);
   return result;
  }


The final Set algorithm I'm going to show you is Symmetric Difference algorithm.
The Symmetric Difference algorithm is similar to Difference algorithm now output set will include all of that exists in only one of two input sets. The Symmetric difference is the set difference of the intersection and union of the input sets. Lets take an example to make it more clear.


  /// <summary>
  /// Symmetrics difference.
  /// <example>The symmetric difference of {1,2,3} and {2,3,4} is {1,4}
  /// 1. Itersection={2,3}
  /// 2. Union={1,2,3,4}
  /// 3. SetDifference of {1,2,3,4} and {2,3} is {1,4}
  /// </example>
  /// </summary>
  /// <returns>
  /// The difference.
  /// </returns>
  /// <param name='other'>
  /// Other.
  /// </param>
  public Set<T> SymmetricDifference(Set<T> other)
  {
   Set<T> intersection=this.Intersection(other);
   Set<T> union=this.Union(other);
   return union.Difference(intersection);
  }

That's all.