Slashdot Mirror
Regex Golf, xkcd, and Peter Norvig
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://regex.alf.nu/
Some favor trickiness, some favor just listing possibilities, but it's fun. I'm at 3651.
I live in constant fear of the Coming of the Red Spiders.
... that can find frost psits?
Confucius say, "Find worm in apple - bad. Find half a worm - worse."
Now build a robot that can design a program to write a regex expression to solve the xkcd problem.
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.
The International Obfuscated C Code contest had a winning entry that could flag the names of US presidents as republican or democrat.
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,
I wonder whether you can make a regexp that is shorter than this and accomplishes the same thing.
Avantslash: low-bandwidth mobile slashdot.
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.
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 or unemployment/welfare apocalypse depends on your political affiliation.)
There's really no better way to scan a log file for odd log entries than to write a big regexp that filters out whitelisted entries. Lets you find log entries you're NOT expecting. (and occasionally, log entries that not even the developers are expecting)
Editing them of course is a royal pain, (not to mention debugging!) so I usually write a script to compose the regexp. I just checked on one of mine, and it composes a 17,000+ character single-liner that scans my wired.log file.
I've got a smaller one that keeps an eye on secure.log for anomalies.
I work for the Department of Redundancy Department.
Some of us programmers have families, a life, don't watch anime, and aren't basement dwelling nerds.
Umm ... I just spent the last hour playing regex golf with my wife and kids.
There's a field called Grammar Induction, and the problem of learning regular languages, aka regular inference, can be considered a subfield. People have been working on this since the '50s. Applications include learning DTDs for XML/wrapper induction, and all kinds of problems in bioinformatics and natural language processing.
There's a strong link with the graph coloring problem, see
http://www.cs.ru.nl/~sicco/papers/alt12.pdf
In this field, the focus is generally on learning FSAs, but these can easily be transformed into regexps. There's work on learning regexps directly, see
http://www.informatik.uni-trier.de/~fernau/papers/Fer05c.pdf
Enjoy.
Why does this upset you? Is it the recognition that people much more intelligent than you are spending time on problems whose significance you don't understand, and attacking them makes you feel better?
The algorithm is an AI algorithm. It's using hueristics to attempt to minimize some function, as many AI algorithms do.
What a fool believes, he sees, no wise man has the power to reason away.
Python is very similar to Perl, and also has most of the characteristics that make Lisp a good language to program AI algorithms.
What a fool believes, he sees, no wise man has the power to reason away.
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.
Here's to hot beer, cold women, and Glaswegian kisses for all.
sowing only web pages for delta airlines; and not delta faucets? that's "googlely."
We fans know the first one is really "Star Trek: The Tone Poem".
Socialism: a lie told by totalitarians and believed by fools.
Well now you've just ruined my terror. I'll have to go read up on the up-coming UK legal hilarity to restore it.
I believe this is what you were looking for.
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
Usually easier to use the language you know, rather than learn a whole new language for a project.
"First they came for the slanderers and i said nothing."
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?