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

Output:

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

Output:

LOVE 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

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

*/

#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;
}



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

/*
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:

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.

Output of the above program is:

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”:

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

build file (jamroot.jam or Jamroot):

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

OROROR

Ensure you have a space between “hello_sree.cc” and “;” in the build file. Otherwise you will get the below error:

You will get this message at the successful run:You 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.

Solution :

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.

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

") : Sent \'" + text + "\'");

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

}
catch (Exception e) {
}
}
}

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

// receive(long timeout) - Receives the next message that arrives within the specified
// timeout interval

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

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

} catch (Exception e) {
}
}

// If a JMS provider detects a serious problem with a connection, it informs the connection's
// ExceptionListener,
@Override
public void onException(JMSException arg0) {
+ "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 {
}