Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Regex Golf, XKCD And Peter Norvig

mikejuk (1801200) writes | about 8 months ago

0

mikejuk (1801200) writes "A recent xkcd cartoon has started some deep academic thinking. When AI expert Peter Novig gets involved you know the algorithms are going to fly. Code Golf is a reasonably well known sport of trying to code an algorithm in the shortest possible code. Regex Golf is similar, but in general the aim is to create a regular expression that accepts the strings in one list and rejects the strings in a second list. The xkcd cartoon in question http://xkcd.com/1313/ revealed that this is but the first step. Programmers like recursion and a regex is a string after all and a regex can process a string so a regex can process a regex and this means you can have meta-regex golf and meta-meta-regex golf.... Yes my friend, it's regexes all the way down!
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.""

Link to Original Source

cancel ×

0 comments

Sorry! There are no comments related to the filter you selected.

Check for New Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>