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

41–50 of 97 posts

Re: Regex Puzzle

#42

Post by eutectic »

jonahx wrote: post #39
eutectic wrote: post #28

Earlier quoted context omitted.

This problem is NP-hard by reduction from SAT. Treat each column as a truth variable and use the rows to encode CNF clauses. For example, `(A | ^C)` becomes `(1..)|(..0)`. Then set all the column regexes to `( 0* )|( 1* )` to enforce a consistent truth value for each variable.

Could you elaborate on the encoding? What are valid mappings?

A variable becomes '1' in the corresponding position and '.' everywhere else, and similarly with negations of variables and '0'. The regex is then just an alternation of these sub-regexes. This incurs just a linear blow-up in the number of variables, for the '.'s.

For an n x m grid, you can encode any CNF formula with n clauses on m variables. See here if you are unfamiliar with CNF: https://en.wikipedia.org/wiki/Conjunctive_normal_form

Re: Regex Puzzle

#44

Post by hokkos »

jfries wrote: post #24
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…

How did you solve backreferences with that approach?

I had the luck that XSD regex doesn't support backreference.

Re: Regex Puzzle

#45

Post by shabble »

Does any common regex format/dialect require '\-' for a literal hyphen? AFAIK it's only special inside character classes, and escaping it doesn't necessarily work there if it would form a valid range identifier.

Re: Regex Puzzle

#46

Post by rspeer »

dmit wrote: post #41
dbrgn wrote: post #8

If you want a challenge, try this one: http://twiki.org/p/pub/Codev/TWikiPresentation2013x03x07/reg...

Originally from the MIT Mystery Hunt: https://devjoe.appspot.com/huntindex/puzzle/mit2013601 PDF: http://web.mit.edu/puzzle/www/2013/coinheist.com/rubik/a_reg...

Note that as a Mystery Hunt puzzle, the goal of the puzzle isn't just to fill in the grid, it's to find the answer, a secret word or phrase that would be filled into another puzzle (the metapuzzle).

The puzzles generally don't tell you how to extract the answer, but the idea is you know it when you see it.

Re: Regex Puzzle

#47

Post by angry_albatross »

samjs wrote: post #38
bluesmoon wrote: post #3

Well, there is https://regexcrossword.com/

The OP converted into this format: https://regexcrossword.com/playerpuzzles/595e5542d2433

There's an error in the second "Across" expression. [^PZVJG]{4}(.)[EFUG]{6}(.)[^\sPZVJI]{2} should be [^PZVJG]{4}(.)[EFUG]{6}\1[^\sPZVJI]{2}

Re: Regex Puzzle

#48

Post by vacri »

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.

As I get more experienced in operations, I find regex to be more and more invaluable. I used to dread doing a regex, now I get enjoyment out of sorting out a tricky one.

Re: Regex Puzzle

#49

Post by okdana »

shabble wrote: post #45

Does any common regex format/dialect require '\-' for a literal hyphen? AFAIK it's only special inside character classes, and escaping it doesn't necessarily work there if it would form a valid range identifier.

I don't know of any that require it. But it's common to see punctuation characters escaped like that because Perl (and PCRE and its various cousins/descendants) allows you to escape any non-meta-character and have it treated as a literal.

I suppose the two main benefits are

(a) neither the writer nor the reader has to remember which punctuation characters are meta-characters (you just have to remember that it's always a literal if it's escaped), and

(b) in implementations like PHP's which try to replicate the Perl-style 'delimited' syntax (e.g., /foo/), it prevents characters in the pattern from conflicting with the delimiters.

Maybe there's some other advantage but i can't think of what.

Re: Regex Puzzle

#50

Post by rootlocus »

jgrahamc wrote: post #6

Worth doing this by hand to exercise your knowledge of regular expressions. My solution (SPOILER): http://imgur.com/a/9iK9J

I'm assuming the solution isn't unique because I found some positions that are under-constrained.
Post reply on HN