## Google Code Jam 2012 – Qualification Round

I’ve passed the Qualification Round of Google Code Jam 2012. I’ve learned, that I am not allowed to submit the large dataset after the first 8 minutes.

18,365 programmers took part in this contest. 15,692 had at least 20 points and advanced to the First Rounds.

These are my solutions:

## Problem A: Speaking in Tongues

This one was easy. It’s a simple substitution cipher:

#!/usr/bin/python
# -*- coding: utf-8 -*-

def decode(ciphertext, key="ynficwlbkuomxsevzpdrjgthaq",
alphabet="abcdefghijklmnopqrstuvwxyz"):
dic={}
for i in range(0,len(key)):
dic[key[i]] = alphabet[i]

plaintext=""
for l in ciphertext:
if l in dic:
l=dic[l]
plaintext+=l

return plaintext

if __name__ == "__main__":
testcases = input()

for caseNr in xrange(0, testcases):
cipher = raw_input()
print("Case #%i: %s" % (caseNr+1, decode(cipher)))

A minimalistic python solution for this one was suggested by Niklas B. He makes use of Lambdas, str.translate() and str.maketrans():

#!/usr/bin/python
# -*- coding: utf-8 -*-

import string as s

testcases = input()

key = "ynficwlbkuomxsevzpdrjgthaq"
decode= lambda c: s.translate(c, s.maketrans(key, s.ascii_lowercase))

for i in range(0, testcases):
print decode(raw_input())

## Problem B: Dancing With the Googlers

#!/usr/bin/python
# -*- coding: utf-8 -*-

from math import ceil, floor

def line2intlist(line):
list = line.split(' ')
numbers = [ int(x) for x in list ]
return numbers

def getDist(points, isSurprising=False):
p = floor(points / 3.0)
trip = [p, p, p]
if 3*p < points:
trip[0] += 1
if (3*p + 1) < points:
trip[1] += 1

trip.sort(reverse=True)

if isSurprising and (trip[1] == trip[0]) and trip[1] > 0:
trip[1] -= 1
trip[0] += 1
trip.sort(reverse=True)

return trip

mg = 0
surp = 0
for pi in points:
trip = getDist(pi, True)
if ceil(pi/3.0) >= p:
mg += 1
elif trip[0] >= p:
surp += 1

mg += min(surp, surprising)

return mg

if __name__ == "__main__":
testcases = input()

for caseNr in xrange(0, testcases):
originalList = line2intlist(raw_input())
surprising = originalList[1]
p = originalList[2]
points = originalList[3:]

## Problem C: Recycled Numbers

The small dataset of this one was easy, but I had to change my code a bit to make it work for the large dataset. Sadly, I didn’t know that I only have 8 minutes to get it work

I’ve tried cPickle for the 2,000,000 list. It took 128.7 MB and 1 minute 6.287s for the large data set after it was pickled. Without pickling it took 1 minute 31.900s.

#!/usr/bin/python
# -*- coding: utf-8 -*-

try:
import cPickle as pickle
except:
import pickle

def line2intlist(line):
list = line.split(' ')
numbers = [ int(x) for x in list ]
return numbers

def binomialCoefficient(n, k):
if k < 0 or k > n:
return 0
if k > n - k: # take advantage of symmetry
k = n - k
c = 1
for i in range(k):
c = c * (n - (k - (i+1)))
c = c // (i+1)
return c
#return n * (n - 1) / 2

def rot(num, rot):
num = str(num)
num = num[len(num)-rot:len(num)] + num[0:len(num)-rot]
return int(num)

def getRotList(num):
""" Only return bigger rotated ones """
rotList = [num]
for i in xrange(1, len(str(num))):
tmp = rot(num, i)
if tmp not in rotList and len(str(tmp)) == len(str(num)):
rotList.append(tmp)
return sorted(rotList)

def inBorder(rotations, A, B):
count = 0
for el in rotations:
if A <= el and el <= B:
count += 1
return count

def recycled(A, B, liste):
pairs = 0
minList = range(0, B+1)

for tmpList in liste[A:B+1]:
if minList[tmpList[0]]:
nrInBorder = inBorder(tmpList, A, B)
pairs += binomialCoefficient(nrInBorder, 2)
minList[tmpList[0]] = 0

return pairs

if __name__ == "__main__":
liste = []
try:
liste = pickle.load(open( "save.p", "rb" ))
except IOError:
for i in xrange(0, 2000001):
tmp = getRotList(i)
liste.append(tmp)
pickle.dump(liste, open( "save.p", "wb" ))

testcases = input()

for caseNr in xrange(0, testcases):
A, B = line2intlist(raw_input())
print("Case #%i: %i" % (caseNr+1, recycled(A, B, liste)))

## Problem D: Hall of Mirrors

This one was very hard. I had some ideas, but none of them seemed to work.

This is a solution based on the solution of “dwenzel”. At the moment, I’ve only made some comments and broke some lines to let them fit into my blog. This solution needs about 2 minutes 42 seconds for the small input set and 2 minutes 12 seconds for the large input set.

You might also be interested in the official Contest Analysis with some hints to this challenge.

#!/usr/bin/python
# -*- coding: utf-8 -*-

from math import floor, ceil, sqrt

precision = 0.01

def line2intlist(line):
list = line.split(' ')
numbers = [ int(x) for x in list ]
return numbers

def seeReflection(x, v, m, d):
cur_y = x[0]
cur_x = x[1]
vy = v[0]
vx = v[1]
dist = 0
while dist <= d + precision:
if abs(cur_x - x[1]) < precision and \
abs(cur_y - x[0]) < precision and dist > 0:
return True

if vy == 0:
if vx < 0:
cur_x -= 0.5
else:
cur_x += 0.5
if abs(cur_x - round(cur_x)) < precision:
tmp = int(floor(cur_y))
if vx < 0 and m[tmp][int(round(cur_x) - 1)] == 1:
vx = -vx
elif vx > 0 and m[tmp][int(round(cur_x))] == 1:
vx = -vx
dist += 0.5
elif vx == 0:
if vy < 0:
cur_y -= 0.5
else:
cur_y += 0.5
if abs(cur_y - round(cur_y)) < precision:
tmp = int(floor(cur_x))
if vy < 0 and m[int(round(cur_y) - 1)][tmp] == 1:
vy = -vy
elif vy > 0 and m[int(round(cur_y))][tmp] == 1:
vy = -vy
dist += 0.5
else:
# Find how far is the next time we hit something
# .0 or .5
if vy < 0:
dy = cur_y - floor(cur_y)
else:
dy = ceil(cur_y) - cur_y
if dy > 0.5 + precision:
dy -= 0.5
elif dy < precision:
dy += 0.5

if vx < 0:
dx = cur_x - floor(cur_x)
else:
dx = ceil(cur_x) - cur_x
if dx > 0.5 + precision:
dx -= 0.5
elif dx < precision:
dx += 0.5

# See which will come up first
ty = dy / abs(vy)
tx = dx / abs(vx)
if ty > tx:
t = tx
else:
t = ty

dy = vy * t
dx = vx * t
cur_y = cur_y + dy
cur_x = cur_x + dx
dist += sqrt(dy * dy + dx * dx)

roundy = round(cur_y)
roundx = round(cur_x)
ybounce = False
xbounce = False
if abs(cur_y - roundy) < precision and \
abs(cur_x - roundx) < precision:
# Case we're at a corner
neighbors = []
intx = int(roundx)
inty = int(roundy)
neighbors.append(m[inty - 1][intx - 1] % 2)
neighbors.append(m[inty - 1][intx] % 2)
neighbors.append(m[inty][intx] % 2)
neighbors.append(m[inty][intx - 1] % 2)
sum = 0
for neighbor in neighbors:
sum += neighbor
if sum == 1:
if vy < 0:
nexty = inty - 1
else:
nexty = inty
if vx < 0:
nextx = intx - 1
else:
nextx = intx
if m[nexty][nextx] == 1:
return False
elif sum == 3:
vy = -vy
vx = -vx
elif sum == 2:
if neighbors[0] == neighbors[1]:
vy = -vy
elif neighbors[0] == neighbors[3]:
vx = -vx
elif abs(cur_y - roundy) < precision:
# Case we're middle of a top/bottom edge
if vy < 0:
inty = int(roundy - 1)
else:
inty = int(roundy)
intx = int(floor(cur_x))
if m[inty][intx] == 1:
vy = -vy
elif abs(cur_x - roundx) < precision:
# Case we're middle of a top/bottom edge
if vx < 0:
intx = int(roundx - 1)
else:
intx = int(roundx)
inty = int(floor(cur_y))
if m[inty][intx] == 1:
vx = -vx
return False

def getMap(H, W):
map = []
for el in xrange(0, H):
line = raw_input()
tmp = []
for char in line:
if char == '.':
tmp.append(0)
elif char == '#':
tmp.append(1)
else:
tmp.append(2)
map.append(tmp)
return map

def process_case(m, H, W, D):
vectors = set()
ratios = set()
for i in range(D + 1):
for j in range(1, D + 1):
if i <= j and i*i + j*j <= D * D:
ratio = float(i) / float(j)
if ratio not in ratios:
x = None
for i in range(H):
for j in range(W):
if x == None and m[i][j] == 2:
x = (i + 0.5, j + 0.5)
count = 0
for vector in vectors:
if seeReflection(x, vector, m, D):
count += 1
return count

if __name__ == "__main__":
testcases = input()
for caseNr in xrange(0, testcases):
H, W, D = line2intlist(raw_input())
map = getMap(H, W)
print("Case #%i: %i" % (caseNr+1, process_case(map, H, W, D)))

### 4 Responses to “Google Code Jam 2012 – Qualification Round”

1. Niklas B. says:

The first one’s easy

>>> key = “ynficwlbkuomxsevzpdrjgthaq”
>>> decode = lambda c: string.translate(c, string.maketrans(key, string.ascii_lowercase))

2. Niklas B. says:

Man, I really like that stuff: https://gist.github.com/2417788 Can you make it even shorter? We should start an obfuscated Python contest!

3. A says:

Check out this solution for Hall of Mirrors Small input in 25 lines of python: