Google Code Jam language usage

[Bearophile]

> (There can be ways to speed up this Python code, I have not tried to
> use a 1D matrix with shifts to find the right starting of the rows as
> in C, and often in such dynamic programming algorithms you can just
> keep 2 rows to avoid storing the whole dynamic matrix, this saves
> memory and speed up code because there are less cache misses.


It was easy to do, running time about 0.13 seconds:


from array import array

def main():
    b = "welcome to code jam"
    len_b = len(b)
    di = array('l', [0]) * len_b
    dim1 = array('l', [0]) * len_b
    for t in xrange(int(raw_input())):
        a = raw_input()
        for j in xrange(len_b): # set to 0
            di[j] = 0
            dim1[j] = 0
        if a[0] == b[0]:
           dim1[0] = 1
        for i in xrange(1, len(a)):
            for j in xrange(len_b): # set to 0
                di[j] = 0
            di[0] += dim1[0]
            if b[0] == a[i]:
                di[0] += 1
            for j in xrange(1, len_b):
                di[j] += dim1[j]
                if b[j] == a[i]:
                    di[j] += dim1[j - 1]
                di[j] %= 10000
            di, dim1 = dim1, di
        print "Case #%d: %04d" % (t+1, dim1[len_b - 1])

import psyco; psyco.full()
main()

Bye,
bearophile