Beta

Slashdot: News for Nerds

×

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

samzenpus posted about 6 months ago | from the problem-to-solve dept.

Programming 172

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.'"

cancel ×

172 comments

FWIW, the Regex Golf game (5, Interesting)

Amorymeltzer (1213818) | about 6 months ago | (#45933553)

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

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

Re:FWIW, the Regex Golf game (3, Informative)

Garridan (597129) | about 6 months ago | (#45933809)

Or, if you want to try your hand at meta regex golf [stackexchange.com] there's a place for that, too.

Cookies required? (1)

Okian Warrior (537106) | about 6 months ago | (#45933969)

Be sure to allow cookies, else the site won't work.

Cookies are an essential part of websites nowadays, dontcha' know...

Re:FWIW, the Regex Golf game (0)

Anonymous Coward | about 6 months ago | (#45936675)

Or just search for the github page and you'll easily hit 4061. ;-)

Is there a regex... (3, Funny)

Hognoxious (631665) | about 6 months ago | (#45933555)

... that can find frost psits?

Re:Is there a regex... (1)

syockit (1480393) | about 6 months ago | (#45936035)

Now I know where Frosty Piss's username came from.

Meta-meta-meta-meta.. (2)

Travis Mansbridge (830557) | about 6 months ago | (#45933561)

Now build a robot that can design a program to write a regex expression to solve the xkcd problem.

The Motion Picture (0)

Anonymous Coward | about 6 months ago | (#45933621)

Why is The Motion Picture not considered the subtitle for the first Star Trek movie?

Re:The Motion Picture (3, Funny)

lgw (121541) | about 6 months ago | (#45934479)

We fans know the first one is really "Star Trek: The Tone Poem".

Re:The Motion Picture (0)

Anonymous Coward | about 6 months ago | (#45934579)

I agree that it was awful, but I don't know why Norvig left it out.

RegExps (5, Interesting)

ledow (319597) | about 6 months ago | (#45933639)

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.

Re:RegExps (3, Funny)

Hognoxious (631665) | about 6 months ago | (#45933693)

Regexp's are a programming language unto themselves.

It would appear that apostrophes are too.

Re:RegExps (-1)

Anonymous Coward | about 6 months ago | (#45933823)

I would say that \'s [whacks] are a language too. If you get to 39 whacks, stop. It did not work out well before.

Re: RegExps (2)

LordSnooty (853791) | about 6 months ago | (#45934401)

I don't know, apostrophes can be used to indicate missing letters and it helps to highlight that regexp isn't really a word (yet).

Re: RegExps (2, Insightful)

Anonymous Coward | about 6 months ago | (#45934437)

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

Re:RegExps (0)

Anonymous Coward | about 6 months ago | (#45935929)

Shame about the downmod. That one made me laugh out loud.

Re:RegExps (4, Insightful)

Anonymous Coward | about 6 months ago | (#45933703)

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

Re:RegExps (1)

simplypeachy (706253) | about 6 months ago | (#45933725)

Just wait till you play with Privoxy. It uses different sorts of regex for different parts of the URL pattern. You then have two additional problems, rather than just one ;-)

Re:RegExps (5, Funny)

Anonymous Coward | about 6 months ago | (#45933753)

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.

You will be truly amazed by the number of people who copy a not-working example...

Re:RegExps (2, Informative)

Anonymous Coward | about 6 months ago | (#45933915)

If regular expressions are a programming language, then they are not a very powerful one. The languages they recognize are the so-called regular languages, which are the least expressive category in the Chomsky hierarchy of languages (note the difference between the language of regular expressions and the languages recognized by regular expressions). See the Wikipedia articles on regular languages [wikipedia.org] and the Chomsky hierarchy [wikipedia.org] for details.

Re:RegExps (0)

Anonymous Coward | about 6 months ago | (#45935571)

Programming languages do not have to be Turing complete.

Re:RegExps (0)

Anonymous Coward | about 6 months ago | (#45936039)

the so-called "regular expressions" which are actually used are typically extensions, sometimes fairly radical ones, of theoretical regular languages (which are worthy of their own interest, of course).

Re:RegExps (0)

Anonymous Coward | about 6 months ago | (#45934357)

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.

I'm not. Regular expressions are often too hard to understand, too hard to create correctly without consulting a manual all the time, and there's no requirement for someone to program if administering servers. There's a REASON why we've got so many IT people around - it's relatively easy for any typical computer geek to become one. But if it required skills that you find amazing that people lack, it's be a very unpopular profession indeed.

Re:RegExps (1)

Anonymous Coward | about 6 months ago | (#45934577)

But it is amazing how many people I know that work in IT have no idea how to program

Is it? Programmers routinely make 30% more. Why should an IT person, with their entire forte of knowledge and skills, ever need to take on someone else's and even if they did, why would they keep their low salary.

It is akin to an auto mechanic that knows how to use a CNC machine to make replacement parts. Sure it would be convenient to hire a $10/hr mechanic that can do $40/hr G-code, but what is in it for the mechanic?

Re:RegExps (0)

Anonymous Coward | about 6 months ago | (#45935485)

Why should an IT person, with their entire forte of knowledge and skills, ever need to take on someone else's [job] and even if they did, why would they keep their low salary.

It is akin to an auto mechanic that knows how to use a CNC machine to make replacement parts. Sure it would be convenient to hire a $10/hr mechanic that can do $40/hr G-code, but what is in it for the mechanic?

Few career programmers are interested in switching down to "general" IT positions, but you imply the converse is only a problem because of salaries.

You put it as if having programming-enhancements for the IT tech, and CNC-enhancements for the auto-mechanic "knowledge and skills" are all we need to land the programming job or G-code position. In tech, real programmers find walls for jobs they rightfully match with factual resume experience. Just how much more easily is their wall to climb by aspiring job-switchers that come from under-rated skillsets and bring no day-to-day experience?

Re:RegExps (2)

Redmancometh (2676319) | about 6 months ago | (#45936009)

A $40/hr G-code monkey would be underpaid.

Re:RegExps (1)

Anonymous Coward | about 6 months ago | (#45935347)

This is pretty common. It is not some new, strange thing only you have seen:

http://en.wikipedia.org/wiki/Cargo_cult_programming

People go through life with blinders on, because life is complicated and our minds try to ignore things that it figures aren't important. A lot of people think details of one sort or another aren't complicated or relevant, then complain when things don't work for some reason. That's why empirical reasoning and the scientific method is cool; it works against this sort of logical fallacy.

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

raymorris (2726007) | about 6 months ago | (#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:RegExps (0)

Anonymous Coward | about 6 months ago | (#45937263)

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.

Not really. A lot of people like regexps because of how compact they are.
The problem is that they aren't efficient nor readable. They may have their uses but if you can achieve the same result in a screens worth of C-code it is preferable.
Compact one-liners are great as a hobby but doesn't belong in code that is supposed to be maintained.

Admittedly I might just be burned by people who insists on using regexp for all text-matching, regardless of Chomsky hierarchy. (Yes, including html and xml.)

ioccc 2013 US president matching code (4, Interesting)

hankwang (413283) | about 6 months ago | (#45933677)

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.

Re:ioccc 2013 US president matching code (2)

hankwang (413283) | about 6 months ago | (#45933711)

Pardon, I forgot the "not" operator. De-obfuscated, it is a boolean expression acting on a string s,

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

Re:ioccc 2013 US president matching code (0)

Anonymous Coward | about 6 months ago | (#45933827)

I wouldn't say that's de-obfuscated -- I still have no idea what it does

Re:ioccc 2013 US president matching code (4, Informative)

hankwang (413283) | about 6 months ago | (#45934199)

It takes the first four bytes of the president's name, converts them to int; then applies four modulo operations (%4796 %275 %4). How the author figured out that those four operations would do the job, who knows? Maybe brute-forced the parameter space.

Re:ioccc 2013 US president matching code (1)

Mes (124637) | about 6 months ago | (#45934461)

Can someone explain, how are they using 1[..] as the name of an array? I tried making a simplified program and gcc kicked out the approriate error.

Re:ioccc 2013 US president matching code (1)

Anonymous Coward | about 6 months ago | (#45934493)

In C, arrays are really just pointers to the first element, and array[index] is defined through pointer arithmetic: It just means *(array+index). Addition is commutative, so you could just as well write index[array], because that is defined as *(index+array), which is the same as *(array+index).

Re:ioccc 2013 US president matching code (0)

fisted (2295862) | about 6 months ago | (#45934823)

In C, arrays are really just pointers to the first element

No.

, and array[index] is defined through pointer arithmetic: It just means *(array+index). Addition is commutative, so you could just as well write index[array], because that is defined as *(index+array), which is the same as *(array+index).

Yes.

Re:ioccc 2013 US president matching code (1)

Anonymous Coward | about 6 months ago | (#45934893)

Could you be less helpful?

Re:ioccc 2013 US president matching code (0)

Anonymous Coward | about 6 months ago | (#45935735)

Could you be less helpful?

Probably.

Re:ioccc 2013 US president matching code (0)

Anonymous Coward | about 6 months ago | (#45935709)

To you're no, care to explain?

int array[32];

and

int* blah = &(array[0]);

will both point to the exact same element in memory. If you do an equivalence operator on them, they'll be equal. There is, fundamentally, no difference. In fact, I can then later take

*(int*)((int)blah+(3*sizeof(int)))

and that would be the equivalent of

array[3]

In fact, if you ever look at the disassembly of some C code, you find that what it's doing isn't really far off of what I wrote in that rather nasty piece of code.

Now, hopefully when I post this, all my code doesn't disappear.

Re:ioccc 2013 US president matching code (2)

thogard (43403) | about 6 months ago | (#45937315)

I think the subtletyâZ the objector had was that arrays and pointers are slightly different which is true In this context, an array is a pointer with potentially compiler allocated backing memory for the data while the pointer might not. A pointer will also have an address while the pointer used in array definitions won't have an address. Old compilers used to treat them identically but then again they used to treat pointers as integers as well. Modern compilers tend to know enough about the CPUs and have built in array checks that they do work slightly differently.

Re:ioccc 2013 US president matching code (1)

Anonymous Coward | about 6 months ago | (#45934403)

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

because a[b] is the same as a+b is the same as b+a is the same as b[a].

The "not" forces a boolean expression, which evaluates to 0 or 1. The bitwise not (~) flips the bits. For 1 the result is -2 (two's complement representation of -2 is 1111...1110). For 0 the result is -1 (two's complement...). So the index evaluates to 1-(-1)=2 or 1-(-2)=3 and the puts prints the second or third argument to the program, depending on the result of the boolean expression.

For the boolean expression, s[1], the pointer to the first argument, is cast to an int pointer and dereferenced, so *(int*)s[1] is the first four bytes of the first argument interpreted as an int. Then there are 3 modulos. The last one, %i, is %4, because i is the argument count, including the name of the program as argument 0. If the result of this calculation is 0, then the boolean expression (before negation) is false, otherwise it's true.

Re:ioccc 2013 US president matching code (0)

Anonymous Coward | about 6 months ago | (#45934569)

Sorry, forgot to dereference:
because a[b] is the same as *(a+b) is the same as *(b+a) is the same as b[a].

Re:ioccc 2013 US president matching code (-1)

Anonymous Coward | about 6 months ago | (#45933979)

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

Not in Python like this dumbass.

Python, lol. Don't use too many spaces! (and fuck you editor snobs, having a bandaid to fix a systemic problem is no solution)

Re:ioccc 2013 US president matching code (0)

Anonymous Coward | about 6 months ago | (#45934551)

LRN2<ecode>

Regex this (-1, Troll)

BringsApples (3418089) | about 6 months ago | (#45933695)

Ok, mod me troll, but...
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. And for the folks that are working on this, is this one of those things that you need 2 monitors for? I mean honestly, who in the hell has time to fuck off like this, and why? If you were going to school for coding, and your teacher gave you this as an assignment, I imagine that it'd be one of those things that you'd gripe about 'having' to do, and how stupid it is - a waste of time. And you'd be right.

Re:Regex this (2, Insightful)

Anonymous Coward | about 6 months ago | (#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.

Re: Regex this (-1)

Anonymous Coward | about 6 months ago | (#45933857)

Some of us programmers have families, a life, don't watch anime, and aren't basement dwelling nerds.

Regex golf is about as interesting a hobbie as stamp collecting. The only fear here is being lumped into a stereotype that we don't belong, and I doubt I'm the only one who despises people who perpetuate that stereotype.

Re: Regex this (0)

Anonymous Coward | about 6 months ago | (#45933903)

Yeah, right. Look where you are.

Re: Regex this (5, Funny)

ShanghaiBill (739463) | about 6 months ago | (#45933939)

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.

Re: Regex this (0)

Anonymous Coward | about 6 months ago | (#45934425)

and I just closed a multi-billion-dollar business deal over a round of regex golf at a very exclusive regex golf resort in the Bahamas.

Re: Regex this (0)

Anonymous Coward | about 6 months ago | (#45934291)

Maybe if you and BringsApples didn't spend so much time posting to Slashdot, you would have more time to do something constructive and potentially educational. And if you didn't spend so much mental effort worrying about what others do to your stereotype and what you think you can accomplish by complaining about it on the internet, then maybe you could come up with something fun to do with your family that accomplishes the same thing, so you don't have to act like family time is mutually exclusive with free time.

Re:Regex this (1)

Anonymous Coward | about 6 months ago | (#45934005)

Take deep breaths. It is going to be ok.

This is what I really can't stand in a teacher. Don't lie to your student. Don't sugar coat the hard truth. It's not going to be okay. He's going to die. Dead; no longer living. It may take time. It might be not that painful, but there's a fair chance that it's going to be awful. Just tell him the truth now. Don't say

It is going to be ok.

He will have to face it:

In the end we are all going to be dead. Dead; DEAD.

It might seem to him to be okay to be angry, about people with different hobbies, but if it causes him stress, make him take up smoking, or worse, restart smoking after giving up, and then die of a disease caused by his lack of tolerance, trust me he's not going to thank you for hiding the truth.

I know, right! (0)

Anonymous Coward | about 6 months ago | (#45933843)

Every single human should be working towards curing cancer and getting in to space and solving the mysterious universe that we live in!

Fuck people that have fun and hobbies!

Hard AI (4, Insightful)

Okian Warrior (537106) | about 6 months ago | (#45933845)

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:Hard AI (2)

Eythian (552130) | about 6 months ago | (#45934739)

That's not true. The field hasn't been stagnant at all. The problem is you're missing most of the field in your assumption of what it is.

AI is not all about making "computer programs that can think" (a.k.a "Strong AI"), it's more about creating systems that can adapt to their environment in order to improve their chance of success. If their environment is getting lists of names and they adjust, without the direct input of a person, to better match them according to some scoring system, that is AI.

It can use statistical methods, evolutionary characteristics, or just adjusting variables according to how wrong they currently are in order to try to match some problem. I'm not even touching symbolic AI here, because I don't understand it nearly so well.

Strong AI is part of the field sure, but certainly not all of it as you imply. It is a very large field.

Re:Hard AI (1)

Okian Warrior (537106) | about 6 months ago | (#45935087)

AI is not all about making "computer programs that can think" (a.k.a "Strong AI"), it's more about creating systems that can adapt to their environment in order to improve their chance of success.

Take a few moments and see if you can come up with a definition of Intelligence - one that can be used as a metric to see whether a topic falls within the field of study.

Abstract Algebra [wikipedia.org] has a precise definition, so it's pretty easy to tell whether something falls within the realm of Abstract Algebra. There are corner cases and some overlap, but the field is pretty-well delineated.

In contrast, AI is all over the map. Anything and everything can be put under the term, including lots of stuff that more rightly belongs in other areas.

If you can come up with a good precise definition, you'll be the first.

Re:Hard AI (1)

Eythian (552130) | about 6 months ago | (#45935393)

I gave a definition for AI already. In fact, you quoted it. It's not the most precise one, but I don't have to provide a precise one. All I was doing was demonstrating that your implied definition was far, far too narrow.

There are many things that are considered AI that don't match the range you suggested for it. Genetic algorithms, neural networks, language learning systems, robots that take information from their environment, discard it, and drive into walls. They're never* going to think, but they are rightfully AI.

It's not a requirement of a field that it has tight definitions, especially one where different methods that seem in a similar spirit pop up somewhat regularly.

In essence, writing a computer program that uses heuristical and adaptive methods to generate regexes to match/not match specific lists could be a form of genetic programming (though there are other options) which is comfortably under the AI umbrella.

* never say never, but with the scale they're on at the moment, it seems a long ways off.

Re:Hard AI (4, Interesting)

Antonovich (1354565) | about 6 months ago | (#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...

Re:Hard AI (1)

bunratty (545641) | about 6 months ago | (#45935927)

This is why Russell and Norvig sidestep the issue in their book. They provide the notion of "behaving rationally", which is performing well according to some performance metric within a given environment. So essentially any problem for which we cannot write a program that quickly finds the best answer leads to some programs which can do better than others. The ones that do better behave more rationally than the ones that do worse. There really isn't any intelligence in the way that you mean in these programs. A translation program doesn't understand the sentences it's translating any more than a chess-playing program understands that it's playing chess any more than a sorting program understands it's sorting things.

Re:Hard AI (1)

Anonymous Coward | about 6 months ago | (#45937093)

Let's consider the expression "the definition of insanity is doing the same thing over and over again and expecting different results." Such behavior would generally be described as unintelligent, so something that's intelligent should not exhibit this behavior at all, if possible. Doing the same thing over and over again is basically the computer equivalent of an infinite loop. If a computer program were intelligent it should be able to determine if a computer program is looping endlessly. This is more commonly known as the halting problem, which is just one of several undecidable problems. Intelligence is being able to recognize that fact instead of endlessly grinding away in the same manner.

Humans can generally spot this type of behavior and stop the program themselves. Some are a bit more clever and can construct proofs about why computers aren't able to do that. We may have to start building different types of computers if we want them to be intelligent.

Re:Hard AI (1)

BringsApples (3418089) | about 6 months ago | (#45934951)

One of the field's many problems is the lack of a good definition for intelligence.

Well, I don't mean to sound like I know everything, I certainly don't. But in my mind, 'intelligence' is the ability to make sense of Nature (or another way to say this is to be able to sense Nature). Those that don't have a good definition for 'intelligence' more than likely are living in a way that is not in tune with Nature.

They're probably dorking around with some regex, trying to sort a list of stupid from silly. Not saying that you, sir, are (as from the tone of your response, it appears that you are a sensible person). But From my original post, I should have guessed that it'd be flamebait, rather than troll.

Re:Hard AI (1)

retchdog (1319261) | about 6 months ago | (#45936743)

Since you brought it up, I should point out an interesting continuum I've noticed.

On one end, we have stoner fuck-ups who think everything is an amazing manifestation of Nature (or Jesus, or Buddha, or whatever the fuck) that they're constantly and uniquely (maybe along with a few of their friends) in touch with. They can't really ever describe why, or convince anyone of anything, but they know that they are in touch with something transcendent, and if other folks are wearing blinders, so what? This is perfectly fine, of course.

On the other end, we have people who've earned contact with Nature. Scientists like Feynman or Schroedinger, who have through incredible effort and ability actually achieved contact with the real thing which so many people experience only as a dim shadow on a cave wall or looking glass. Almost literally demigods; the first thing any of them would tell you, is to beware of that delusion, that cosmic banality and self-obsession, which drives the stoners on the other end of the spectrum. Not that it's bad per se. In fact, it can be an amazing and beautiful motivation, but it can also lead one to surrender and give up that natural skepticism which is as important as that thrill of exploration.

So far, so good.

Now what's interesting is, we have people in between. People like, for instance, me; people who can work and struggle and hope and dream, but will never be a Feynman, something which is all the more painful because we don't want the fame or whatever. We just know that something exists that we don't fully understand, but relish the partial understanding we do have. We just want more of that, but in the end we can't do it. Some of us give up in middle school algebra or earlier; some of us in intro to physics; some of us in E&M or differential geometry or nonlinear optics or whatever the fuck; some of us drop out of an advanced degree; some of us might even earn a doctorate, but at the end of the day, it just won't happen.

What do we do? We know how to think, but we just can't think quite broadly or deeply enough. We can see the beauty of what we can't achieve, and on the other hand we can achieve plenty, but a plenty which falls short. We could give up entirely, of course, in whatever way; sell ourselves for the most money, or raise a family and call that good enough. Another choice is to revel in what we can do; that same mind that can't even approach quantum chromodynamics can perform a complete analysis of what regular expression is necessary for some problem, or of whatever program can generate whatever regular expression is necessary, or of how to optimize a rendering routine to run on totally inadequate hardware, or any number of other things.

Perhaps the most fortunate, are the ones who never realize that Nature is a thing to be named. They simply think, unaware of a greater context, with an ignorance they are unknowingly fortunate of, solving and reveling in exactly those problems to which they are suited.

But when someone like you starts talking about the glories of Nature, and the short-sightedness of those people in the middle of the spectrum, and blah blah blah, I always ask myself: is this person a stoner fuck-up, or is this person an unrecognized Feynman? ...

Well, which one are you?

Re:Hard AI (0)

Anonymous Coward | about 6 months ago | (#45935323)

Or, to put it another way, "I am unaware of the research in this field, and therefore have decided that this field is not investigating the problems it purports to solve. Let me present how I think this field I know little of should change: ..."

lol

Re:Regex this (0)

Anonymous Coward | about 6 months ago | (#45933867)

Think of it this way: people who do things like this aren't out in public, adding to traffic on the highway (or possibly wandering out into the street aimlessly, getting hit by cars and making huge traffic backups). See, that's a plus for you.

Or think of it another way: other people have no obligation to live their lives in any way that you may or may not approve of. After all, what's a bigger waste of time, writing regex golf code, or bitching about other people writing regex code?

Re:Regex this (1)

Threni (635302) | about 6 months ago | (#45933879)

He works at Google on AI, and this problem is both amusing and interesting. Having two monitors is totally normal.

Slashdot really has gone to the dogs, hasn't it. Would be great if there were some sort of technical test one could take here; the results of which could be used to filter out all the - for want of a better word - users.

Please, no, don't filter all users out (4, Interesting)

Xaedalus (1192463) | about 6 months ago | (#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.

Re: Regex this (0)

Anonymous Coward | about 6 months ago | (#45935871)

I think all of IT have gone that way. It has become diluted by people who just want to solve their problem at hand as sloppily as possible and get home to watch TV.

Re:Regex this (2)

alienmole (15522) | about 6 months ago | (#45933997)

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?

Re:Regex this (1)

BringsApples (3418089) | about 6 months ago | (#45934981)

Well, I certainly didn't mean to attack anyone, I just didn't really know that my comments would hurt feelings. And perhaps you're right, maybe I don't understand why 'sorting a list in the quickest way possible, being made into a game' is useful. Can you enlighten me?

Re:Regex this (1)

RamiKro (3019255) | about 6 months ago | (#45934009)

It's a special case of automatic code optimisation: Since regular expressions should be reduce-able to logical gates, it stands to reason a minimized equivalent boolean function could be decompiled into a regex.
On it's own, having compilers\interpreters that optimize regexes is beneficial. But how about you turn the table over and ask yourself this, "Can I design a high, expressive, programming language that could be fully optimised without sacrificing human readability and productivity?" As far as I can tell, this is the holy grail of system research, or what's left of it nowadays...

Re:Regex this (1)

BringsApples (3418089) | about 6 months ago | (#45934159)

Ok, I get the need for optimization of coding habits. But as far as I understand this article however, it's about solving the XKCD "problem" - how to write a formula that separates elected presidents from unelected presidents. If I'm wrong, then I'm sorry. I read a bit of the article, and determined that it was a shot at being nifty - trying to get a bunch of brogramers to 'stroke out the biggest cock, in the shortest amount of time' sorta thing.

Re:Regex this (0)

Anonymous Coward | about 6 months ago | (#45934087)

Yeah, fuck people who have time to do useless things, like regex golf, and posting to Slashdot, and..... wait... what?

Re:Regex this (0)

Anonymous Coward | about 6 months ago | (#45934121)

It's called exercising our 'little grey cells'. Beats watching TV.

And no, I didn't use two monitors. I used pencil and paper.

Re:Regex this (1)

hermitdev (2792385) | about 6 months ago | (#45934917)

There are sorts of "problems" that may seem a waste. When Einstein was pondering Relativity, I'm sure it would have been thought of in the same manner. The point is, sometimes great things arise from "trivial" pursuits. This could also be construed as a implementation of a search algorithm that can take a relatively broad search term and produce a more generalized search pattern, i.e. now you cannot specify give me presidential candidates A, B, C, D, E, F according to whether or not they won an election.

This may seem trivial, but it is this sort of logic/AI that may lead to computers in the future answers questions like we see in Star Trek.

Re:Regex this (0)

Anonymous Coward | about 6 months ago | (#45934977)

So why did you "go to school for coding" if you clearly don't like it?

Re:Regex this (1)

Pseudonym Authority (1591027) | about 6 months ago | (#45935657)

"Coding" is what replaceable, uncreative idiots do. It's better to solve an interesting problem, for whatever definition of interesting is to the solver, than it to be a brainless drone making another fucking login page. Why don't you try to actually make something instead of letting the potential (that you probably don't have, to be honest) waste away? If you can't do that, then at least leave the actual programmers and computer scientist to practice the art while you die having accomplish nothing but having your code thrown in the trash a single support cycle after you get laid off.

Re:Regex this (1)

BringsApples (3418089) | about 6 months ago | (#45936267)

Oh, solving problems. See I thought that this was just about playing some programing-related game, via shortening algorithms. Hell, if we're talking about solving problems, let's get to world hunger and water filtration. I'm working on the world hunger bit. You wanna work with me, or do the water filtration bit?

Re:Regex this (1)

Pseudonym Authority (1591027) | about 6 months ago | (#45936875)

No, I don't particularly find those interesting and don't really care all that much. Let me clarify what I meant some; by problem, I mean a something closer to a puzzle, something intellectually challenging. The problems you describe are not those, as the solutions to such are evident but lacking the logistic plan to implement them. That is no less challenging perhaps, but not in the same way. It is the difference between developing a cure for HIV and actually navigating your way through a suspicious population while avoiding the wrath of the local warlords to actually distribute it to those in need. The problem you suggest is of the nature of the latter. Good for you. But just because that's what you find to be the noblest of goals doesn't mean that the guys working on, say, solving abstract mathematical problems need to stop and direct all their attention to your pet causes.

Anyway, let me direct your attention to the qualifier that I have attached that bit:

for whatever definition of interesting is to the solver

Obligatory xkcd (-1)

Anonymous Coward | about 6 months ago | (#45933701)

Obligatory xkcd [xkcd.com]

Thank you! I'll be here all week! Try the veal! Be sure to tip your waitress!

Terrifying (1)

simplypeachy (706253) | about 6 months ago | (#45933735)

"Find it interesting"? I find it fucking terrifying. There's no way I'll be following that link. That's in bat country.

Re:Terrifying (1)

ysth (1368415) | about 6 months ago | (#45933755)

No, actually it is far from terrifying. Just some brute force generation and application of simple, short, regex fragments. No "AI-like", no "algorithms going to fly".

Re:Terrifying (2)

bunratty (545641) | about 6 months ago | (#45934071)

The algorithm is an AI algorithm. It's using hueristics to attempt to minimize some function, as many AI algorithms do.

Re:Terrifying (2)

simplypeachy (706253) | about 6 months ago | (#45934497)

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.

Missed the point (1)

NonSequor (230139) | about 6 months ago | (#45933807)

I'd have been extremely surprised if solving for the shortest regex golf pattern for a pair of lists weren't NP hard. And greedy approaches are fairly obvious.

The point is, that's what makes it analogous to golf. The optimal solution is your hole in one. Some greedy algorithm solution is your par. Those aren't the interesting areas, they're just the end points.

For those who couldn't work it out for the,selves, here are the rules of regex golf:

How many characters you use in your regex is your score
Lower is better
There's a par calculated for each hole, and totaled for the course, which serves as a frame of reference for performance

whitelisting with regexp (3, Funny)

v1 (525388) | about 6 months ago | (#45933921)

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.

This problem has been studied for decades (5, Informative)

DogPhilosopher (1149275) | about 6 months ago | (#45933955)

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 [cs.ru.nl]

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 [uni-trier.de]

Enjoy.

Obligatory (-1)

Anonymous Coward | about 6 months ago | (#45933965)

round of applause [youtube.com]

xkcd is terrible! (-1, Troll)

Anonymous Coward | about 6 months ago | (#45933981)

Holy shit, nerds. xkcd is universally terrible and you're all garbage people for constantly sucking its dick. Grow up.

NP-hard? (1)

Anonymous Coward | about 6 months ago | (#45934061)

Sure, it's NP-hard, but it's also nonrecursive via Rice's theorem.

Calling this NP-hard is like calling the Andromeda Galaxy "bigger than the average rhino".

Re:NP-hard? (1)

Anonymous Coward | about 6 months ago | (#45934083)

For clarification, this is referring to the problem of writing a program that identifies regex finders. The problem of finding the shortest regex is likely NP-hard, but it's not as obvious as the article attempts to imply.Giving a shitty algorithm to solve a problem, and then saying that it would also solve SET COVER, does not imply that any algorithm for solving the first problem can be used to solve SET COVER via a Karp reduction.

Unless Pyhon has changed recently. (1)

Impy the Impiuos Imp (442658) | about 6 months ago | (#45934217)

Python code? I would expect Perl or similar if parsing was your emphasis, or Lisp or some AI language if AI was your emphasis, but not a standard block-structured language.

Re:Unless Pyhon has changed recently. (3, Informative)

bunratty (545641) | about 6 months ago | (#45934329)

Python is very similar to Perl, and also has most of the characteristics that make Lisp a good language to program AI algorithms.

Re:Unless Pyhon has changed recently. (1)

maxwell demon (590494) | about 6 months ago | (#45934469)

This is about regexes, that is, hard to decipher code that looks like line noise. Obviously Perl is the only language that matches.

Re:Unless Pyhon has changed recently. (1)

dotancohen (1015143) | about 6 months ago | (#45936929)

Additionally, Python accepts in-line comments in Regexes. That alone makes it an above-average choice.

Re:Unless Pyhon has changed recently. (1)

retchdog (1319261) | about 6 months ago | (#45936089)

Then you're a moron.

He's trying to communicate his neat ideas with as many people as he can, not optimize the shit out of something (in execution time, or length of code, or whatever). Python has become the standard language for communicating with a broad base of people who are not idiots, but not necessarily "real programmers" either. This is a good thing: it has basically replaced pseudocode.

Re:Unless Pyhon has changed recently. (2)

phantomfive (622387) | about 6 months ago | (#45936309)

Usually easier to use the language you know, rather than learn a whole new language for a project.

could make google more "googlely" (2)

LifesABeach (234436) | about 6 months ago | (#45934379)

sowing only web pages for delta airlines; and not delta faucets? that's "googlely."

Obligatory XKCD (1)

Anonymous Coward | about 6 months ago | (#45934643)

Obligatory XKCD.

Oh, never mind.

Re:Obligatory XKCD (2)

RussR42 (779993) | about 6 months ago | (#45935653)

I believe this [xkcd.com] is what you were looking for.

ah the old 1 or 2 problem (1)

deviated_prevert (1146403) | about 6 months ago | (#45936813)

//solution is simple

if a_1=nopaper

if a_2=paper

//problem with this solution though is that it tends to be gender specific,

//and that is the problem with two compared variables in a statement it can easily lead to a 3turd condition.

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

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>
Create a Slashdot Account

Loading...