I came across the Regex Golf site, which contains regex challenges: there are two columns: "match all of these" and "match none of these" and the intension is to create a regex that's as short as possible to fit the requirements.
Would this kind of challenges be interesting for Programming Puzzles and Code Golf? I do not mean that we should copy challenges from there, but I'm just asking whether it would be interesting.
Honestly, I don't see why not. They're code golf puzzles, just like any other, and thus well within our scope.
That said, I agree that there are some potential issue with such challenges. Let me try to respond to some of them point by point, and argue why they don't really matter that much (or at least don't require immediate action):
"We're being / going to be flooded with them."
Well, yes. (Although five is hardly a flood yet.) That's what happens when something ends up on XKCD. The thing is, though, that it's a fad, and like all fads, it's going to pass and settle down to a more sustainable level. We've just had the same issue with code-trolling, but that seems to have peaked now — I don't see a single troll question on the front page right now. I fully expect the same to happen with regex golf in a week or two at most.
"There's no originality in picking two arbitrary sets and asking for a regexp to distinguish them."
No, there isn't, just like there's no originality in picking an arbitrary piece of text and asking for the shortest program to print it. Yet we haven't really had an issue with that.
The thing is, the community here is pretty good at voting up challenges they think are interesting, and voting down those they think are boring. If you're going to post yet another "print this text" golf challenge and want some upvotes for it, you'd better include something in it that makes it different from all the n+1 previous ones. I expect it's going to work just the same way for regex golf, too.
"They're just going to be solved by computer-generated regexps."
I doubt it. Or at least, I hope not. If that does end up happening regularly, I do agree with Peter Taylor's suggestion that they should be closed as duplicates of the meta-challenge. But let's wait a while and see if that'll actually happen, instead of just assuming that it will.
The thing is, regex golf is NP-hard. That means you're never going to have an algorithm that would be guaranteed to find the optimal solution in reasonable time. Sure, there are heuristics that can produce pretty good solutions pretty efficiently, but most of the time, a sufficiently clever human can find tricks to improve them that the program simply never considered. Which is what makes it fun.
"Allowing only regexp solutions makes it boring."
You mean like Perl Golf is boring, because you can only use Perl?
Yes, we've decided that challenges on this site are language-agnostic by default, and I think that's a good decision. But that doesn't make the occasional language-specific questions off topic, nor does it necessarily make them boring. Sometimes, a challenge only makes sense in a specific language; sometimes, constraining the language just spices up an old challenge. And sometimes, maybe you just don't want GolfScript / APL to always win. ;-)
But if you still think so, feel free to post a language-agnostic "distinguish these sets" challenge. It could be fun!
As a counter point to @Chrisjester-Young I would say that it is a benefit that regex is at least somewhat language agnostic. This levels the playing field allowing at least some competitions to take place that regardless of your language of choice.
I have to at least partially agree with the fact that the solutions may all lead to the same general answer, but this is not necessarily the case for complex word lists.
I would say golfing is productive in that it forces you to look at and practice with whatever language your working with in an extreme situation. I would say regex golf has the potential to do this.
Finally, in all honesty it may not be a great fit for site. Anyone can create two random word lists and post them meaning the solutions while interesting are a little arbitrary. It could devolve into something similar to doing Sudoku or a crossword puzzles.
PS @PeterTaylor I'm sure that programs can find general solutions, but for complex word lists I'm pretty sure the results wouldn't be optimal. The logic I used for the two problems I posted and solved by hand (I created a small utility to test my regex, but not to actually do any solving) I would find very hard to program the logic or just brute force a near-optimal or optimal solution. Though I'm sure there are ways.
Regex golf can be really interesting: Hard code golf: Regex for divisibility by 7. The questions inspired by the xkcd will be fun for a while, and I expect 'em to die off. I figured it was a fun enough challenge to post one. My expectations of the problem were that it'd generate some more copycats, that it would raise a small ruckus here, and that people would get bored of it before too long.
I also wanted to establish some reasonable ground rules because I felt that their existence was inevitable due to the xkcd comic -- thus, I posted my question with alacrity, skipping the vetting here, to 'pull the bandaid off'. I think it went well, personally.
Different languages support different things in their regular expressions. What I love about this site is that things are a fast & loose. We pit languages against eachother, and dirty tricks are often encouraged. Languages are not on a level playing field, and obscure knowledge of multiple languages is highly incentivized. You won't find that at the regex-golf site.
Edit: I've now gotten my solutions on http://regex.alf.au honed to a point that I need to stop improving them and move on with life (though I'll tinker with alphabetize some more when I have time...). This is a blast. 3-divisibility? Primes? Palindromes? Matching parentheses? These are great problems. Problems like this should be welcome on the site. Distinguishing between two crap lists of random objects? Boring except for the metagolfers. But some of these are just gold.
In this post, I am speaking as a user, not a moderator.
To me, part of the appeal of this site is seeing a variety of different solution approaches, in a variety of languages. While I think regex golf is fun, I don't think it provides either of these attributes, so I would prefer not to see such questions here.
In my view, there are two types of regex golfs -- ones with clear patterns that test if you understand regex (most of the ones here ) and ones where you match random lists of words (The subtitles of Star Trek films to Star Wars). Neither of these make for good problems for this site.
The first type are fun problems, but probably too close-ended for this site -- most people familiar with regex instantly will write out the straightforward answer when there's a clearly optimal answer (e.g., the first four problems on http://regex.alf.nu/ where you can see the pattern quickly)). Occasionally, you can modestly improve upon the straightforward solution. E.g., to the powers problem (#13 at http://regex.alf.nu) (matching the string x^(2^i) where i=0,1,2,...,10) has a straightforward 45-char solution:
^((((((((((x)\10?)\9?)\8?)\7?)\6?)\5?)\4?)\3?)\2?)\1?$
but code golfing it you can reduce it to 43-char ^(((((((((xx?)\9?)\8?)\7?)\6?)\5?)\4?)\3?)\2?)\1?$. Also, if you don't mind picking up some matches not in the positive set (but not in the specifically negated set), you can reduce it to at least 38 characters with ^(xx?|xxxx|x{8}|x{16}|x{32}|(x{64})*)$ (which matches a string of 192 x's, despite 192 not being in the form 2^(2^i). But again, rather quickly you reach the best solution as there are only a few ideas to really use.
The second type of matching one list without matching a second list of random items is silly. Doing it by hand is going to be significantly worse unless you use custom-written tools (that may not do all the work for you; e.g., you suggest clauses by looking at the words not matched so far). The other problem is the second type will generally be uninsightful or clever as you are so constrained (must use a regex and must match these words). While the problem is NP hard, the problem size is also quite small and humans are also bad at NP hard problems.
I'd have no problem with their being one regex golf problem of the random list type, but I don't think there should be many of them. Each code golf problem of distinct lists is often quite similar, similar to how it makes sense to allow "Calculate 6*9 in different bases" (reference to hitchhiker's guide to the galaxy question and answer), but it wouldn't make sense to repeat the question many times with different products.
I suspect that most answers would be produced by taking a program which would be a suitable submission to Meta regex golf and maybe doing a bit of manual tweaking to optimise. As such, I think there's a case for closing regex golf questions as duplicates (specifically, specialisations) of that question.
