Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Regex Puzzle

bbc.co.uk

Post reply on HN
Print view View original

81–90 of 97 posts

Re: Regex Puzzle

#81

Post by squeaky-clean »

dahart wrote: post #71
squeaky-clean wrote: post #69

Earlier quoted context omitted.

Yes, thank you. I of course use Linux, but I really don't care to remember the specifics of regex libraries across PHP, Python, JS or Java. So I just work out my regex, and from the drop downs choose "Use->Javascript->Chrome->Get Text From Numbered Group". And it spits out like 6 lines of JS that will handle cases of it either being found or not. You can choose the names of the ingoing and outgoing variables. You don…

The funny part (to me) is that it was already obvious you use Linux or mac -- some flavor of (star)nix -- because you said you keep a Windows install at the ready. That implies to me that Windows isn't your primary OS. I keep a Windows install at the ready too, for a whole bunch of reasons that have nothing to do with how much I like or dislike Windows. I would love to be able to remember regex specifics from lib to…

I highly recommend it if you have to deal with regex a lot. I really wish it was open-source, or there was some OSS alternative as good as it, but oh well. The tools linked above are great for simpler usage.

The built in regex step-debugger is also great, though I've learned that if I have to rely on that, it's probably not a task well suited to regex.

Re: Regex Puzzle

#82

Post by long »

eru wrote: post #79
hokkos wrote: post #22

I've worked on the project where some XSD files defined fields with regex restrictions, also some rules over fields added other stricter regexps or negative regexps depending on some context in a format called Schematron. I had to generate XML files conforming to those XSD, so I used some tools around Z3 solver and Microsoft.Automata to generate those strings conforming to multiple regexps. It would convert the regex…

There's also redgrep ( https://github.com/google/redgrep ) that supports intersection and complements of regular expressions. I am toying the idea of writing a little game where player A thinks of a regular expression, and player B tries to guess. If B guesses right, they win. If B guesses wrong, A has to provide a false positive and a false negative (if they exist), and B gets to guess again. Can you think of ways t…

In computer science academia, this kind of game is called grammar induction (of which inferring regular expressions is a special case).

A classic algorithm for inferring regular expressions was given by Angluin: https://people.eecs.berkeley.edu/~dawnsong/teaching/s10/pape...

(This isn't quite the same setup as you're thinking of but there are a ton of variations on the basic idea)

Re: Regex Puzzle

#84

Post by seven800 »

canada_dry wrote: post #15

Regex is one of those tools that I use a couple times a year - usually for cleaning up lousy input data. I always end up spending a fair amount of time using tools like: http://regex.inginf.units.it/ https://regex101.com/ http://www.regexr.com/ And of course stackoverflow.

You might also be interested in a tool I made which generates random strings that match a given regex:

http://regexicon.com/

Very useful when code reviewing other people's regular expressions.

Re: Regex Puzzle

#85

Post by chpatrick »

andyjohnson0 wrote: post #7

I know that there are problems to do with regex matching that are NP-hard. So I'm wondering if it is possible to attack this puzzle using an algorithm that simplifies the individual regexes using knowledge of the regexes that that they interact with?

You can solve it using a SAT solver like Z3. There are particularly elegant solutions in Haskell that basically interpret the regex but on "symbolic" characters rather than real ones. You can then ask what values these characters can take such that all regexes match.

Some implementations: https://github.com/ekmett/ersatz/tree/master/examples/regexp... https://gist.github.com/LeventErkok/4942496

Re: Regex Puzzle

#86

Post by Xophmeister »

That wasn't as hard as I thought it would be. I was worried that, without stard/end of string anchors, things could get quite hairy, but the biggest stretch of logic was just, "There are five spaces for me to fit a character, an optional characters and two two-character sequences. Therefore that optional character must not appear."

Re: Regex Puzzle

#87

Post by eru »

long wrote: post #82
eru wrote: post #79

Earlier quoted context omitted.

There's also redgrep ( https://github.com/google/redgrep ) that supports intersection and complements of regular expressions. I am toying the idea of writing a little game where player A thinks of a regular expression, and player B tries to guess. If B guesses right, they win. If B guesses wrong, A has to provide a false positive and a false negative (if they exist), and B gets to guess again. Can you think of ways t…

In computer science academia, this kind of game is called grammar induction (of which inferring regular expressions is a special case). A classic algorithm for inferring regular expressions was given by Angluin: https://people.eecs.berkeley.edu/~dawnsong/teaching/s10/pape... (This isn't quite the same setup as you're thinking of but there are a ton of variations on the basic idea)

Thanks. I had figured out that grammar induction was the right word to look for a while ago. (But took me a bit to find it.) I know the paper you linked to, but yes, it's not quite the right setup.

Re: Regex Puzzle

#88

Post by long »

eru wrote: post #87
long wrote: post #82

Earlier quoted context omitted.

In computer science academia, this kind of game is called grammar induction (of which inferring regular expressions is a special case). A classic algorithm for inferring regular expressions was given by Angluin: https://people.eecs.berkeley.edu/~dawnsong/teaching/s10/pape... (This isn't quite the same setup as you're thinking of but there are a ton of variations on the basic idea)

Thanks. I had figured out that grammar induction was the right word to look for a while ago. (But took me a bit to find it.) I know the paper you linked to, but yes, it's not quite the right setup.

There's a conference on grammar induction called ICGI; might wanna browse through the proceedings to see if there's anything closer.

Re: Regex Puzzle

#89

Post by eru »

long wrote: post #88
eru wrote: post #87

Earlier quoted context omitted.

Thanks. I had figured out that grammar induction was the right word to look for a while ago. (But took me a bit to find it.) I know the paper you linked to, but yes, it's not quite the right setup.

There's a conference on grammar induction called ICGI; might wanna browse through the proceedings to see if there's anything closer.

Thanks!

I'm basically interested in the equivalent of the "guessing game" for regular expressions. (See eg https://stackoverflow.com/questions/5440688/the-guess-the-nu... for a rational number solution.)

With a fixed guesser, that would encode all regular expressions / finite automata as sequences of binary digits. (But in a interestingly different way from just serializing the table for a DFA, or writing down the regular expression in ASCII characters.)

Re: Regex Puzzle

#90

Post by long »

eru wrote: post #89
long wrote: post #88

Earlier quoted context omitted.

There's a conference on grammar induction called ICGI; might wanna browse through the proceedings to see if there's anything closer.

Thanks! I'm basically interested in the equivalent of the "guessing game" for regular expressions. (See eg https://stackoverflow.com/questions/5440688/the-guess-the-nu... for a rational number solution.) With a fixed guesser, that would encode all regular expressions / finite automata as sequences of binary digits. (But in a interestingly different way from just serializing the table for a DFA, or writing down the re…

So I do AI research on something pretty related to the guessing game -- I'll shoot you an email.
Post reply on HN