Nurikabe vs. Intel Multi-Threading Competition Series

I have been working for a few weeks on writing first a solver for Nurikabe puzzles and then a generator. It turns out that while a backtracking solution works fine for sudoku, there isn't enough pruning to make it work well for nurikabe, so it is necessary to code most of the logic steps used by a person to solve nurikabe puzzles. Anyway, I finally got my generator working well enough that it can make 5x5 nurikabe puzzles in real-time. And, it can generate 9x9 puzzles, but it can take a couple seconds to do so, which is too much for my webserver to handle if many people play, and too long to make people wait, anyway. So, I have a daily 9x9 nurikabe puzzle.

I got this up just in time (on Tuesday), as the first of the Intel Multi-Threading Competitions started on Wednesday. These are two week long programming competitions with cash prizes that are sponsored by Intel and put on by TopCoder. The programs that competitors write are run on a computer with 8 hyperthreaded processors, making for a total of 16 virtual processors. The idea is to teach coders how to use threads effectively to take advantage of multi-core multi-processor computers, of which there are more and more these days. I expect this to consume a chunk of my time over the next couple of weeks.

When PageRank Goes Wrong

About once each month somone mails a request for "Deuling Banjos sheet music" to the debian-devel mailing list. Someone else mails requesting to be removed from CallWave. Debian-devel is obviously not the place to make either of these requests, so why do people?

The problem is the way link counting is used to increase the percieved usefulness or popularity of a page. Since mailinglist archives have links to the next and previous mail by thread and by date, and often these are on the same subject, the posts end up ranking highly on search engines. This is great if it is on topic to the list and helps people find answers. The problem is when a list, like debian-devel, becomes the top resource for something it can't provide, like dueling banjos sheet music or removal of CallWave service.

In these two cases, someone got the idea to ask on debian-devel, and things got out of hand from there. I can't help with dueling banjos, but nchip has a post about it. I can do a little to help with CallWave removal. I posted those instructions to debian-devel in response to such a request about a year ago. But people still email debian-devel rather than following the directions.

Innovation Over Income: The Secret to Google's Success

I think about this every time I see a new Google product or an article pondering whether or not Microsoft and others should be afraid of Google. Well, I saw both of those yesterday.

Why is Google so successful? I believe the answer is in their reasons for coming out with new products. It seems to me that the reason is always along the lines of "I wish this were available, so let's do it," where "this" is webmail with 1GB of storage, the ability to search for files locally, a listing of the most popular news topics, etc. Sure, some of these help drive Google's advertising revenue. Some of them threaten other players and make them improve. But, I think Google's reason for providing them was because they are useful.

I cite in particular Google's Library initiative to scan and make searchable every book ever published. When I was at the Googleplex this September for the finals of the 2005 Google Code Jam we were treated to a talk by the head of this initiative. One thing that struck me was that he said that Google would be happy if other companies also started book scanning and searching programs. That is, as long as such a service were available, Google didn't care so much if they were the ones providing it or someone else. Just about a week later, Yahoo unveiled their similar program, and, sure enough, Google publicly stated that they were happy to hear about it.

How does Google do it? Their 20% time policy, that engineers should be working on pet projects 20% of their time, has a lot to do with it, I think. I also believe that a large part of their picky hiring practices has to do with wanting not only great engineers, but also creative engineers. Finally, Page and Brin seem to value innovation quite highly, so much so that engineers seem to be the first class citizens at Google, even over management.

Can Google keep it up? With the rapid pace at which Google is growing, can they keep their environment of innovation? When I was at Google in September, most of the employees I met had been working their for less than a year. My tour group was led by a veteran of 9 months, and the group I went out to dinner with had two Google employees in attendance who had worked there for 1 month and 2 months respectively. When I was at Google for the 2004 Google Code Jam finals, I got the impression that 20% time was supposed to be spent on one's own creative ideas, possibly in a small group with a few other Googlers. This time I was told by one of the new employees that most people spend their 20% time working with some other group within Google on established products.

That said, I expect that Google's new Create a Module for the Google Homepage program will help them recruit some creative talent. There is nothing like having developers create products for you to see what kind of talent they have.

Proprietary Drivers and Glue Layers

About a year ago my inlaws gave us a Canon i250 printer that they received with a new computer. They already had two other printers that they used, so they didn't need this one, and our Epson Stylus Photo 820 finally quit printing well, even after lots of print head cleanings. My first dissappointment was to find out that it wasn't supported by gimp-print or any other open source drivers. Fortunately, I found that Canon Australia and Canon New Zealand had released linux drivers.

These drivers consisted of six proprietary libraries, and a decent amount of GPL code to provide the user interface. They also provided RPMs for some ancient version of Red Hat. After fighting with compiling the provided source (it didn't include the proprietary libraries it turns out), I used alien to convert the RPMs to DEBs and installed them. I was able to configure the printer, but nothing was printed. Debug output from CUPS finally showed me that I needed to install libtiff3g, libpng2, and libxml1.

Over the past month, I have spent some time trying to compile the source again. While I can get parts of it to compile once I have the libraries installed, I still don't end up with everything that is in the RPMs. I was thinking I would put together a non-free package of the libraries, and then some DEBs that depended on it, so I could get rid of the outdated libraries, as well as help others get their i250s working on Debian. In the end, I wrote a guide to help others install the Canon provided RPMs instead.

The lesson here is that proprietary drivers are no fun, especially if the provided glue layer isn't all there. I'll have outdated libraries on my system until I get a new printer.

How Open Can Your Mind Be?

I am a member of the URC Mens' Club at my church, and this past week we were discussing, "Is there a God?" Except, that isn't what we discussed. What we actually talked about is the reasons people might have for not believing there is a God, such as "If there is a good God, why is there so much evil and suffering in the world?" and "How could a good God let people go to Hell?"

Before we all left, we lamented that we had failed to truly discuss our topic because none of us had approached the discussion with an open mind to the possibility that there might not be a God. We decided it would have been a much better discussion if we had had some atheists among us.

Anyway, this leads me to this post's title - whether or not you believe there is a God, are you able to really consider with an open mind the question, "Is there a God?"

My New Blog and Why The New Website

I have resisted having a blog to this point because I didn't have a public website on which to post it. Now that I have created www.logicgamesonline.com I figure I might as well add a blog to the site.

I recently became addicted to sudoku puzzles when they appeared in our local newspaper, the Ann Arbor News. This addiction was fed when we got to my inlaws' for a week of vacation at Thanksgiving and they had a Sudoku book lying on the coffee table. After not finding any really good places to play sudoku online, I spent much of my freetime during the week creating my own. I hope you enjoy it as much as I do.