Submission + - Regex Golf, XKCD And Peter Norvig (i-programmer.info)
The hover over text gives a regular expression that matches the last names of the elected US presidents, but not the losers. This started Peter Norvig, the well-known computer scientist, director of research at Google and wearer of brightly colored shirts, thinking about the problem. Is it possible to write a program that would create a regular expression to solve the xkcd problem? The result is an NP hard problem that needs AI like techniques to get an approximate answer.
To find out more read the complete description, including Python code, at Peter Norvig's blog post http://nbviewer.ipython.org/url/norvig.com/ipython/xkcd1313.ipynb which ends with the challenge:
"I hope you found this interesting, and perhaps you can find ways to improve my algorithm, or more interesting lists to apply it to. I found it was fun to play with, and I hope this page gives you an idea of how to address problems like this."