Getting a Boost

March 11, 2011

Most of you that use C++ (and some of you that don’t) are sure to have heard of Boost C++. I won’t go into what it is, since if you want to know that just follow the previous link. I will however talk about the “installation” process. This is mainly for me, in case I ever feel like putting it on another computer, but I suppose some people might find this useful.

Step 1

Download Boost, I would recommend the latest version but it’s your call. You can find download links by going to the Boost website and doing a little “read-n-search”, aka using your brain. I will assume that you have downloaded the file (let’s call it FILE, and assume it is has extension bz2) to your desktop. Open a terminal and move to where you would like the Boost files/libraries/binaries to be located, call this $BOOST. In short you just run the following in the terminal:

cd $BOOST
tar --bzip2 -xf ~/Desktop/FILE

Step 2

At this point you are more or less done and are able to use quite a few of the provided libraries. However, there are some libraries that need to be built. So let’s go ahead and build them all, since you never know when you’ll need one, and you aren’t that strapped for space on your system.
First move to the folder that contains a file called bootstrap.sh, on my system that means moving to $BOOST/boost_1_46_0/. At this point I assume that you will be using the “default” GCC compiler.

(sudo) ./bootstrap.sh --prefix=$SOME_PATH --libdir=$OTHER_PATH

The sudo is optional depending on what you choose for $SOME_PATH and $OTHER_PATH. I chose $SOME_PATH=/usr/local and $OTHER_PATH=/usr/local/lib, in these cases I did need to include the sudo.
This should run without any errors.

Step 3

Finally you are ready to build and install the libraries. However, first there is a file called project-config.jam in your directory. Read it’s contents, at the bottom there should be a place that tells you what your prefix and libdir are set to. Make sure these are what you want, if not delete this file

rm -f project-config.jam

and go back to step 2.
So everything is in order. Now just run

(sudo) ./bjam --build-dir=build --layout=system install

You will only need to use sudo if it was required for the previous step. This command will the necessary files into $OTHER_PATH (you should go there to make sure it worked). This command will take a while to run since we are installing all the libraries (there is a way to specify which to install but I won’t bother with that). There will be a lot of text printed to the screen, just keep any eye out for anything that looks like an error message. Some of these can be ignored, like the ones that deal with Python integration, while others are actual problems you will need to fix.

Step 4

Hopefully, you have made it this far without any errors. So it is time to test that everything actually works.

//ASSUME THIS FILE IS CALLED test.cpp
#include <boost/regex.hpp>
#include <iostream>
#include <string>

int main()
{
   std::string line;
   boost::regex pat( "^Subject: (Re: |Aw: )*(.*)" );

   while (std::cin)
   {
       std::getline(std::cin, line);
       boost::smatch matches;
       if (boost::regex_match(line, matches, pat))
           std::cout << matches[2] << std::endl;
   }
}

Use the following to compile

g++ -o test test.cpp -I $BOOST/boost_1_46_0 -L $OTHER_PATH -lboost_regex
./test

If there are any mistakes or if you have any suggestions let me know. I know this isn’t the best walk through but I think it’s better (for beginners) than the one presented at the Boost website.

Advertisements

Inclusion Exclusion

August 22, 2010

I am sure that most of you have heard of the inclusion exclusion principle.  If not then I suggest that you either head over to Google or Wikipedia.  It is a really useful technique with many applications; even to this day I am still discovering new ways in which it can be used.

In this post I will outline a partial solution to the following problem located on SPOJ, PGCD.

The first thing you should notice is that the answer to (a,b) will be the same as the solution to (b,a).  This is because of the symmetry of the gcd(\cdot,\cdot) operation, thus suppose that a\le b.

Suppose that there are a columns in our gcd table.  We will find how many primes there are in each column.  Suppose that there are m rows, and we are looking at column n=p_1p_2\cdots p_r, where p_1,p_2,\cdots,p_r are distinct primes.  I’m not going to consider the case where a prime factor is repeated, though I have a feeling that the solution below should still work.

First we find how many multiples there are of each prime between 1\ \mbox{and}\ m.  This is just

\displaystyle\sum_{i=1}^r\left\lfloor\frac{n}{p_i}\right\rfloor

But what about the multiples of say, p_1p_2?  Well they were counted twice, and their entry in the table is not going to be a prime (you can easily convince yourself of this fact).  So we just subtract them out twice, leaving our answer as

\displaystyle\sum_{i=1}^r\left\lfloor\frac{n}{p_i}\right\rfloor-\sum_{1\le i<j\le r}2\left\lfloor\frac{n}{p_ip_j}\right\rfloor

Now what about the divisors of n with exactly 3 prime factors?  Their multiples have been removed too many times, thus we need to add them back.  If we continue this way we see that we will be using inclusion exclusion.

So to solve this we can use the following code.


#include bitset
#include vector

int answer=0;
bitset PIE;
for(int i=2 to n;++i)
{
	vector prime_factors=factor(i);
	int r=prime_factors.size();
	for(int cnt=1 to 2^r - 1;++cnt)
	{
		PIE=cnt;//express cnt in base 2 and store in PIE
		int ones=PIE.count();//the number of 1s in our bit string
		int p=1;
		for(int j=0 to prime_factors.size() -1;++j)
			if(PIE[j])
				p*=prime_factors[j];
		if(ones&1)//there are an odd number of 1s
			answer+=(ones*(m/p));
		else//there are an even number of 1s
			answer-=(ones*(m/p));
	}
}

This isn’t totally legal code because I had to paste it into HTML so the less than and greater than signs disappear and I don’t want to waste the time to fix it (even though I know how to).
For those of you that don’t know the bitset is just a string of 1s and 0s. When I did PIE=cnt I basically set it so that the bit string was equal to the base 2 representation of cnt. Using this method we can get all possible combinations of the prime factors.
The code can easily be converted to Java since I think it too has something similar to a bitset. If your language of choice doesn’t have a bit set, no need to worry. You can just get the base 2 representation on your own (it’s not that hard, trust me).
WARNING: This approach will only be feasible if each number doesn’t have too many prime factors. Not the case with the problem on SPOJ since each number can be decomposed into the product of at most 23 primes, and at most 9 distinct primes. So I’m not sure if the time limit will allow you use this method, I haven’t tried, but please let me know if you do.


Included Files

August 22, 2010

Do you ever wonder where the files you include in your C/C++ programs are located, and how the linker finds them?  Well on a Linux system (unless you have changed things) they are located at /usr/include and /usr/include/c++.  If you go you can see the list of files you can #include in your program.  Additionally, you can view the source code, if you are the kind of person (and I have a feeling that you are) that finds these things interesting.


Eclipse

July 16, 2010

I’m sure that you have heard of Eclise.  If not then all you need to know is that it is a very popular (and for a good reason) IDE mainly for Java.  However, it does also have C/C++ support, but it is mostly used with Java.

As you know, I’m not big on programming in Java.  But I recently purchased a Nexus One phone, and the IEEE SECon got me a little interested in Android application development.  I don’t plan for anything I make to be widely distributed, but rather just for personal use.  In any case, I would still need a place to create my programs.  Sure this can be done with a normal text editor and the command line but why bother with that when Eclipse and the Android SDK make it so simple?

I’m going to talk about getting and installing Eclipse onto you system (which I will assume to be Ubuntu).  Sure you could just run sudo apt-get install eclipse but this way assumes that you are using the OpenJDK version of Java and not Sun’s. So if you are using SunJava, which it seems most people do, then this how-to is for you.

First head over to the Eclipse site and download the IDE. To find the site just use Google and then do some reading and clicking, so there is no need for me to post a link. If you can’t get past this step then you probably shouldn’t be thinking about using Eclipse.

Next we will open the package you have just downloaded and then move it to the /opt directory. To do this just run the following sequence of commands:

tar xzf <filename>
sudo mv eclipse /opt/eclipse
cd /opt
sudo chown -R root:root eclipse
sudo chmod -R +r eclipse
sudo chmod +x `sudo find eclipse -type d`

The chown command changes the owner of a file/directory, if you have been reading this blog then you should be able to figure out what the other commands do.

Next we will add eclipse executable to your path.

sudo touch /usr/bin/eclipse
sudo chmod 755 /usr/bin/eclipse
sudoedit /usr/bin/eclipse

then add this to the file

#!/bin/sh
#export MOZILLA_FIVE_HOME="/usr/lib/mozilla/"
export ECLIPSE_HOME="/opt/eclipse"

$ECLIPSE_HOME/eclipse $*

I’m not all to sure exactly what the touch command does but you can look that up yourself (either online or with man).

Finally, the “most important” part; creating a GNOME-menu icon. This is something that would normally be done when you use the apt-get method.


cd /usr/share/applications
sudo nano eclipse.desktop

And enter the following into the created file;

[Desktop Entry]
Encoding=UTF-8
Name=Eclipse
Comment=Eclipse IDE
Exec=eclipse
Icon=/opt/eclipse/icon.xpm
Terminal=false
Type=Application
Categories=GNOME;Application;Development;
StartupNotify=true

All the stuff entered into the file makes perfect sense, so if you ever wanted to make a menu item for any other program you now know how.

All of these steps can be found at http://flurdy.com/docs/eclipse/install.html.


See My Coffee: A C and Java tale

August 13, 2009

Anyone with half a brain can tell you that (pick one: C/C++ or Java) is vastly superior to (pick the other). The only problem is that I don’t know all that much about Java. So instead of doing the obvious thing and talking about how “C/C++ is better than Java”, I am going to talk about a few aspects of C++ that annoy the hell out of me.

Fist off why would you have a ‘long‘ data type if it is not required to be any bigger than a regular ‘int‘?  All that is specified is that both int and long must be at least 32bits. Thus if you want to get a 64bit integer you have to use ‘long long‘ (or __int64 if you are using Microsoft Visual C++).  This should really be addressed, and hopefully sometime soon. Though I suppose there are more pressing issues.

Second, I don’t know about you but no one ever told me why you it is poor C++ programming to include a class function’s definition inside the class.  It wasn’t until I was reading Thinking in C++ Vol.1 that it was made clear.  When you do this, the compiler will inline your function.  This means that everywhere you use it the compiler will reproduce the written code, instead of making a function call.  Sure, for small functions this is alright, but for larger ones it can add to code bloat, thus possibly resulting in a slower program.  The “standard” for determining if a function is small is, “does it take up more than one line of code?” If so then don’t inline.

Why are struct and classes the same?  The only difference is that the members of a class default to private, while those of a struct default to public.  Oh well, until they change this I will continue to use struct and then specify private/protected/friend when needed.

Finally, the STL is not quite as vast as the Java API.  But that can be attributed to what the languages were designed for, so I suppose I can live with this “fault”.


Balance

July 25, 2009

No big news yet.  Still exploring though.  Recently I have been trying to code a balanced binary tree.  As for why; I am trying to solve ORDERS on SPOJ.  Doing a naive with arrays and linked list are too slow. However,  you can use the same approach with trees (balanced trees actually) and have your solution accepted.  I already know how to solve it in my head, the only hindrance is actually creating a balanced binary tree.  Well I think I’ll take a break from thinking about it for a while and move on to another problem.  Then come back when my skills have matured (lord knows they have a lot of that to do).

Apart from balanced binary trees I’ve also read about heaps.  The one I find most interesting is a variant called an interval tree.  Basically suppose node X is the interval [a,b] with a<b, then its two children are the intervals [a,c] and [c+1,b], where c is the midpoint of [a,b].  I came across this structure when reading a TopCoder tutorial on how to solve the Range Minimum/Maximum Query problem.  Though I have yet to actually practice using any of these methods, the tutorial did a good job of explaining so I don’t imagine it being all that hard.