Codejam 2006 qualification round

I'm pleased that I made it into the round of 1000 in Google's Codejam. The Python support was much appreciated!

(Actually, I'd be curious what the breakdown was by language of the contestants and qualifiers. I have no real stats but from the 50+ submissions I glanced at, all C#, Java, and C++, I would guess that topcoder's "Python might be too slow" disclaimer scared a lot of people away from Python. Or, like VB.NET, it just isn't that popular with this group. The ignomy!)

I solved the 250 pt problem (problem set 5) very quickly, which is good because I didn't end up solving the 750 pt one at all. The 250 pt problem was

You are given a tuple (integer) f that describes a set of values from a function f. The x-th element (zero-indexed) is the value of f(x). The function is not convex at a particular x value if there exist y and z values such that y < x < z, and the point (x, f(x)) lies strictly above the line between points (y, f(y)) and (z, f(z)) in the Cartesian plane. All x, y, and z values must be between 0 and n-1, inclusive, where n is the number of elements in f. Return the number of places where f is not convex.

Here was my brute force solution:

class point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

def convex(x, f):
    fx = f[x]
    for y in xrange(x):
        fy = f[y]
        for z in xrange(x + 1, len(f)):
            fz = f[z]
            if above(point(x, fx), point(y, fy), point(z, fz)):
                return True
    return False

def above(x, y, z):
    slope = (z.y - y.y) / float(z.x - y.x)
    lineatx = y.y + slope * (x.x - y.x)
    return x.y > lineatx

class ConvexityIssues:
    def howMany(self, f):
        return sum(int(convex(x, f)) for x in xrange(len(f)))

The other problem was more interesting. A brute-force solution here is just too slow for a 16x16 matrix (i.e., 16! = 20922789888000 permutations) and I couldn't figure out the pattern in time to construct a better algorithm.

The permanent of a nxn matrix A is equal to the sum of A[1][p[1]] * A[2][p[2]] * ... * A[n][p[n]] over all permutations p of the set {1, 2, ... , n}.

You will be given a tuple (string) matrix, where each element contains a single space delimited list of integers. The jth integer in the ith element represents the value of A[i][j]. Return the int represented by the last four digits of the permanent of the given matrix.

There's also a discussion thread about this question for the curious.

This is probably as far as my CodeJam career goes since I don't really have time to practice for the next round, and this part of my brain is clearly rusty. Still, I enjoy it, especially in Python. Thanks, Google!