Home ›

The rotate google contest in 15 lines

Christian Harms's picture
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)
  15.     if search(k*"B", s) or search(reB%(n-1), s) or search(reB%n, s) or search(reB%(n+1), s):
  16.         result+=1
  17.  
  18.     #find one of the 4 variants: horiz, verti, slash, backslash for Red
  19.     reR = "(R.{%%d}){%d}R" % (k-1)
  20.     if search(k*"R", s) or search(reR%(n-1), s) or search(reR%n, s) or search(reR%(n+1), s):
  21.         result= result+2
  22.     print "Case #%d: %s" % (case, ["Neither", "Blue", "Red", "Both"][result])

There are 15 effective lines of code for the solution. And some lines are used for imports or reading from the input file (comments and spacer not counted) - cool?

handling the gravitation

To understand the code read the problem description in nicos article or in the google code contest page. I will describe now the two steps for the solution. First the play field have to sorted like a gravitation to the right. All dot character are handled like spaces and the capital letters goes to the right border.

We start with a n by n matrix:

  1. ..R          ..R
  2. .R.   ->     ..R  
  3. R.B          .RB

To remove the dots simple replace it with nothing as a standard string manipulatin method. To fill it from the left use the common used string formating well know from printf.

  1. newLine = “%3s” % lin.replace(“.”, “”)

To do this with the length n use this obscure-looking multi step format string:

  1. newLine = “%%%ds” % n % line.replace(“.”, “”)

And to do this with a complete list of lines use a list comprehension (read more about functional programming in python).

  1. lines = map(lambda x:"%%%ds"%n%(x.replace(".","")), lines)

This is done in line 10 in the example (with joining to one string).

find the winner

Second part is to find the k=4 characters in a line:

  1. RBBBB
  2. _RBBB   -> "RBBBB#_RBBB#__RBB#___RB"
  3. __RBB
  4. ___RB

I concat all lines to one string to find the four different directions with regular expressions: “RBBBB-_RBBB-__RBB-___RB”

  • The horizontal line is easy: /BBBB/ or with k: /B{4}/
  • the vertical line can found by 4 B’s and n characters (one line up): /B.{5}B.{5}B.{5}B/ or shorter: /(B.{5}){3}B/
  • the backslash line is the same like the vertical line, only with n+1 spaces
  • the slash line is the same like the vertical line, only with n-1 spaces

I prepared the regular pattern with k: reB = "(B.{%%d}){%d}B" % (k-1) and used the multi step format string for the different pattern strings (see example above in line 15).

That’s all!

Comments

Solutions for the google code jam 2012 qualify round | unite's picture
Pingback
Solutions for the google code jam 2012 qualify round | unite (not verified) - Sun, 04/15/2012 - 22:17

[...] The rotate problem from the Round 1A 2010 from nico and my self [...]