The first qualification round of the Google Code Jam just ended, and I managed to scrape through with two of the three problems solved in time. On the third, unfortunately, I failed to take into account the orders of magnitude of complexity, and my algorithm was not fast enough to solve the larger input case.

Since the round is now closed, I can publish the solutions I used without unfairly influencing the competition. (Don't read on if you want to figure it out for yourself, though. It's really fun to solve on your own.)

Problem 1: Snappers

The Snapper is a clever little device that, on one side, plugs its input plug into an output socket, and, on the other side, exposes an output socket for plugging in a light or other device.

When a Snapper is in the ON state and is receiving power from its input plug, then the device connected to its output socket is receiving power as well. When you snap your fingers -- making a clicking sound -- any Snapper receiving power at the time of the snap toggles between the ON and OFF states. [read on]

The beautiful simplicity of this problem is obvious as soon as you consider the pattern of switches on each clap:

Having established that the switches follow the progression of binary numbers, it is also clear what property the binary number must have for the light to be on: All switches must be switched on; the binary number (from the nth digit to the right) has to completely consist of ones. That means if you add one to the number, that pattern must consist of zeros.

It is possible to do all this using modulo arithmetic, but I thought using actual bitwise operators might be somewhat faster.

def snapper(n, k):
    # Add one to the number, AND it with the number "2^n-1", check for 0.
    return (k+1) & ((1<<n) - 1) == 0
 
def main():
    labels = ["OFF", "ON"]
    try:
        cases = xrange(1, int(raw_input())+1)
        for case in cases:
            n, k = map(int, raw_input().split())
            print "Case #%d: %s" % (case, labels[snapper(n, k)])
    except ValueError:
        print "INVALID INPUT"
 
main()

Problem 2: Doomsday

On our planet, Jamcode IX, three Great Events occurred. They happened 26000, 11000 and 6000 slarboseconds ago. In 4000 slarboseconds, the amount of time since all of those events will be multiples of 5000 slarboseconds, the largest possible amount... and the apocalypse will come.

This one was a bit trickier. Obviously, you will immediately be thinking along the right lines of what is required here: Modulo arithmetic and greatest common divisors. Hope you have the Euclidean algorithm fresh in your mind (gcd a b = b ? (gcd b a%b) : a). However, it is not immediately clear what you need to do with those numbers. Clearly, 26000, 11000 and 6000 have nothing in common, divisor-wise, with 5000.

Naturally, the differences between these numbers do. You will find that regardless of the order of the numbers, the intervals between them have the same greatest common divisor - 5000. Even more, it can be shown that any group of numbers shares a remainder class for the greatest common divisor of their differences - 1000 in this case. The complement of this remainder class (4000) is the doomsday time we are looking for.

So the algorithm looks like this:

def doomsday(events):
    T = gcd_n(intervals(events))
    return -events[0] % T
 
# Absolute values of the intervals between N numbers.
def intervals(z):
    return [abs(a-b) for a, b in zip(z, z[1:])]
 
# Greatest Common Divisor of N numbers.
def gcd_n(z):
    # gcd(a, b, c) = gcd(gcd(a,b), c)
    return reduce(gcd_2, z)
 
# Greatest Common Divisor of 2 numbers.
def gcd_2(a, b):
    while b:
        a, b = b, a % b
    return a
 
def main():
    try:
        cases = xrange(1, int(raw_input())+1)
        for case in cases:
            line = map(int, raw_input().split())
            n, events = line[0], line[1:]
            assert n == len(events)
            print "Case #%d: %d" % (case, doomsday(events))
    except:
        print "INVALID INPUT"
            
main()

Problem 3: Theme Park

The roller coaster can hold k people at once. People queue for it in groups. Groups board the roller coaster, one at a time, until there are no more groups left or there is no room for the next group; then the roller coaster goes, whether it's full or not. Once the ride is over, all of its passengers re-queue in the same order. The roller coaster will run R times in a day.

This is the problem I didn't manage to solve in time. I had two implementations using the same approach, one in Haskell and one in Python. Both did not scale well, as the algorithm ran in linear time and the final input differed by orders of magnitude from what I had tested it with.

def rollercoaster(rides, size, queue):
    profit, aboard = 0, 0
    while rides > 0:
        i, aboard = 0, 0
        for x in queue:
            if aboard + x > size:
                break
            i, aboard = i + 1, aboard + x
        profit += aboard
        queue = queue[i:] + queue[:i]
        rides -= 1
    return profit
 
def main():
    cases = xrange(1, int(raw_input())+1)
    for case in cases:
        rides, size, queue_len = map(int, raw_input().split())
        queue = map(int, raw_input().split())
        assert queue_len == len(queue)
        print "Case #%d: %d" % (case, rollercoaster(rides, size, queue))
main()

Tesseract 2.0 is out. I haven't tried it yet, but I'm looking forward to it very much, as I've had no end of trouble trying to get the 1.04 beta to work. Especially under Linux - it just wouldn't compile.

I'm hoping this new version will make things a lot easier.

I've waited for this particular news for quite some time: Google has released their desktop search for Linux.

The number of reasons that are keeping me from running Linux as my main OS is quickly shrinking.

I just read a Google blog post which finally clears up what I always wondered about: Why am I getting no spam in my Gmail account?

Seriously, just about the only thing that slips past the filter these days is stock spam that is encoded into a hard to read image.

Apparently, it is possible to defeat spam with the right amount of dedication. And here I was thinking that the 200 daily spam messages in my barely-used Yahoo inbox were inevitable.

My visitor log shows me the referring pages, of course, and since I neither have a big audience of periodic readers nor other popular bloggers who link to me, most of these are Google searches.

In fact, the most frequent of those for the past few years has been for two images - one of the skyline of Houston, TX, and one of the Mt. Rushmore memorials - neither of which were ever on my site (I evilly hot-linked them) and neither of which are still available at their original site. Oh, and as an added bonus, the blog entry they were included in is over two years old and has been gone for over a year. So it seems that Google Image Search still needs some tweaking.

But I also get new queries. Some of those are quite funny, especially from the perspective of a "seasoned" search engine user. Common words strung up without any quotes to a full sentence is basically an "I'm Feeling Lucky" search.

Misspelled words and AOL slang in a question is even funnier.

Thus, I present exhibit c:

what r we supposed 2 eat

Note the "r" of R'lyeh, which is what brought me that far up.

I can only express my hope that the searcher was eventually able to find something more nutritious and less stringy than my blog...

... and Drupal.

Well, I installed the gsitemap module, which is so far only released for 4.7.x, but whose CVS repository already has a 5.x-compatible version... with a bit of meddling required.

Finally, I've been able to submit a sitemap and verification page for Google (that "google495953..." thing), and also look at the request logs to see what exactly Google requests from my site:

These are:

• google...html
• noexist_...html

Apparently, the noexist_ file is meant to return a 404, in order to check if the server returns a pseudo-404 page with code 404, which would make this check impossible.

So now I know more.

According to PC Advisor and numerous other sources on news.google.com, the Quaero project initiated by France and Germany is falling apart.

Quaero was intended to become the favored European search engine, in order to gain independency from Google (which I personally think is pointless, and this is coming from an anti-corporate European). Incidentally I found out today that the university I study in (RWTH Aachen) was one of the contributors in this project, which I didn't know before.

Anyway, Germany has pulled out of the cooperation, apparently turning its effort to another project they call "Theseus".

Most interesting is the reason for the falling-out. Apparently there is a difference in conceptions over what the search engine was actually supposed to do.

The French partners wanted Quaero to rank search pages by popularity, in a direct competition with Google (in fact, President Jacques Chirac spoke of "taking up the challenge" of American search engines).

The German partners apparently prefer to focus on a niche Google has stayed completely out of: Semantics. Obscure search engines like Clusty and formerly Northern Lights (before it turned into a database of paid content) have provided so-called "clustering" of search results for a long time.

The premise is simple: When you look for an ambiguous term, such as "golf", you may be looking either for a Volkswagen car or a sport, but rarely both at once.

Google requires you to make your search query more specific to exclude one or the other meanings (which is very easy once you've learned how to use it). Clustered search engines will give you two separate categories which can simply be clicked to narrow down search results - and each category already shows a few sample results, and an overall estimate for the number of results.

And it does this on the fly, for whatever term you enter.

This is done by analyzing the sites and finding certain words common to a lot of them - in our example, all the ones containing "vw", "car", or "volkswagen" will be grouped into "car", and the ones containing "game", "sport", "club" etc. will be grouped into "sport".

This isn't foolproof, of course, and the code required is very complex - but I've tried it, and it's kind of amazing.

--

What is even more amazing is that apparently, the Theseus project will aim to work like this, and possibly even work in a way that will be compatible with Google.

Google now offers prints from Picasa Web Albums. On one hand, this is great and very convenient (I probably won't use it, but still). On the other hand, these don't even need to be your photos - you can have anything printed provided it's hosted on Picasa Web.

The idea of anyone in the world being able to get a mousepad with my mugshot on it is frankly a bit unsettling... ^_^

I was looking for the quote from George Orwell's novel 1984 that begins "War is Peace." So I plugged it into Google, and noticed something funny in the suggestions (I use search auto-completion).

After entering "war is" Google already came up with a ton of suggestions that start that way. Suggestions are ranked by the number of results they return, so these quotes are ranked by their popularity.

These are the top 10:

• war is hell
• war is peace
• war is kind
• war is a force that gives us... [cut off]
• war is a racket
• war is not the answer
• war is peace freedom is... [cut off]
• war is good
• war is over
• war is peace 1984

This might be food for thought, but alas I don't have the time to comment on it because I need to get some work on my Nano done.

Edit: But I did enter "war is good", and notice that all suggestions were variations of "war is good for the economy".

I've taken to using Google's calculator function quite frequently. Mostly because with the toolbar and the search box in the upper right corner of my browser window, it's the nearest calculator I can reach in terms of clicks and mouse movement; I like to economize (Translation: *cough*lazyass*cough*).

I also use the Suggestions option for the search box (it does the same as Google Suggest), which allows me to see if I spelled something correctly, or if the first suggestion for a company name is "X sucks" or something like that.

What seems to have been added fairly recently is a suggestion menu containing the result to your current calculation if you entered in a Math expression. This effectively means you can click, enter something like "cube root of pi" (literally!) and have the result without having to click or press enter.

(Note: If you try to double-check this with your own calculator, be sure to set your calculator to Radians. I forgot and promptly got the wrong result. But Google was right.)

Perfection is in the details, and in the convenience.

And seriously, try entering "cosine of cube root of pi" or "30 degrees to radians" or even "thirty meter in feet". I'm currently trying to think of a natural language expression too complex for it to understand. It's not easy.

But, for example, currency conversion doesn't work: "30 euro in dollar" or "convert 30 euro to dollar" does return the correct result on the search page, but it doesn't put it into the suggestions menu. Yet.

Here's dreading the day it says "Sorry Aran, I'm afraid I can't do that."