Beat 99.95% of submitted solutions for Merge Two Sorted Linked Lists

Yes, I did it again. Simple enough.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        head=None
        cur=None
        while l1 is not None or l2 is not None:
            if head is None:
                if  l1 is not None and l2 is not None and l1.val<l2.val:
                    head=l1
                    l1=l1.next
                    cur=head
                elif l1 is not None and l2 is not None and l1.val>l2.val:
                    head=l2
                    l2=l2.next
                    cur=head
                elif l1 is None and l2 is not None:
                    head=l2
                    l2=l2.next
                    cur=head
                else:
                    head=l1
                    l1=l1.next
                    cur=head
            elif l1 is not None and l2 is not None and l1.val<l2.val:
                cur.next=l1
                l1=l1.next
                cur=cur.next
            elif  l1 is not None and l2 is not None and l1.val>l2.val:
                cur.next=l2
                l2=l2.next
                cur=cur.next
            elif  l1 is None and l2 is not None:
                cur.next=l2
                l2=l2.next
                cur=cur.next
            else:
                cur.next=l1
                l1=l1.next
                cur=cur.next
        return head

                
                
                

Beat 95.56% of python submissions

Good result. I'm happy.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        count=0
        tmp=list()
        cur=head
        while cur is not None:
            # if count>n:
            #     break
            tmp.append(cur)
            cur=cur.next
            count+=1

        if count==1 and n==1:
            return None
        
        if n==1:
            tmp[len(tmp)-n-1].next=None
            return head
        
        if n==len(tmp):
            head=None
            head=tmp[1]
            return head
        
        if n>0:
            tmp[len(tmp)-n-1].next=tmp[len(tmp)-n+1]
            return head

    

if __name__ =='__main__':
    s=Solution()
    class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None
            self.head=self
        
        def add_to_the_end(self, val):
            cur=self.head
            while cur.next is not None:
                cur=cur.next
            cur.next=ListNode(val)
           
            
            
        
        def printLinkedList(self):
            cur =self.head
            while cur is not None:
                print (cur.val)
                cur=cur.next 
            
    ln=ListNode(1)
    ln.add_to_the_end(2)
    ln.add_to_the_end(3)
    ln.add_to_the_end(4)
    ln.add_to_the_end(5)
    s.removeNthFromEnd(ln,5)
    ln.printLinkedList()

        

Beat 100% of python3 submissions

Yes! I did it.

Here is simple code that  gives me  performance  described on picture above.

class powxy:
    def pow(self, x, n):
        if n == 0.0:
            return 1
        if n < 0:
            n = -n
            x = 1/x
        if n % 2 == 0:
            return self.pow(x*x, int(n/2))
        return x*self.pow(x*x, int(n/2))

How to use virtual invironment in python 3.6

A Virtual Environment, allows to create an isolated working copy of Python. It is quite common situation  when Python applications  use packages  that  are not part of the standard library. It happens that  multiple applications may require different version of the same library. In other words- single installation of  Python  will not be able to serve  all the possible requirements  for   applications. This issue  can be solved by utilizing  Virtual environments. Virtual environment is directory that contains  all the Python installation  and all the required  packages.  Different Python application may use  dedicated  virtual environments.

Starting Python 3.6  -  virtual environment  creation module shipped  as part of Python installation.

Here is example - how to create virtual environment using Python 3.6

python -m venv env

This command creates new forlder "env" in current directory (if directory not yet exists). It also create subdirectories in "env" directory that   containing a copy of the Python interpreter, the standard library,  supporting files, etc.

After  virtual environment is created- it needs to be activated:
Depend on  OS type- it can be done in several ways.

For Windows:

.\env\Scripts\activate.bat

For Linux:

./env/Scripts/activate.sh

After  virtual environment is activated-  shell will show  activated virtual  environment as a prefix in command prompt: (venv).

Now we can install  all the required libraries for our current  Python application.
For example:

python -m pip install beautifulsoup4

python -m pip install lxml

All the installed packages  will be stored inside of "venv" folder  and not overlap/affect any other Python  applications.
v

Vertx: How to write log file using JavaScript

For those who  are not familiar with Vertx- its tool-kit for building reactive applications on the JVM.
It make sense to start with introduction  to Vertx, but  it's already done by many other  guys in internet. I'll share here   few  code snippets that I wrote  using Vertx in JavaScript.
I would like to admit one important  thing: Vertx runs on JVM- which means- we can get access to entire Java ecosystem from any language that supported by Vertx.
Now let's  get back to our main topic: how to write log file  using Vertx in JavaScript?
Here is code snippet of mylog.js:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

var fw = null;//log file handler var logFile=null; var $logEnabled=null; var $logPath=null; var $maxLogFileSize=null; //create Text file using java.io.FileWriter and java.io.File this.createLogFile =function(){ var FileWriter=Java.type("java.io.FileWriter"); fw = new FileWriter($logPath); var File= Java.type("java.io.File"); logFile=new File($logPath); } function closeLogFile(){ fw.close(); } //write to log file function append(msg){ var curDate=new Date(); msg=curDate+':'+msg; var fileSize=logFile.length(); console.log('file size='+fileSize); if(fileSize>$maxLogFileSize){ //rotation for log file based on size value console.log('rewrite file from scratch'); closeLogFile();//close file createLogFileHandler()//recreate file fw.write(msg); fw.write("\n"); } else { fw.append(msg); fw.append("\n"); } fw.flush(); } //set initial values to variables this.construct= function(){ $logEnabled=true; $logPath="/var/tmp/test.log"; $maxLogFileSize=1000000; } //public method available from main program this.log=function(msg){ msg=msg.toString()+'\n '; if($logEnabled){ if($logPath!==null){ appendToExistingLogFile(msg); } else console.log("log file path is not defined- unable to write into file"); } else console.log(msg); }

We have to include mylog.js file in main application to start using it.

1 2 3 4 5 6 7

require("mylog.js"); construct(); createLogFile(); log("Hello world");

Pretty simple.

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));

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.

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.