Google Code Jam coded solutions

Here you can find the solutions (coded by myself) to some of the Google Code Jam problems I challenged myself with over the past 2 years. These might not be optimal, but I gave my best to it! I also enjoyed myself implementing a rough, pure python, graph library from scratch, which supports among others edge weighting, breadth first and depth first searches. This is not optimal by any means, but the interface is simple and can solve GoogleJam large inputs in the provided time constraints.

A few useful tricks I learned

1. Writing Makefiles for multiple machines

It happens a lot of times that one develops code locally, for example on a laptop computer, and may want to run the same code at some remote location. For example you may want to test Gadget on your laptop, running a small simulation with only \(32^3\) particles, but in order to run a realistic simulation with \(512^3\) particles (which requires 128GB of RAM) you need to export the code on some remote, and more capable, computer cluster. There are all sorts of trouble when you do this, and the main one is that the paths to the compilers and libraries you want to link to your code will be all different. Including all these differences in the same Makefile can be a pain, and so I often adopt this strategy: I create four different Makefiles, called "Makefile", "Makefile.main", "Makefile.mylaptop" and "Makefile.cluster" respectively. These have the following structures 
 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
######Makefile.main#############
######This contains all the dependencies, for example###########
executable: executable.o
$(CXX) executable.o -o executable $(LINK)
executable.o: executable.cpp
$(CXX) -c executable.cpp -o executable.o $(INCLUDES)

######This needs to be set only once! It's machine independent!###########


#######Makefile.mylaptop###########

#######This contains the paths to the local compilers, for example#########
CXX = clang++
INCLUDES = -I/usr/local
LINK = -L/usr/local -lfftw3

#######Makefile.cluster###########

#######This contains the paths to the remote compilers, for example#########
CXX = /path/to/c++/compiler/g++
INCLUDES = -I/path/to/fftw_library/include
LINK = -L/path/to/fftw_library/lib -lfftw3

#######Makefile###########

#######This contains only three lines, and that's the file that "make" will read!############
me = ${THIS}
include Makefile.$(me)
include Makefile.main
All that you have to do is set an environment variable called THIS in your laptop and on the cluster; THIS will have the value "mylaptop" on the local machine, and "cluster" on the remote machine. This will ensure that "make" selects the correct compiler paths in a machine independent way

2. Linking C++ dependent libraries to C code

Have you ever been stuck with the problem of having to link a C++ library to your C code? The opposite is very easy to do (just prepend "extern "C" " to all the C functions you need to include in your C++ code), but that's not the point we're talking about here. I had to solve this problem when I needed to link some openCV libraries to do some image processing on galaxy images; too bad that the latest version of openCV is written in C++, and my original analysis code was straight C... how to solve this problem? That's how I did it: the first thing to do is wrap your C++ function call in a C compatible interface; by "C compatible" I mean that this interface must not include any C++ classes (with defined methods in them), but only C types. Suppose that this wrapper function is contained in a file called "myfunc.cpp" 
 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
////////////*myfunc.h*////////////////
#ifndef __MYFUNC_H
#define __MYFUNC_H

#ifdef _MYFUNC_IS_CPP
extern "C" void myfunction(int x, .....);

#else
void myfunction(int x, .....);

#endif


#endif

/////////////*myfunc.cpp*///////////////
#define _MYFUNC_IS_CPP

#include "myfunc.h"

extern "C" void myfunction(int x,...){
	//Function body, can have C++ library calls (e.g. openCV) etc...
}

#undef _MYFUNC_IS_CPP
You compile this code with your favourite compiler, and, why not, put it in a library: 

	clang++ -c -g -Wall myfunc.cpp -o myfunc.o -I/path/to/opencv/include -I/path/to/myfunc
	ar libmyfunc.a myfunc.o
	ranlib libmyfunc.a
Now the issue is how to link this wrapper library to a C code: suppose that you have a C driver that makes use of myfunction, say something like this 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
///////////*driver.c*///////////////////
#include "myfunc.h"

int main(){

	int x;
	......

	myfunction(x,....);

	return 0;

}
How do you compile and link it properly? Since this code is (almost) straight C, you can do the following. To compile: 

	clang -c -g -Wall driver.c -o driver.o -I/path/to/myfunc
At linking stage you need to specify the original C++ library you wanted to link to (e.g. openCV), as well as the standard C++ library, libstdc++ 

	clang -g driver.o -o driver -L/path/to/myfunc -lmyfunc -L/path/to/opencv/lib -lopencv_core -lstdc++
And you are done!!