Atoms in Regular Expressions

Posted in Perl with tags , , on December 14, 2008 by vinaychilakamarri

I read about something interesting today. There is a term called ‘Atom’  when you are dealing with regular expressions. Knowing the importance of  how you formulate a regular expression becomes important because some
expressions might turn out as something you usually don’t anticipate. Talking about quantifiers in the context of  atoms, the importance of atoms becomes more vivid when you consider this example: ha{6}, (ha){6}. Although
they seem to be very similar, the additional parentheses treat ‘ha’ as a single atom and match only those words whose pattern contains ‘ha’ for 6 consecutive times. The former expression tries to match only those patterns in which ‘h’ is followed by 6 a’s. Let’s say I wanted to match a word that starts with ‘pre’ and ends with ‘tion’

These are some of the possibilities that I should be expecting:
premonition
predilection
prediction
etc.

So, a possible expression can be:

^(pre)+([a-z]*|[A-Z]*|\\s)*(ion)+\$

Any word that beings with the atom “pre”, in which the atom “pre” Must occur at least one time and can occur more than one time after the beginning, and there can be 0 or many characters in the middle, starting from a-z OR A-Z OR space characters with a quantifier *, which indicates that the characters can occur 0 or more times, with an external quantifier that ensures that the letter case is ignored during the match, and it only matches the patterns that end with the atom, “ion”, which is specified by the concluding $

Example 2:

^?[0-9]+(ord)+\$?

Says that the atom ‘ord’ has to be preceded at least once by a number. The + quantifier after [0-9] signifies that the numbers can be repeated any number of times. Also the ^? signifies that the numbers need not start from the beginning of the pattern in question. Also what the “\$?” means is that the pattern need not essentially end with the atom “ord”

Advanced Packaging Tool forces the usage of CD-ROM sources and quits…. help!

Posted in Linux with tags , , , on December 13, 2008 by vinaychilakamarri

When I started using a headless Debian, my only weapon to install the needed packages was ‘apt’. But I was hit on the head, when it was forcing me to install sources from CD-ROM, instead of looking for sources from the internet. Picture this scenario:

vinay@darkbox:~$ sudo apt-get install blah-app

………………

After printing some packages that need to be updated

…………..

………

[b]Media change: please insert the disc labeled
‘xxxxxxxxxxxx_xxxxxxxxxx_ -xxxxxxxxx(xxxxxxxx)’
in the drive ‘/cdrom/’ and press enter
<enter>
Media change: please insert the disc labeled
‘xxxxxxxxxxxx_xxxxxxxxxx_ -xxxxxxxxx(xxxxxxxx)’
in the drive ‘/cdrom/’ and press enter

** The xxxxxxxxxxxx_xxxxxxxxxx_ -xxxxxxxxx(xxxxxxxx) can be anything depending on your distro.

A solution for this is to comment out the source list that points to the CD-ROM on the apt sources. So I did this:

vi /etc/apt/sources.list and comment the line that reads something similar to this:

deb cdrom:[ xxxxxxxxxxxx_xxxxxxxxxx_ -xxxxxxxxx(xxxxxxxx) ]/ hoary main restricted

This will restrict the apt tool from looking back to CD-ROM for the sources and quit. There may be some other approaches for this problem. It would be helpful if anyone who reads this thread discuss those approaches here.

Good Luck!

Tetrahedral Numbers puzzle

Posted in Algos on November 23, 2008 by vinaychilakamarri

Was attending an interview few days ago an I was presented with a good puzzle. The question goes this way:

A pirate arranges his cannon balls as show in the following way:

1

In the first arrangement, there is only one cannon ball. To support it, he inserts 3 cannon balls under it. And to support those 3, 6 would be placed under them and so on. Now if you count the balls in each case it would follow a series like 1 , 4 , 10 …. Write a logic for generating this.

This is interesting puzzle. As we can see, the cannon balls have some embedded pattern in them:

1

1 + (1+2)

1+ (1+2) + (1+2+3)

and so on.

A little math knowledge would help here. If you are aware of the formula for first N natural numbers, it is

N* (N+1) / 2. This can be extended to this puzzle easily to calculate the series. Here is how it can be applied

1*(1+1)/2

1*(1+1)/2 + 2 * (2+1)/2

1*(1+1)/2 + 2 * (2+1)/2 + 3*(3+1)/2

and so on.

As can be seen, we could apply a Sigma operator to condense this formula a little bit:

∑ n * (n+1)/2

for n = 1 to n

Now that we have a cute little Math counter in our hand, we can code it fast. Here is what I did:

public class TetrahedralNumbers {

public static void main(String[] args){

int cannon = 0;
for(int i = 1; i < 14; i++)
{
cannon += (i * (i+1))/2;
System.out.println(cannon);
}
}

}

If you are unaware of the Math part and want to go solving this, there is a slightly inefficient approach that still solves the puzzle:

public class TetrahedralNumbers {

public static void main(String[] args)
{
for (int i = 1; i < 10; i++)
{
int count = 0;

for(int j = 1; j <= i; j++)
{
for(int k = 1; k <= j; k++)
{
count += k;
}
}
System.out.println(count);
}
}

}

Installing Gnome for a headless CentOS Image for VirtualBox

Posted in Linux with tags , , , , , on November 18, 2008 by vinaychilakamarri

Was searching for VDI Linux image files to plug them into my Virtual Box and was wanting to play around with CentOS image.

http://virtualbox.wordpress.com/images/

This place has a gorgeous collection of images. You can pick one from them too. But the latest distribution of CentOS comes with no GUI.So I wanted to have Gnome on my new CentOS baby. Luckily it had wget, yum for rescue. Here is what I did after booting up the image and logging in as root (don’t follow this before you read entire article):

yum groupinstall “X Window System” “GNOME Desktop Environment”

After downloading a bunch of packages, it complained about the absense of  a “libgaim.so.0” package that is needed by “nautilus-sendto” package. You would see something like this:

0002483: nautilus-sendto requires a non-existent libgaim.so.0

Fortunately, it’s a known bug: http://bugs.centos.org/view.php?id=2483

The solution is to get an rpm package and install it with nodeps option. So here is what you need to do:

wget http://mirror.centos.org/centos/5/os/i386/CentOS/nautilus-sendto-0.7-5.fc6.i386.rpm

After downloading the package, install it as follows:

rpm -Uvh –nodeps nautilus-sendto-0.7-5.fc6.i386.rpm

Once this is done, type in this:

yum groupinstall “X Window System” “GNOME Desktop Environment”

That’s it. Your headless centOS is equipped with Gnome!

Creating a map of maps in Java

Posted in Java with tags , , , on July 30, 2008 by vinaychilakamarri

At times I saw that some people get struck when it comes to creating a map of maps. It is not really a rocket science but needs a little sleight of hand. Here I will explain on how to create a map of maps in Java language. The same can be used for other languages. Also post in some of the other cool tricks if you may have any:

Here is the scenario… I have a text file in this format:

Gasoline Mexico $2.5

Gasoline USA $4.5

Gasoline Afghanistan $85

Beer Mexico $1.25

Beer USA $2.85

Beer Afghanistan $0.0

Now I want to query for ‘gasoline’ and get a map of all ‘country —> price’ listings. Similarly, I want to ask for beer and get a list of ‘country —> price’. This can be easily done by building a hashmap of hashmaps. As a visual guide, this is how the Datastructure will look like, after we’re done designing it:

My Approach:

Hashmap<String,Properties> gasBeerMap = new HashMap<String,Properties>();

//read the text file, get the inputstream

while(there are more lines in the textfile)

{

String[] tokens = tokenize the line;

Properties tmp = (Properties) gasBeerMap.get(tokens[0]);

if(tmp == null)

{

tmp = new Properties();
_gasBeerMap.put(tokens[0],tmp);

}

tmp.setProperty(tokens[1],tokens[2]);

}

This will check if the map for a specific entry is null. If it is, then it will insert a new map to that specific entry as it’s mapped value. As it can be observed, for the next iterations, the map will only get updated. This is one approach to the problem. Let me know if you have some cool approaches to this problem

Exporting your Java project to a jar file in two clicks using Fat-jar plugin

Posted in eclipse, Java with tags , , , , , on July 29, 2008 by vinaychilakamarri

Sick and tired of writing manifest files and arranging jar files and class files, I searched to see if I can find some click-click-click eclipse feature that will do this job for me. And the answer came in after a brief googling: The fat-jar plugin. Installing this plugin’s zip is easy. Extract the zip to some place and copy the folder under ‘plugins’ to the actual eclipse plugins directory. Restart the eclipse and you should see a ‘Build Fat jar’ with a green cross when you right click on your project. Here is the tutorial on how to build the jar file after you are done with the plaugin installation:

http://fjep.sourceforge.net/fjeptutorial.html

Happy jar building!

Subtle things in perl part 2: The difference between ‘or’ and ||

Posted in Perl on July 27, 2008 by vinaychilakamarri

In perl, both ‘or’ and || mean the same thing. But they act in different ways when used in certain circumstances. For example, lets say we are trying to open a file for read and write operations. It’s always a good idea to handle the IO errors and we do this in the following way:

………………..
$file = shift;
open FILE, $file or die “Couldn’t open the file $file”; #note this
…………………

The second step can also be written in this way:
open FILE, $file || die “Couldn’t open the file $file”; #note this

But when the execution of this program happens, you will never see the message in ‘die’, if you use a || instead of ‘or’. Reason for this is that the || operator has a precedence level higher than that of ‘or’ and since
the ‘open FILE, $file’ returns a value after an attempt to execute, the || is always true and die is never reached
.

The actual reason as Martin, one of the commentators  puts it,

The actual reason is that the operator precedence for the double pipe is higher than the comma, so perl is resolving the double pipe first, which chooses the first true result of its two parameters, in this case $file and the die statement. As long as $file is a nonempty string it counts as true and always gets returned by the double pipe.

So it is always advisable to use ‘or’ instead of ||. If you want to use ‘||’, you can do it by using the
pen file with parathesis which ensures the precedence of the operators.

open (FILE, $file) || die “Couldn’t open the file $file”;