code jam

The facebook hacker cup is a google-code-jam like coding contest - starting with the 2012 qualification round this weekend. Try to solve the 2011 practice round. If you can submit your solution (the spinner after submit dont stops) try to check the result response with HTTPFox (it shows the correct / incorrect response) - hoping this will be fixed for this weekend.

All solutions can be testet with codejammer.com - a fine javascript solution for running code contests like facebook hacker cup or google code jam.Read more

Space Emergency is a nice little puzzle from Google Code Jam 2011.

The solution is quite simple. Fly as long as the boosters are built. Once they are done, reorder your remaining distance. Use the boosters on longest distances. Voila - that's it.

Let’s see the straight forward implementation for the small input.

This is a problem I particularly enjoyed. I had to turn it around a few times in my head before I found the solution.

First I was thinking about simulation the chickens moving before noticing I am going in the totally wrong direction.
Then it dawned to me, that the solution is quite simple.

We can break the solution down into two parts.

• Is the specific case solvable
• How many swaps do we need

Is the specific case solvable

Leaving all other aspects aside, just check if enough chickens can make it to the barn in time. If this is not the case, it's an IMPOSSIBLE one to solve.
For this to find out, you only need to get their position, add the speed multiplied by the time you have at hands and see if they make it into safety, also known as the barn.

With the Google Code Jam 2011 less than four weeks away, it is time for some finger exercises.

Let's start with the Minimum Scalar Product, which should only take you a few minutes.

Here's the Java version, which will only work for the small input set. I'll explain later.

What we do is sort both arrays, then multiply them. One starting from the beginning, the other from the end. So our biggest numbers are multiplied with the smallest. The math is on Google's solution page, we're just looking at coding here.Read more

Time again for a new google code jam article about alien numbers. This time instead of decoding words from an other alien language we have to convert numbers from one alien digit system to another.Read more

It's time for some basic finger exercise. The Google Code Jam Rotate is very trivial, so relax and fire up your IDE.

I was a bit lazy, so there is no reading of the input sets, just a two-dimensional array and two functions

Rotating

As the Google solution pointed out, there is actually no need to really rotate the 2dim array. Just push everything to the right, as if gravity would be to the right. That's the same as rotating everything and keeping gravity towards the bottom. But we save a few lines this way.

So here is the "gravity from the right" code

Theme Park is another good example of a problem which can be solved with a fairly simple algorithm. The simple version will solve the small input set without a problem, but will run almost infinitely with the large dataset.

You can read the problem on the Google Code Jam site: Theme Park

simple solution

The simple solution is to put the groups in a static array, use a pointer that "wraps around" using modulo and fill the roller coaster until it's so full, that the next group does not fit in, then let it ride earning income accordingly to the seats taken.

This is a correct solution, but unfortunately a bit slow. The input set can have a roller coaster with up to 10⁹ seats and 10⁸ rides and groups as large as 10⁷. Read more

The Google problems are always nice, sometimes even a bit too tricky. This years entry problem was quite nice with some difficulties you could run in.

You need to read the problem first, to follow the article, so here's the link: http://code.google.com/codejam/contest/dashboard?c=433101#s=p0&a=0

If you're a hands on programmer first you might just want implement the chain without looking at the problem more extensively. So you might end up with something like this:

The Google Code Jam is an interesting option to work on some challenging problems.
With the first qualification round coming up at May 7th, it's time to look at the Africa qualification round, to see what to expect.

You have 24 hours to solve three rather simple problems. Solving two problems brings you into the next round.

I will present my Java solutions. The Code Jam site provides the code of every contestant.

Store Credit

read problem description
You just need two nested loops to find the matching articles. Just a finger exercise.