Skip to main content

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!

Comments

Anonymous said…
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.
Anonymous said…
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

Popular posts from this blog

Why schema definition belongs in the database

Earlier, I wrote about how ORM developers shouldn't try to re-invent SQL . It doesn't need to be done, and you're not likely to end up with an actual improvement. SQL may be designed by committee, but it's also been refined from thousands if not millions of man-years of database experience. The same applies to DDL. (Data Definition Langage -- the part of the SQL standard that deals with CREATE and ALTER.) Unfortunately, a number of Python ORMs are trying to replace DDL with a homegrown Python API. This is a Bad Thing. There are at least four reasons why: Standards compliance Completeness Maintainability Beauty Standards compliance SQL DDL is a standard. That means if you want something more sophisticated than Emacs, you can choose any of half a dozen modeling tools like ERwin or ER/Studio to generate and edit your DDL. The Python data definition APIs, by contrast, aren't even compatibile with other Python tools. You can't take a table definition

Python at Mozy.com

At my day job, I write code for a company called Berkeley Data Systems. (They found me through this blog, actually. It's been a good place to work.) Our first product is free online backup at mozy.com . Our second beta release was yesterday; the obvious problems have been fixed, so I feel reasonably good about blogging about it. Our back end, which is the most algorithmically complex part -- as opposed to fighting-Microsoft-APIs complex, as we have to in our desktop client -- is 90% in python with one C extension for speed. We (well, they, since I wasn't at the company at that point) initially chose Python for speed of development, and it's definitely fulfilled that expectation. (It's also lived up to its reputation for readability, in that the Python code has had 3 different developers -- in serial -- with very quick ramp-ups in each case. Python's succinctness and and one-obvious-way-to-do-it philosophy played a big part in this.) If you try it out, pleas

A review of 6 Python IDEs

(March 2006: you may also be interested the updated review I did for PyCon -- http://spyced.blogspot.com/2006/02/pycon-python-ide-review.html .) For September's meeting, the Utah Python User Group hosted an IDE shootout. 5 presenters reviewed 6 IDEs: PyDev 0.9.8.1 Eric3 3.7.1 Boa Constructor 0.4.4 BlackAdder 1.1 Komodo 3.1 Wing IDE 2.0.3 (The windows version was tested for all but Eric3, which was tested on Linux. Eric3 is based on Qt, which basically means you can't run it on Windows unless you've shelled out $$$ for a commerical Qt license, since there is no GPL version of Qt for Windows. Yes, there's Qt Free , but that's not exactly production-ready software.) Perhaps the most notable IDEs not included are SPE and DrPython. Alas, nobody had time to review these, but if you're looking for a free IDE perhaps you should include these in your search, because PyDev was the only one of the 3 free ones that we'd consider using. And if you aren