Regular Expression in Python: Greedy match

When you use re.findall(“(.*):” to get the strings ending with full-colon(:), you may not always get the expected result if your string has multiple full-colons. Lets run the command before we talk.

Concentrate on the commands put inside single colon. (You can neglect the rest as it is part of my effort to avoid creating a python file for running this code)

Screen Shot 2014-10-15 at 6.12.15 PMOutput:Screen Shot 2014-10-15 at 6.12.21 PM

What happened here is python did a greedy search and found maximum string ending with a full-colon. If that is what you desired, stop reading further.. 🙂

If you expected a list of all the strings ending with full-colon, change your command to re.findall(“(.*?):”

As you can see, I added a question mark which will force python to avoid greedy approach.

Before we part, lets make sure python is ok with this change..

 

Screen Shot 2014-10-15 at 6.11.40 PM

Output:

Screen Shot 2014-10-15 at 6.12.00 PMLOVE YOU PYTHON…

Find the biggest black square from an N*N matrix of black or white squares

Question:

Find the biggest black square from an N*N matrix of squares. 1 means it’s black, 0 means it’s white. Output should be the list of squares which forms the largest black square.

Input     : ‘{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#1#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}’

Output    :    {(3#0,3#1,3#2,3#3),(4#0,4#1,4#2,4#3),(5#0,5#1,5#2,5#3),(6#0,6#1,6#2,6#3)}

 

Solution(Python):

    # Author            :        Sreejith Sreekantan
    # Description        :        

    #                         Find the biggest black square from an N*N matrix of squares. 1 means it's black, 0 means it's white
    #                         Input     : '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#1#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
    #                         Output    :    {(3#0,3#1,3#2,3#3),(4#0,4#1,4#2,4#3),(5#0,5#1,5#2,5#3),(6#0,6#1,6#2,6#3)}
    

#!/usr/bin/python

def largestSquareAt(sq, i, j, k=1):
    if not ( i+k<len(sq) and="" j+k<len(sq[i])="" ):=""   =""    =""  return="" 0=""  for="" x="" in="" range(0,k):=""  if="" sq[i+x][j+k-1]="='0':" y="" sq[i+k-1][j+y]="='0':" 1="" +="" largestsquareat(sq,="" i,="" j,="" k+1)  =""  ="" def="" biggestsquare(input1):="" len(input1)="=0" or="" not="" (="" input1.count('{')="=input1.count('}')" )="" :="" ''=""  i="str(input1)"  j="i" for="" j]=""  resx="-1"  rexy="-1"  ressize="-1"  res="[]" range(0,len(j)):=""  res.append([])="" range(0,len(j[x])):=""  res[x].append(largestsquareat(j,="" x,="" y))="" ressize<res[x][y]:=""  resy="y"  resstring="" ressize="">0:                                
        resstring = "{"
        for x in range(resx,resx+ressize):
            if x>resx:
                resstring += ","
            resstring += "("
            for y in range(resy,resy+ressize):
                if y>resy:
                    resstring += ","
                resstring += (str(x)+"#"+str(y))
            resstring += ")"    
        resstring += "}"
    
    return resstring  

input = '{0#1#1#0,0#1#1#1,0#1#1#1,1#1#1#1}'
input1 = '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#1#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
input2 = '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#0#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
input3= '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,0#1#0#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
input4 = '{0#0#0#0,0#0#0#0,0#0#0#0,0#0#0#0}'
print biggestSquare('')    
print biggestSquare(input1)    
print biggestSquare(input2)        
print biggestSquare(input3)        
print biggestSquare(input4)

Given a string of length N, output “Correct” if brackets close in correct order else output “Incorrect”

Question:

Given a string of length N, output “Correct” if brackets close in correct order else output “Incorrect”

Input     :   ({}[((({{}})[{()}]))])

Solution(Python):

    # Author            :        Sreejith Sreekantan
    # Description        :        

    #                         Given a string of length N, output "Correct" if brackets close in correct order else output "Incorrect"
    #                         Input     : ({}[((({{}})[{()}]))])
    #                         

#!/usr/bin/python
def validString(input1):
    stk = []
    flag = True
    for x in input1:
        if x in ['{', '(', '[']:
            stk.append(x)
        else:
            if  len(stk)==0:
                flag = False
            elif x == '}' and not stk[len(stk)-1]=='{' :
                flag = False    
            elif x == ')' and not stk[len(stk)-1]=='(' :
                flag = False 
            elif x == '}' and not stk[len(stk)-1]=='{' :
                flag = False    
            if not flag:
                return "Incorrect"
            else:
                stk.pop()
    return "Correct"
 

input1 = '({}[((({{}})[{()}]))])'
input2 = '({}((({{}})[{()}]))])'
print validString(input1)    
print validString(input2)

Count Inversions in an array

This file contains all of the 100,000 integers between 1 and 100,000 (inclusive) in some order, with no integer repeated.

Your task is to compute the number of inversions in the file given, where the ith row of the file indicates the ith entry of an array.

 

Tips:

If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.
Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

Eg: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

 

 

You can get working program from here

Input files :     Input1            Input2

 

Answer for input1 :

Answer for input 2: 25

Google Code jam Solutions: Problem A. Minimum Scalar Product

Problem

You are given two vectors v1=(x1,x2,…,xn) and v2=(y1,y2,…,yn). The scalar product of these vectors is a single number, calculated as x1y1+x2y2+…+xnyn.

Suppose you are allowed to permute the coordinates of each vector as you wish. Choose two permutations such that the scalar product of your two new vectors is the smallest possible, and output that minimum scalar product.

Input

The first line of the input file contains integer number T – the number of test cases. For each test case, the first line contains integer number n. The next two lines contain n integers each, giving the coordinates of v1 and v2 respectively.

Output

For each test case, output a line

Case #X: Y

where X is the test case number, starting from 1, and Y is the minimum scalar product of all permutations of the two given vectors.

Limits

 

Small dataset

T = 1000
1 ≤ n ≤ 8
-1000 ≤ xi, yi ≤ 1000

Large dataset

T = 10
100 ≤ n ≤ 800
-100000 ≤ xi, yi ≤ 100000

Sample

Input Output
2
3
1 3 -5
-2 4 1
5
1 2 3 4 5
1 0 1 0 1
Case #1: -25
Case #2: 6

C++ Solution:

/*
    Author      :   Sreejith Sreekantan
    Description :   Problem A. Minimum Scalar Product
                    (https://code.google.com/codejam/contest/32016/dashboard#s=p0)

*/

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

int main(int argc, char const *argv[])
{
    // freopen("as.in", "rt", stdin);
    // freopen("as.out", "wt", stdout);
    int n;
    cin >> n;
    int c;
    int tmp;
    vector v1, v2;
    int a, b;
    for(int a=0; a<n; a++)=""    ="" {=""        ="" v1.clear();="" v2.clear();="" cin="">> c;
        for(int b=0; b<c; b++)=""        ="" {=""            ="" cin="">> tmp;
            v1.push_back(tmp);
        }
        for(int b=0; b<c; b++)=""        ="" {=""            ="" cin="">> tmp;
            v2.push_back(tmp);
        }
        sort(v1.begin(),v1.end());
        sort(v2.rbegin, v2.rend());

        long long sumofprod = inner_product(v1.begin(), v1.end(), v2.begin(), (long long)0);
        cout << "Case #" << a + 1 << ": " << sumofprod << endl;
    }
    return 0;
}


Project Euler Problem 9: Solution in C++

Special Pythagorean triplet

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

/*
    Author      :   Sreejith Sreekantan
    Description :   
                    Special Pythagorean triplet
                    Problem 9

                    A Pythagorean triplet is a set of three natural numbers, 
                    a < b < c, for which, a2 + b2 = c2

                    For example, 32 + 42 = 9 + 16 = 25 = 52.

                    There exists exactly one Pythagorean triplet for which 
                    a + b + c = 1000.
                    Find the product abc.

    Eg: for Pythagorean triplets:
    (3, 4, 5 )  (5, 12, 13)     (8, 15, 17)     (7, 24, 25)
    (20, 21, 29)    (12, 35, 37)    ( 9, 40, 41)    (28, 45, 53)
    (11, 60, 61)    (16, 63, 65)    (33, 56, 65)    (48, 55, 73)
    (13, 84, 85)    (36, 77, 85)    (39, 80, 89)    (65, 72, 97)
    (20, 99, 101)   (60, 91, 109)   (15, 112, 113)  (44, 117, 125)
    (88, 105, 137)  (17, 144, 145)  (24, 143, 145)  (51, 140, 149)
    (85, 132, 157)  (119, 120, 169)     (52, 165, 173)  (19, 180, 181)
    (57, 176, 185)  (104, 153, 185)     (95, 168, 193)  (28, 195, 197)
    (84, 187, 205)  (133, 156, 205)     (21, 220, 221)  (140, 171, 221)
    (60, 221, 229)  (105, 208, 233)     (120, 209, 241) (32, 255, 257)
    (23, 264, 265)  (96, 247, 265)  (69, 260, 269)  (115, 252, 277)
    (160, 231, 281)     (161, 240, 289)     (68, 285, 293)

*/
#include 
#include 


using namespace std;

void pythagoreanTriplet(unsigned long sum)
{
    unsigned long m, n, s=sum;
    s /= 2;
    unsigned long sqrt_s = sqrt(s);

    for (int m = 1; m <= sqrt_s ; ++m)
    {
        if (s%m==0)
        {
            n = (s/m)-m;
            if (m>n)
            {
                cout << sum << " : " << pow(m,2)-pow(n,2) << " "  
                << 2*m*n << " "  << pow(m,2)+pow(n,2) << endl;
            }
        }
    }

}


int main(int argc, char const *argv[])
{
    unsigned long sums[] = {12, 30, 40, 56, 70, 84, 90, 126, 132, 
                            144, 176, 182, 1000};
    for (int i = 0; i < sizeof(sums)/sizeof(unsigned long); ++i)
    {
            pythagoreanTriplet(sums[i]);
    }

    cout << " the end..." << endl;
    return 0;
}


C++ Brain Teaser : Virtual Destructor

Hi All,

This time I plan to explain to you a C++ brain teaser I came across. With no further adieu, let me get directly to the question:

C++ Brain Teaser : Virtual Destructor Question

What is the problem with this code, if any?

(Assurance from me: this code will compile and execute fine. ie. no compilation error)

.

.

.

.

.

.

Hope you have put enough thought on it. Some might have already cracked it. For the rest of the folks, let me reveal it.

Yes, this code has some serious problem at run-time. If not compilation-error, what is it?

You are right; the worst nightmare, memory leak! But where is it leaking?

Let pause that question for a few minutes to discuss something in C++ language.

In a scenario where a Child class inherits a Parent class, when a Child object is created, first the Parent-Constructor is invoked and then the Child-Constructor and when the Child object is destroyed, first the Child-Destructor is invoked and then the Parent-Destructor is executed.

In our above program, we use a variable of type “Parent” to point to a “Child” object. Lets use below program to check if the order of invocation of constructor and destructor is followed in this case.

virtual Destructor program with cout

Output of the above program is:

Screen Shot 2014-02-04 at 2.33.23 PM

As you can see, here the child destructor is not invoked, which means, whatever we coded in the Destructor method of Child class is not executed. In our main program, we allocate an array of memory in the Constructor of Child and delete the same in its Destructor. So our main program successfully allocates an array of memory but don’t delete it, which will result in Memory Leak.

So we have answered our question. Now lets see how we can avoid it.

Here is where Virtual-Destructor comes for help. Make the destructor of “Parent” class virtual and this issue is solved.

New implementation of “Parent”:

Virtual Destructor New Parent impNew output:

Virtual Destructor new output

To put it straight, virtual destructor forces the parent class to check for child class destructors and executes it.

Use a virtual destructor if you ever expect a derived class to be destroyed through a pointer to the base class to ensure that the destructor of the most derived classes gets called.

It’s a good practice to make the destructors of all interface classes, ie. any class with at-least one virtual method, as virtual.

C++ build tool: boost bjam intro

Reference Material : HERE

Source code (hello_sree.cc):

Screen Shot 2014-02-26 at 2.56.26 PM

build file (jamroot.jam or Jamroot): Screen Shot 2014-02-26 at 7.00.22 PM

Now in terminal, change the present working directory to the folder where the code and build-file resides. Run any of the below commands:

Screen Shot 2014-02-26 at 7.01.05 PMORScreen Shot 2014-02-26 at 7.00.45 PMORScreen Shot 2014-02-26 at 7.01.52 PMORScreen Shot 2014-02-26 at 7.03.09 PM

Ensure you have a space between “hello_sree.cc” and “;” in the build file. Otherwise you will get the below error:Screen Shot 2014-02-26 at 7.03.23 PM

Screen Shot 2014-02-26 at 7.03.33 PM

You will get this message at the successful run:Screen Shot 2014-02-26 at 7.04.01 PMYou will see a bin folder with a hierarchy of folders and executable file created as part of successful build of our program

uHerbert : Pack 4 Level 5 Solution

Till now, the questions were easily solvable. Here comes a tougher one. I have to accept, this one took a fair amount of time for me to solve. So don’t you easily give up trying. This can be easily solved with a program of size 28 or 26 but we have a constraint of program size being 13. I started pulling my hair when I have a program of size 14 and at last when I found how to rephrase it to make it 13, I felt the joy of conquering the world.

Before going to the answer try to solve yourself. In between, if you need some tips or tricks, you are welcome to contact me(put your doubts below this blog and I shall help you). I assure you, you will be much more happier when you solve it by yourself.

Question :

Solve the below maize with a program of size 13.

uHerbert: Pack 4 question 5

Solution :

Screen Shot 2014-01-31 at 3.09.42 PM

For any clarifications: I am here; drop a comment 🙂

ActiveMQ Producer and Consumer in Java

Use this post as a reference for those who work with Apache ActiveMQ middle-ware.

You can download the needed ActiveMQ release from here.

Use this link to get through the installation, configuration and starting of ActiveMQ: Getting Started

You should have Java installed in your machine.I am using ActiveMQ 5.9.0.

Once you bring up the ActiveMQ instance, provided you left all the configurations as default,ActiveMQ will support TCP connections at port 61616. We are going to make use of this port to make our Producer and Consumer classes connect to ActiveMQ.

Disclaimer: ActiveMQ instance and Producer and Consumer programs run on the same machine. Therefore programs can use the URL tcp://localhost:61616 to connect to the ActiveMQ instance.

Producer Class is nothing but a java class which will connect to ActiveMQ and send a message to it specifying the queue to which the message should be en-queued.

Consumer Class is the one which connects to ActiveMQ to retrieve a message from a particular queue.

Lets get to the code now. I used Eclipse IDE to create this java project.
Producer Class(AMQProducer):

import java.sql.Timestamp;
import java.util.Date;

import javax.jms.*;

import org.apache.activemq.ActiveMQConnectionFactory;

public class AMQProducer implements Runnable{
    // Use the same factory for all the producer threads.
    static ActiveMQConnectionFactory activeMQConnectionFactory = 
            new ActiveMQConnectionFactory("tcp://localhost:61616");
    @Override
    public void run() {
        try {
            // Create a JMS connection from the ActiveMQ server
            Connection connection = activeMQConnectionFactory.createConnection();
            connection.start();

            // Create a session to send message
            Session session = connection.createSession(false, Session.AUTO_ACKNOWLEDGE);

            // destination represents the message queue to which the message is en-queued
            Destination destination = session.createQueue("HelloMoto");

            // MessageProducer is used to send messages
            // Refer http://docs.oracle.com/javaee/1.4/api/javax/jms/MessageProducer.html for more
            MessageProducer messageProducer = session.createProducer(destination);

            // Sets the producer's default delivery mode. 
            messageProducer.setDeliveryMode(DeliveryMode.NON_PERSISTENT);

            // Message defines the message header and the acknowledge method used for all JMS messages
            String text = "Hello Motorola from producer " + Thread.currentThread().hashCode() + "..."
            + new Timestamp((new Date()).getTime());
            Message message = session.createTextMessage(text);

            messageProducer.send(message);

            System.out.println("Producer Thread("+Thread.currentThread().hashCode()+
                    ") : Sent \'" + text + "\'");

            // Clean up 
            messageProducer.close();
            session.close();    
            connection.close();

        }
        catch (Exception e) {
            System.out.println("Consumer Thread("+Thread.currentThread().hashCode()+") Exception occured.");
        }
    }    
}

Consumer Class(AMQConsumer.java):

import javax.jms.*;

import org.apache.activemq.ActiveMQConnectionFactory;
public class AMQConsumer implements Runnable, ExceptionListener  {
	// Use the same factory for all the consumer threads.
	static ActiveMQConnectionFactory activeMQConnectionFactory = 
			new ActiveMQConnectionFactory("tcp://localhost:61616");

	@Override
	public void run() {
		try {
			// Create a JMS connection from the ActiveMQ server
			Connection connection = activeMQConnectionFactory.createConnection();
			connection.setExceptionListener(this); // override "void onException(JMSException arg0)" method
			connection.start();

			// Create a session to receive message
			Session session = connection.createSession(false, Session.AUTO_ACKNOWLEDGE);

			Destination destination = session.createQueue("HelloMoto");

			// MessageConsumer is used to receive messages
			// Refer http://docs.oracle.com/javaee/1.4/api/javax/jms/MessageConsumer.html for more
			MessageConsumer messageConsumer = session.createConsumer(destination);

			System.out.println("Consumer Thread("+Thread.currentThread().hashCode()+") : Waiting");

			// receive(long timeout) - Receives the next message that arrives within the specified
			// timeout interval
			Message message = messageConsumer.receive(10000);

			// if the received message is text message, display it on console
			if (message instanceof TextMessage ) {
				TextMessage textMessage = (TextMessage)message;
				System.out.println("Consumer Thread("+Thread.currentThread().hashCode()+ 
						") : Recieved \'" + textMessage.getText() + "\'");
			} else {
				System.out.println("Consumer Thread("+Thread.currentThread().hashCode()+
						") : Dont have any message to display");
			}

			// Clean up
			messageConsumer.close();
			session.close();
			connection.close();

		} catch (Exception e) {
			System.out.println("Consumer Thread("+Thread.currentThread().hashCode()+") Exception occured.");
		}		
	}

	// If a JMS provider detects a serious problem with a connection, it informs the connection's
	// ExceptionListener,
	@Override
	public void onException(JMSException arg0) {
		System.out.println("Consumer Thread("+Thread.currentThread().hashCode()+") JMS Exception occured.  "
				+ "Shutting down client.");
	}
}

Main Class(AMQMain):

import org.sree.activemqeg.AMQConsumer;
import org.sree.activemqeg.AMQProducer;

public class AMQMain {

	public static void main(String[] args) throws InterruptedException {
		(new Thread(new AMQProducer())).start();
		(new Thread(new AMQConsumer())).start();
		(new Thread(new AMQConsumer())).start();
		(new Thread(new AMQConsumer())).start();
		Thread.sleep(1000);
		(new Thread(new AMQProducer())).start();
		(new Thread(new AMQProducer())).start();
	}
}

Output:

Apache ActiveMQ Java Producer Client OutputNeglect the log4j warnings for the time being…

You can analyze the statistics of the various queues of ActiveMQ from a browser with the URL http://localhost:8161 (replace ‘localhost’ with the IP of the machine if ActiveMQ is in a different system). Have a look at the queue we created with our program.

ActiveMQ queue screenshot

Meet you in my next post “ActiveMQ Producer and Client in Java using Spring Framework” which will make things more configurable and professional. 😉