google

After a long saturday in berlin I could write some facts about the talks and list all the news. But the gdd world tour is over and all speaker announced to publish the slides. So I will offer the not-complete list.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

Yesterday it was a very long day starting at 7 o'clock on the M.U.C in munich (ends 8 pm) - here only the first visual impressions from the google developer day 2010 in munich. Later I will give some written impressions to the talks and I try to collect all links to the shared documents (or help with comments).

 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

Problem

In the 2009 qualification round there was a simple problem with a nice background story:

After years of study, scientists at Google Labs have discovered an alien language transmitted from a faraway planet. The alien language is very unique in that every word consists of exactly L lowercase letters. Also, there are exactly D words in this language.

Once the dictionary of all the words in the alien language was built, the next breakthrough was to discover that the aliens have been transmitting messages to Earth for the past decade. Unfortunately, these signals are weakened due to the distance between our two planets and some of the words may be misinterpreted. In order to help them decipher these messages, the scientists have asked you to devise an algorithm that will determine the number of possible interpretations for a given pattern.Read more

The rotate example nico last week reported was funny to solve: No rotating needed! Read the complete problem description in nicos article or in the google code contest page. Here my complete python solution with file handling and solution printing.

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