Home ›

google

Christian Harms's picture

Google code jam solution for alien language

by Christian Harms on Mon, 08/30/2010 - 10:58
in

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

Christian Harms's picture

The rotate google contest in 15 lines

by Christian Harms on Thu, 08/19/2010 - 12:35
in

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.

  1. import sys
  2. from re import search
  3.  
  4. fp = file(sys.argv[1])
  5. for case in range(1, 1+int(fp.next())):
  6.     n, k = [int(x) for x in fp.next().split()]
  7.     lines = [fp.next() for x in range(n)]
  8.    
  9.     #right-gravitation and joining to one line (delim is a line)
  10.     s = "#".join(map(lambda x:"%%%ds"%n%(x.strip().replace(".","")), lines))
  11.     result = 0
  12.  
  13.     #find one of the 4 variants: horiz, verti, slash, backslash for Blue
  14.     reB = "(B.{%%d}){%d}B" % (k-1)
Read more

Nico Heid's picture

Google Code Jam - Rotate

by Nico Heid on Sun, 08/15/2010 - 17:33
in

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

  1. public static void fakeRotate(char[][] board) {
  2.  
  3.     for (int i = 0; i < N; i++) {
  4.         for (int j = N - 1; j >= 0; j--) {
  5.             if (board[i][j] != '.') {
  6.                 // push to right
  7.                 int m = 1;
  8.                 while ((j + m) < N && board[i][j + m] == '.') {
Read more

Nico Heid's picture

Google Code Jam - Theme Park

by Nico Heid on Sat, 07/31/2010 - 12:20
in

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 109 seats and 108 rides and groups as large as 107. Read more

Nico Heid's picture

Google Code Jam - The Snapper Chain

by Nico Heid on Sun, 06/20/2010 - 12:23
in

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:

  1.                         // snapping
  2.                         boolean toggle = true;
  3.                         for (int j = 0; j < snaps; j++) {
  4.                                 toggle = true;
  5.                                 for (int k = 0; k < snapperCount; k++) {
  6.                                         if(toggle == false){
  7.                                                 break;
  8.                                         }
  9.                                         if (toggle == true) {
  10.                                                 snapper[k] = !snapper[k];
  11.                                         }
  12.                                         if (snapper[k] == true) {
  13.                                                 toggle = false;
  14.                                         }
  15.  
  16.                                 }
  17.                         }
  18.  
  19.                         // we need power on all snappers
  20.                         boolean power = true;
  21.                         for (int j = 0; j < snapperCount; j++) {
  22.                                 if (snapper[j] == false) {
Read more

Nico Heid's picture

Google Code Jam - Africa Qualification Round 2010

by Nico Heid on Mon, 04/26/2010 - 15:49
in

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.

  1. for (int i = 0; i < items.size(); i++) {
  2.                         for (int j = i + 1; j < items.size(); j++) {
  3.  
  4.                                 // is this the right shopping?
  5.                                 int newSum = items.get(i) + items.get(j);
  6.  
  7.                                 if (newSum == credit) {
  8.                                         return "Case #" + caseNr + ": " + (i + 1) + " " + (j + 1);
  9.                                 }
  10.                         }
  11.  
  12. }
Read more

Christian Harms's picture

TOP 7 Exceptions in my google app engine described

by Christian Harms on Sat, 11/21/2009 - 19:40
in

After running the IP-geolocation application in the google app engine some weeks I gained some experience while fetching data and saving into the storage. Looking at the logs with the dash board some interesting errors appeared and that's why I write this article as a notepad for me (or for other python developers). If possible python snipplets will solve the problem cases of errors like "ApplicationError: 5" or "CapabilityDisabledError".Read more

Nico Heid's picture

Running a Java Wicket Application in the Google App Engine

by Nico Heid on Thu, 04/30/2009 - 23:00
in

The Google App Engine (GAE) is a wonderful playground for your apps, especially when you have no server at hand. It gives you everything you need for free, up to a certain limit. As I happened to be a Java developer it became really interesting when the GAE started supporting Java. You have to register for a GAE account and then apply for Java to be activated. There is a small waiting time but there still seem to be open slots.

As I'm working with Apache Wicket at the moment I thought it would be a nice idea to give you everything you need to get started with development with the GAE and Wicket as your frontend. So in the following lines we will set up a minimal Java / Wicket application and deploy it into the GAE.Read more

Syndicate content