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!

## 2 comments:

Thanks for posting the problems as I forgot to sign up. I worked out a python solution for the other one this afternoon and did a short writeup.

Good luck in the semi-finals.

hey, I got the same question. I also used brute force and it doesn't work with the larger matrices.

oh, btw, python is my favorite language too :)

cheers

Post a Comment