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:
  • by Amorymeltzer (1213818) on Sunday January 12, 2014 @04:24PM (#45933553)

    http://regex.alf.nu/ [regex.alf.nu]

    Some favor trickiness, some favor just listing possibilities, but it's fun. I'm at 3651.

  • RegExps (Score:5, Interesting)

    by ledow (319597) on Sunday January 12, 2014 @04:41PM (#45933639) Homepage

    Regexp's are a programming language unto themselves.

    I'm currently doing some temp IT work for schools while my promised job becomes available and it's eye-opening. The web-filtering is all reg-exp based but nobody understands how it works.

    They just copy/paste an example and change the parts of the URL that they can see to match the one they want. They barely bother to test the impact, past the site they need becoming "unfiltered" or "filtered" as necessary (i.e. no implication of knock-on effects on other sites with similar names). Let's not even mention the use of "." without the escape character for them to mean a literal period (but, obviously, it means "any character" in a regexp).

    I talked to them about changing their template regexp because, from the start, I could see that it wasn't really up to the job and just met if not opposition then at least apathy about the problem.

    Until someone brought an iPad into the helpdesk where a site that was supposed to be unfiltered was filtered - because nobody had considered what happens if you use "http://example.com" instead of "http://www.example.com". I was the one to spot it, and tell them that it's because their regexp was very basic.

    The good thing was, the other tech on the team was young and keen to learn and I was able to give them a quick rundown of regexps and we crafted an alternative template for them to use that would take account of the situation without, for instance, the blocking of "microsoft.com" affecting "antimicrosoft.com".

    But it is amazing how many people I know that work in IT have no idea how to program, no idea how to handle regexps, and just work on a "copy a working example" basis.

  • by hankwang (413283) on Sunday January 12, 2014 @04:47PM (#45933677) Homepage

    The International Obfuscated C Code contest had a winning entry that could flag the names of US presidents as republican or democrat. [ioccc.org]

    main(int riguing,char**acters){puts(1[acters-~!(*(int*)1[acters]%4796%275%riguing)]);}

    Quoting: "This one-line C program accepts as a first command-line argument the last name of any of the last 31 US Presidents (from Franklin Pierce onwards), in lower case, and prints out their political affiliation. Use "republican" as the 2nd command-line argument, and "democrat" as the 3rd (or equivalent strings of your choice)."

    De-obfuscated, it is a boolean expression acting on a string s,

    (*(int*)s)%4796%275%4

    I wonder whether you can make a regexp that is shorter than this and accomplishes the same thing.

  • by Xaedalus (1192463) <Xaedalys.yahoo@com> on Sunday January 12, 2014 @06:40PM (#45934343)
    As a junior cadet code monkey of a user, I come to /. precisely because I know my limitations when it comes to understanding tech, coding, and hard science. Despite the -1's, trolls, and certainty-addicted neckbeards (or, because of them) I've learned a lot about how intrinsically cool it is to code, the artistic side of coding, the wonders of science (and how it rivals religious experiences for appreciating one's place in the universe), and I've improved my debating skills on here. /. is one of the net benefits of my life, and I consider it a necessity. Chances are good, I'm not the only user who thinks that.
  • by raymorris (2726007) on Sunday January 12, 2014 @11:37PM (#45936121)

    For matching URLs from a domain, here's a regex we came up with that covers some special cases. Hopefully Slashdot doesn't mangle it too badly.

    https?://([a-z0-9\-]+\.)*foo\.com(/|$)

    That covers:
    https as well as http
    "subdomains" like maps.google.com as well as www.google.com and google.com
    It's not fooled by google.com.hacker.ru

  • Re:Hard AI (Score:5, Interesting)

    by Antonovich (1354565) on Monday January 13, 2014 @04:03AM (#45937219)
    You're both right. The term AI originally had much broader scope because (computer) people hadn't tried to implement it yet and realised that it was going to be *very* hard to do. Now people seem to use the terms Strong AI or Artificial General Intelligence for trying to get the kind of non-domain-specific "intelligence" humans (are supposed to) have, and "simple AI" just means tech that can adapt within a highly restricted domain (like search, navigation, etc.). The problem, of course, is that until we get an even remotely satisfactory definition of what "human intelligence" is, we aren't going to get very far. Unfortunately, it turns out that attempting to specify exactly what intelligence is ends up involving linguists, psychologists, biologists (neuroscientists, etc.) and worst of all, philosophers. Basically, no one agrees on anything and even when there are areas of agreement, each person seems to have deal-breaker elements that no one else agrees on. It gets messy, and quick. Worse still, it turns out that developmental/cultural factors (so development of an individual in a particular socio-cultural context) radically colours what kinds of definitions of intelligence people come up with, and the sorts of solutions it makes sense to think about (representationism vs enaction/actional theories, etc.). For example, a lot of work has been done on the psychological and cultural/historical effects of literacy (and numeracy) and show that someone growing up in a society in the Western Tradition (this is a specific term) that learns to read/write with an alphabet will often strongly prefer a particular view of the higher mental functions (language, thinking, "intelligence", etc.)(see John Goody, Roy Harris, David R Olson, and many more). If we want to create the tech then we need to go beyond that but it's incredibly hard to go beyond your own intellectual baggage. Researchers like Pei Wang have a bit of an advantage coming from a non-Western Tradition culture and he has some great thoughts on the different solution spaces that opens up. I like the way he uses levels (perspectives?) to look at this and the problem more generally. He talks about a Western bias for creating theories looking for "truth" (which has strong links to representationalist thinking) that he wants to avoid. It's certainly not impossible for someone from the Western Tradition (like Goertzel) to think otherwise but it requires significant amounts of meta-reflection - I have a theory that "works" but does everyone think it works? What kinds of people think it works, and what kind doesn't? Do people from all cultural traditions agree? What would my theory sound like to someone from the middle ages? Ancient Greece? Why would I come up with such a theory? How does it fit in to my view on other things (politics, religion, etc.)? If you scratch the surface you quickly realise that there is a vast world of stuff that affects even what we think it's interesting to think about. It's incredibly hard for us to not just assume that the Western Tradition is simply more advanced, purer and better. We are surrounded from birth with a moral framework (the UN, judeo-christian value system, etc.) and an educational system that promotes a Platonic view of pure forms and pure knowledge ("mathematics is the language of the universe", etc.). This sort of thing can even go completely out of whack, and result in the kind of stuff we saw with the Nazis. So if there is considerable debate on what it means to know something, then defining intelligence is not going to be a simple affair! I personally adhere to the school of thought that thinks that the best way to move forward is simply to re-create a human-like machine that acts/reacts in a way that most people would call "human". Almost everyone agrees humans are intelligent, so if it acts the same way then most of us will agree it's intelligent. This (almost) completely avoids the sort of shit we have to deal with that I mention above. Turns out it's far from trivial though...
  • by Shaterri (253660) on Monday January 13, 2014 @04:58AM (#45937413)

    My reading of Norvig's blog post is that he suggests his specific approach (stapling together short regexps with ORs) requires solving the NP-Complete Set Cover problem, but he doesn't actually say anything about whether the core problem (match everything in list A and nothing in list B) does; it's conceivable that e.g. some sort of dynamical programming approach could do the job more efficiently than Norvig's algorithm does. Does anyone know whether the root problem (to avoid having to do the optimization, just phrase it as 'is there a separating regexp for the sets A and B of length less than k?') is specifically known to be NP-complete?

Numeric stability is probably not all that important when you're guessing.

Working...