Forgot your password?
typodupeerror
Programming It's funny.  Laugh.

Regex Golf, xkcd, and Peter Norvig 172

Posted by samzenpus
from the problem-to-solve dept.
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.'"
This discussion has been archived. No new comments can be posted.

Regex Golf, xkcd, and Peter Norvig

Comments Filter:
  • Re:RegExps (Score:4, Insightful)

    by Anonymous Coward on Sunday January 12, 2014 @03:51PM (#45933703)

    ...and then there's the people who think they understand regexes, but try to use them to decide context-free grammars.

  • Re:Regex this (Score:2, Insightful)

    by Anonymous Coward on Sunday January 12, 2014 @04:04PM (#45933777)

    That other people have hobbies different than you is going to be quite common. If you get this angry every time you run into someone with a different hobby then I fear for your long term mental and physical health.

    Take deep breaths. It is going to be ok.

  • Hard AI (Score:5, Insightful)

    by Okian Warrior (537106) on Sunday January 12, 2014 @04:15PM (#45933845) Homepage Journal

    Regex me a list of folks that have time to sit around fucking off their life-time in order to write a regex to work on the XKCD "problem", and folks that don't.

    The field of study known as "AI" has been stagnant, for about 50 years now. One of the field's many problems is the lack of a good definition for intelligence.

    Despite lacking a definition, we have working examples intelligent systems in the real world - humans.

    Humans are very good at partitioning sets by descriptive differences, and they discover these descriptive rules largely by themselves.

    We don't know what intelligence is yet, but if we keep looking at problems and trying to figure out the human approach, eventually we'll have enough contrasts and similarity to partition sets based on differences in intelligence.

    In other words, the more problems we solve, the more data we can use to formulate rules that define intelligence.

    That's a pretty important and useful goal.

    (And belaboring the obvious: If we had even simple AI constructs we could automate much of out work force, freeing us up for more leisurely pursuits. Whether this leads to a post-scarcity utopia [wikipedia.org] or unemployment/welfare apocalypse depends on your political affiliation.)

  • Re: RegExps (Score:2, Insightful)

    by Anonymous Coward on Sunday January 12, 2014 @06:02PM (#45934437)

    Calling backslashes "whacks" disqualifies you from being involved in such discussions.

As in certain cults it is possible to kill a process if you know its true name. -- Ken Thompson and Dennis M. Ritchie

Working...