Regex Golf, xkcd, and Peter Norvig

[sl4shd0t]

mikejuk writes "A recent xkcd strip has started some deep academic thinking. When AI expert Peter Norvig gets involved you know the algorithms are going to fly. Code Golf is a reasonably well known sport of trying to write 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. This started Peter Norvig, the well-known computer scientist and director of research at Google, 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, on Peter Norvig's blog. It ends with this 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.'" http://a.fsdn.com/sd/twitter_icon_large.png (http://twitter.com/home?status=Regex+Golf%2C+xkcd%2C+and+Peter+Norvig %3A+http%3A%2F%2Fbit.ly%2F1kwylU5) http://a.fsdn.com/sd/facebook_icon_large.png (http://www.facebook.com/sharer.php?u=http%3A%2F%2Fdevelopers.slashdot.org% 2Fstory%2F14%2F01%2F12%2F189207%2Fregex-golf-xkcd-and-peter-norvig%3Futm_source%3Dslashdot%26utm_medium%3Dface book) http://www.gstatic.com/images/icons/gplus-16.png (http://plus.google.com/share?url=http://developers.slashdot.org/story/14/01/12/189207/regex-golf-xkcd-and-peter-norvig?utm_source=slashdot&utm_medium=googleplus)

Read more of this story (http://developers.slashdot.org/story/14/01/12/189207/regex-golf-xkcd-and-peter-norvig?utm_source=rss1.0moreanon&utm_medium=feed) at Slashdot.
http://slashdot.feedsportal.com/c/35028/f/647376/s/35cf5b53/sc/4/mf.gif


http://da.feedsportal.com/r/186528660697/u/49/f/647376/c/35028/s/35cf5b53/sc/4/rc/1/rc.img (http://da.feedsportal.com/r/186528660697/u/49/f/647376/c/35028/s/35cf5b53/sc/4/rc/1/rc.htm)
http://da.feedsportal.com/r/186528660697/u/49/f/647376/c/35028/s/35cf5b53/sc/4/rc/2/rc.img (http://da.feedsportal.com/r/186528660697/u/49/f/647376/c/35028/s/35cf5b53/sc/4/rc/2/rc.htm)
http://da.feedsportal.com/r/186528660697/u/49/f/647376/c/35028/s/35cf5b53/sc/4/rc/3/rc.img (http://da.feedsportal.com/r/186528660697/u/49/f/647376/c/35028/s/35cf5b53/sc/4/rc/3/rc.htm)

http://da.feedsportal.com/r/186528660697/u/49/f/647376/c/35028/s/35cf5b53/a2.img (http://da.feedsportal.com/r/186528660697/u/49/f/647376/c/35028/s/35cf5b53/a2.htm)http://pi.feedsportal.com/r/186528660697/u/49/f/647376/c/35028/s/35cf5b53/a2t.imghttp://feeds.feedburner.com/~r/Slashdot/slashdotDevelopers/~4/9m3ZWdiik1g

More... (http://rss.slashdot.org/~r/Slashdot/slashdotDevelopers/~3/9m3ZWdiik1g/story01.htm)