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

I am running a IP-Geo-location demo in my App Engine. After many silent months I got some traffic on it (and hitting the daily CPU limit). Some one would kick the "traffic monster", after all it's starts only as a demo, other ones (like me) will try to optimize the GEO-location script.

Read more

Due to its ListActivity class the Android SDK helps developers to create List-GUIs easily. Therefore the ListActivity uses a ListView. But what about customized lists? What about own list-designs? In this post I'll try to show how to extend a standard ListView to create a custom list-design. To create your own list-design, you should define how an item in your list should look like. As an example I'll use a list of Twitter-updates (also called „tweets“).

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:

Yoda was a great teacher except for his word sequence. For programmer exists the yoda condition. But was is it? Here a normal if-code-snipplet :

As yoda condition written:

I found some discussions on stackoverflow.com and collected some pros and no really contras.Read more

Bananas are picked from the tree green and unripe. Their ripening process continues while they are transported to the markets and end up at the customer. Let us just ignore the fact, that the ripening process is initiated by an artifical condition.

So Banana-Software is software, that "ripes" while in production at the customer. Some people might call it Beta-Software. I've seen plenty of examples where software went into production when it was still Banana-Software.

There's nothing bad in developing software in close contact with the customer. Eg. using Extreme Programming, Rapid Prototyping or some other agile method you prefer. But when it comes to putting software into production, there are some things to consider.Read more

The object access benchmarks last weeks was not surprising but a factor 5 between access "obj.a" and "obj.getA()" is interesting. In this second part I check the access time for properties on objects, created with ECMAScript 3 getter/setter and with the ECMAScript 5 Object.defineProperty variant (works on IE8+, FF3.7+, newest Webkit and Chrome 5) - see more on ECMAScript 5 compatibility table. Oliver asked to add getter tests - and the results produce differences with factor 15-100.Read more