Posts Tagged contest

Google Code Jam: I advanced to Round 2!

September 12, 2009 at 1:25 pm · Filed under software ·Tagged

Last night I participated in Round 1 of the 2009 Google Code Jam.  I thought all of the questions were difficult, but I squeaked by and advanced to Round 2.

I first worked on the Multi-base happiness problem.  I had never heard of happy numbers before, and wasn’t sure how to determine that a number was unhappy.  How many times should I iterate summing the squares before stopping?  Fortunately Wikipedia told me the remarkable property that the iterations either reduce to 1 or enter a cycle.  The other key to this problem is memoization.

I skipped Crossing the Road and tackled the Collecting Cards problem.  I first coded up a simulation.  This failed to generate results with sufficient precision.  I actually succeeded in coding up an alternate solution, but I didn’t submit it in time.  My solution walks down the expectation calculation, passing along the conditional probability of reaching each point.  This works fine, but I feel there must exist a super clean solution for this problem.

In any case, I was fortunate enough to pass on to the next round, where I’ll surely be destroyed.

Leave a Comment

Analysis of Google Code Jam Qualifier Results

September 6, 2009 at 12:03 am · Filed under Programming Languages, software ·Tagged , , ,

I wrote a quick Python script to pull down all of the results from the qualifying rounds of Google Code Jam from 2008 and 2009.  I have put the rank and time of each submitted solution for all participants in these two Google Spreadsheets:

I also put a collection of summary statistics in this Google Spreadsheet.

Here are some conclusions drawn from these data:

  1. The number of participants increased by 1,449 people in 2009, a 20% increase.
  2. There were 2,572 people who participated both years.  This means 36% of the 2008 participants came back for more.
  3. The 2008 Qualifier had more difficult problems.  After normalizing the point totals (2008 had a max total of 75 points but 2009 had a max of 99 points), the average score was 15% higher in 2009.
  4. Problem C in 2008 was extremely hard.  Only 14% of the participants solved Problem C with the small data set, and only 9% solved Problem C with the large data set.
  5. The large data set for Problem C in 2009 was hard for many people.  Only 36% of people solved it.  Furthermore, of the people who solved the small data set, only 57% of those were able to solve the large data set.
  6. People worked roughly the same amount of time both years.  The 2009 times are all slightly larger, but the round was also extended by 2 hours because of technical problems early in the round.
  7. On average, for each participant, there is about a 3.5 hour gap between the submission time of the first solution and the submission time of the last solution.  Of course some people (like me) probably choose to tackle the problems whenever they found free moments during their day.

If people are interested, I’ll post my code and all the data somewhere.

Leave a Comment

Google Code Jam 2009 Qualifier

September 3, 2009 at 4:45 pm · Filed under Python, software ·Tagged ,

I finished all 3 problem in this year’s Google Code Jam.  I found them to be much easier than last year’s qualifier.  (Although last year a friend told me about the qualifier less than two hours before it ended, so I was rushed).

Last year I wrote my solutions in Haskell because I was learning the language.  This year I wasn’t so adventurous; I wrote my solutions using Python.

For the Alien Language challenge, I encoded the lexicon using a tree built with python dictionaries.  I imagine this could be done using a regex, but I haven’t thought that through.

For the Watersheds challenge, I simply built two 2d arrays: one to hold the topology and the other to hold the labels.  From each coordinate on the map, I followed the flow down hill until I reached a sink or reached a labeled coordinate.  This memoization ensures that you only visit each node once.

For the Welcome to Code Jam challenge, I memoized a mapping from (string_index, substring) to the number of times that substring can be completed starting at the index.  Again, this was straightforward.

I’m looking forward to seeing how other people solved each challenge.  I wonder how 16 year old Neal Wu made such quick work of the problems, solving all three in under 26 minutes.  That’s amazing.

Comments (6)

Follow

Get every new post delivered to your Inbox.