Google Code Jam 2012 - My solutions for the qualification round

I participated and managed to find reasonable solutions for A,B C en D-small. I code in Python, as its compactness and focus on sets, dicts and lists are great for coding challenges like these.

They read input from stdin, so a command like

cat input | python program.py

prints the output to your terminal.

A - Speaking in Tongues

speaking_in_tongues.py (gist)

english    = "zq our language is impossible to understand there are twenty six factorial possibilities so it is okay if you want to just give up"
googlerese = "qz ejp mysljylc kd kxveddknmc re jsicpdrysi rbcpc ypc rtcsra dkh wyfrepkym veddknkmkrkcd de kr kd eoya kw aej tysr re ujdr lkgc jv"
mapping = dict(zip(googlerese, english))
lines = map(lambda x: x.strip(), stdin.readlines())
for i in range(1, len(lines)):
    print "Case #%s: %s" % (i, "".join([mapping[char] for char in lines[i]]))

B - Dancing With the Googlers

dancing.py (gist)

def rline():
    return stdin.readline().rstrip()

for i in range(int(rline())):
    data = map(int, rline().split())
    googlers = data[0]
    surprising = data[1]
    p = data[2]
    scores = data[3:]
    num = 0
    for score in scores:
        if score == 0 and p > 0:
            pass
        elif score >= 3*p - 2:
            num += 1
        elif (score == 3*p - 3 or score == 3*p - 4) and surprising > 0:
            surprising -= 1
            num += 1
    print "Case #%s: %s" % (i+1, num)

C - Recycled Numbers

recycled.py (gist)

from sys import stdin
def rline():
    return stdin.readline().rstrip()

for l in range(int(rline())):
    (n,m) = map(int, rline().split())
    total = 0
    length = len(str(n))
    for k in range(n, m+1):
        s1 = str(k)
        total += len([x for x in set([int(s1[n:]+s1[:n]) for n in range(length)]) if x > k and x <= m])
    print "Case #%s: %s" % (l+1, total)

D - Hall of Mirrors

I'm not proud of this solution, but it got the job done. It's not elegant and it only works for the small set. (The only mirrors are the ones on the sides).

It works by tiling mirrored versions of the original map to cover.

hall.py (gist)

from sys import stdin
from math import ceil, sqrt
def rline():
    return stdin.readline().rstrip()
def sign(p):
    if p < 0:
        return -1
    elif p > 0:
        return 1
    else:
        return 0

def same_quadrant((x,y), (p,q)):
    return sign(x) == sign(p) and sign(y) == sign(q)

def already_in_doubles((x,y)):
    for (p,q) in non_doubles:
        if same_quadrant((x,y),(p,q)):
            if x*q == y*p:
                return True
    return False

for l in range(int(rline())):
    (h,w,d) = map(int, rline().split())
    field = [rline()[1:-1] for i in range(int(h))]
    field = field[1:-1]
    h = h-2
    w = w-2
    h_fields = d/h + 1
    w_fields = d/w + 1
    bigfield = []
    for hf in range(-h_fields, h_fields + 1):
        for sub_h in range(h):
            row = []
            for wf in range(-w_fields, w_fields + 1):
                for sub_w in range(w):
                    if hf % 2 == 1:
                        y = h - sub_h - 1
                    else:
                        y = sub_h
                    if wf % 2 == 1:
                        x = w - sub_w - 1
                    else:
                        x = sub_w
                    cell = field[y][x]
                    if cell == 'X' and hf == 0 and wf == 0:
                        cell = 'O'
                    row.append(cell)
            bigfield.append("".join(row))
    mirrored = []
    for y in range(len(bigfield)):
        for x in range(len(bigfield[y])):
            cell = bigfield[y][x]
            if cell == 'X':
                mirrored.append((x,y))
            elif cell == 'O':
                self = (x,y)
    mirrored = map(lambda (x,y): (x-self[0], y-self[1]), mirrored)
    mirrored = filter(lambda (x,y): x*x + y*y <= d*d, mirrored)
    non_doubles = []
    for (x,y) in mirrored:
        if not(already_in_doubles((x,y))):
            non_doubles.append((x,y))

    print "Case #%s: %s " % (l+1, len(non_doubles))