Results from the Workshop Run Within Google

I (Andrew Eland) ran this just before Christmas, as a special festive edition of our usual weekly 'tech talk' slot. I branded the talk as 'Scrapheap challenge', just as at OOPSLA, because the first Google result for 'scrapheap challenge Sudoku' is Nat's blog post, which links to the full details. Despite this, and my citing of the original workshop at the start, nobody found the existing solutions :-)

The workshop was kind-of distributed. We videoconferenced the event to our Bangalore office, and it worked surprisingly well. There wasn't really any interaction between the two sides during the challenge, but solutions were presented to everyone.

The solutions were pretty similar to the OOPSLA results. One team tried to build a Sudoku solver from scratch, and got something that worked for 50% of cases. A number of teams tried Java: all failed, mainly due to 1.4 vs 1.5 compatibility issues. Most teams strung together the Python solver that was used at OOPSLA with either a text-mode web browser, or wget. Most solutions munged the data into the format required by the solver using Python, however a few, including the first one to be completed, used C++.

A couple of solutions warrant a more detailed explanation:

One plugged wget into the python solver, munging the data format (which is non-trivial, if you don't user a text-mode browser to help format the page) entirely in a shell pipeline. Unfortunately, no one accessible machine had both the correct version of Python and wget installed. The contestant solved this by splitting the shell pipeline across two different machines, one with wget installed and the other with python, using netcat to stream text from one to the other. A postmodern distributed system.

The other notable solution used a web based Sudoku solver, rather than a local Python application. The site didn't advertise its solver, it was simply a Sudoku site wherein each puzzle had a 'solve this puzzle' link. They noticed the link pointed at a CGI script, with a description of the Sudoku as a CGI parameter. They simply munged the Sudoku into the relevant form, hijacked the website's solver, and rendered the resulting page to text with a text-mode web browser. Relating this to the REST vs. SOAP argument is left as an exercise for the reader.

The C++ programmers did very well, but typically the bulk of their solution was implemented as a UNIX shell pipeline. The C++ only covered tasks that would have been too tricky with awk. I think most people would opt for a scripting language in this situation, but if you're an STL guru, using C++ isn't such a handicap for small components.

I'm going to encourage the participants to blog their solutions. They'll probably post things before I post about the OOPSLA workshop :-)

— Andrew Eland