"When a Fuun has suffered a severe crash abnormal RNA may be produced. This 'hiccup' RNA is nothing to worry about and doesn't serve any purpose for morphing. It's not entirely clear what the real purpose of the RNA is, but it does seem to be related to the morphing process, because peculiar patterns have been observed. For example, the RNA code CFPICFP occurs very often and seems to indicate a small part of the morphing process is done. There are also other RNA codes, all starting with a C, that most likely indicate the start of a morphing process. Their exact meaning hasn't been figured out, though."

(There were 34 participants.)

It seems like last year's contest was just yesterday, but it turns out a whole year has passed. This year's Berkeley Programming Contest was held last weekend and I again participated. It didn't feel like a very eventful contest, but I did learn the origin of the phrase "[to] follow suit." (Apparently it comes from card games in which one is required to play a card of the same suit as some other card.)

I wonder whether problem number five was inspired by Burning Man, whose city is laid out on such a circular grid. I believe the crux of the solution to that one is that you're better off going through the city center if your destination is more than 2 radians away; otherwise you should just go around.

My C/C++ programming has gotten pretty rusty!

The Berkeley Programming Contest was today and I participated from my secret underground lair. Overall people seemed to do very well. In particular cs61a-nq—whose account name indicates that he or she is probably a freshman—solved six problems, which is very impressive.

I think the relative frequency of solutions may be indicative of the Berkeley CS curriculum. The most-solved problem, number 3, has a simple recursive solution of the sort you're likely to see in CS 61A. I'm surprised that the "longest common subsequence of five strings" problem—which has a standard solution, but one somewhat annoying to code up—had nearly twice as many solutions as number seven, which was fairly trivial.

I submitted acceptable solutions to the three problems indicated with asterisks, which is good enough for something like 10th place. (haha)

If I remember correctly, the first programming contest problem I attempted was number eight on the 1999 Berkeley Programming Contest. The problem reads:

You are given a base-36 numeral (the digits are 0-9, a-z, with a worth 10, b 11, etc.) and told that it comes from the set of all numbers having the same digits (that is, the same number of each digit the given number has). We allow leading 0s. You are to print out the next number from that set (in ascending order). For example, given 03snd3fk5ee2, you should print 03snd3fke25e.

"I can do that," I thought, and proceeded to implement the naïvest of naïve algorithms: my program iterated through base36 numbers, counting up from the number given as input, each time checking whether the digits of the current number were a permutation of the input digits.

My program worked on the example input. I submitted it, waited expectantly for a "success!" email to come back, and was crestfallen at the response: "failure! time limit exceeded." Lesson number one: while the sample inputs are often simple, the testing inputs may be complex or even pathological, exercising special cases not observed with the sample inputs.

The input leading to failure was, if I recall correctly, "xylophone." And that, in a flash, is how I learned about algorithmic complexity. Brute-force guess-and-check is just not a tractable approach for most problems.

A moment with paper and pencil working out the problem reveals a simple, elegant algorithm. This is a good lesson for the programming contests: before rushing to write code, solve some sample cases by hand. I think this is a nice little problem, a fun thing to try implementing in novel languages.

Nobody solved problems two or seven in the 2005 Berkeley Programming Contest (pdf with problem descriptions). There were 24 correct solutions to problem eight (which has a simple closed-form solution), 13 solutions to each of problems one and five, eight correct solutions to each of three and six, and two solutions to problem number four. The two unsolved problems were, in brief:

2. Given a description of a circuit consisting of N outputs connected to N inputs via a collection of XOR gates with some inputs inverted, and a set of outputs of that circuit, find a consistent set of inputs that will produce this output.

7. Reduce a set of ordered pairs by finding subsets that may be written as cartesian products.

I believe I have a good algorithm for number (2), but not yet for number (7). I will post about (2) in another post. In the meantime, I'm curious if anyone else has ideas about these two problems. (I enjoy working on these contest problems because they are so nicely bite-sized. After thinking up an algorithm you have the other fun task of implementing it as succinctly as possible.)