Solutions for the google code jam 2012 qualify round

Christian Harms's picture

Google Code Jam 2012 started this weekend and this years qualification round was simpler than other years.

Problem 1 - Speaking in Tongues

The first exercise is a character mapping problem. You will get some gibberish input and have to encode it to normal english sentences.


gibberish: ejp mysljylc kd kxveddknmc re jsicpdrysi
ready: our language is impossible to understand

And there was only the small data set (with many tries to solve it) available. Ok, looks like a classical problem and I start thinking to build a solution with counting common english characters or iterate over all permutation to find words (from an english dictionary).

I was wondering after reading the three-line-example! You can manually fill out the complete mapping table and you have no hassle with permuting over the missing characters! The python solution has the mapping table and use the build-in function translate.

  1. import string, sys
  2.  
  3. input = file(sys.argv[1]).readline
  4.  
  5. trans = string.maketrans("ynficwlbkuomxsevzpdrjgthaq",
  6.                          "abcdefghijklmnopqrstuvwxyz")
  7. for case in range(int(input())):
  8.     print "Case #%d: %s" % (case+1,
  9.                             input().strip().translate(trans))

Problem 2 - Dancing With the Googlers

The second problem was interesting - here the problem description: You're watching a show where Googlers (employees of Google) dance, and then each dancer is given a triplet of scores by three judges. Each triplet of scores consists of three integer scores from 0 to 10 inclusive. The judges have very similar standards, so it'ssurprising if a triplet of scores contains two scores that are 2 apart. No triplet of scores contains scores that are more than 2 part.

For example: (8, 8, 8) and (7, 8, 7) are not surprising. (6, 7, 8) and (6, 8, 8) are surprising. (7, 6, 9) will never happen. The total points for a Googler is the sum of the three scores in that Googler's triplet of scores. The best result for a Googler is the maximum of the three scores in that Googler's triplet of scores. Given the total points for each Googler, as well as the number of surprising triplets of scores, what is the maximum number of Googlers that could have had a best result of at least p?

How to identify the highest values of a “not surprising” and “surprising” triple? Simply remember the MODULO operator.

  1. def maxNotSurprising(n):
  2.     b = n / 3
  3.     #1: 0+0+1
  4.     #2: 0+1+1
  5.     if n%3>0:
  6.         return b+1
  7.     #0+0+0
  8.     return b
  9.  
  10. def maxSurprising(n):
  11.     b = n / 3
  12.     #2: 0+0+2
  13.     if n%3==2:
  14.         return b+2
  15.     #1: 0+1+0
  16.     if n%3==1:
  17.         return b+1
  18.     #3: 0+1+2
  19.     if n%3==0 and n>0:
  20.         return b+1
  21.     #0: 0+0+0
  22.     return b

And the result script has to check if there are surprising triples left and count the p-hits.

  1. import sys
  2. input = file(sys.argv[1])
  3.  
  4. def solve(s, p, ti):
  5.     c = 0
  6.     for t in ti:
  7.         maxNot = maxNotSurprising(t)
  8.         maxSur = maxSurprising(t)
  9.         if s>0 and maxSur>maxNot and maxSur>=p and maxNot= p:
  10.                 c+=1
  11.                 s-=1
  12.         else:
  13.             if maxNot>=p:
  14.                 c+=1
  15.     return c
  16.  
  17. for case in range(int(input.readline())):
  18.     values = [int(x) for x in input.readline().split()]
  19.     print "Case #%d: %d" % (case+1, solve(values[1], values[2], values[3:]))

Problem 3: Recycled Numbers

The third exercise is a number crunching problem and looks like my perfect number search article.

Problem description: A pair of distinct positive integers (n, m) is recycled if you can obtain m by moving some digits from the back of n to the front without changing their order. For example, (12345, 34512) is a recycled pair since you can obtain 34512 by moving 345 from the end of 12345 to the front. Note that n and m must have the same number of digits in order to be a recycled pair. Neither n nor m can have leading zeros.

First we need to generate all rotated variants (and no doubles). I calculated it as integers - the solution by rotating character on a string is possible too (but slower). My fault on the large data set was calculation the digits with the logarithm function ... I got a float rounding error. int(math.log(1000,10)) was not 3!

  1. def digits(n):
  2.     #return int(math.log(n,10))
  3.     d=0
  4.     while n>9:
  5.         n/=10
  6.         d+=1
  7.     return d
  8.  
  9. def variants(n):
  10.     d = digits(n)
  11.     f = 10**d
  12.     v = set([n])
  13.     for x in range(d):
  14.         n = f*(n%10)+n/10
  15.         v.add(n)
  16.     return v

I had no better idea than iterating over all numbers and checking the condition for every variant.

Condition: Given integers A and B with the same number of digits and no leading zeros, how many distinct recycled pairs (n, m) are there with A ≤ n < m ≤ B?

  1. def check(a, b):
  2.     c = 0
  3.     for n in range(a, b):
  4.         for m in variants(n):
  5.             if m > n and m <= b:
  6.                 c+=1
  7.     return c

This is a non-perfect solution and does run 6 minutes on the large data set (on my old PC)! Puh - 8 minutes with downloading and uploading was a brief timespan.

Problem 4: Hall of Mirrors

The suggested time of two hours was over after solving three problems - so I skipped the hardest and last problem.

Give some comments on pages/articles who solved this problem or other/better solutions for the first three problems.

And check the language statistics for the qualification round 2012!

Other problems solved

Check other our articles about other google code jam problems: