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

Regex Crossword

regexcrossword.com

Post reply on HN
Print view View original

61–70 of 115 posts

Re: Regex Crossword

#61

Post by zatkin »

baby wrote: post #58

http://regexcrossword.com/challenges/intermediate/puzzles/5 Anyone understand what (.)*DO\1 should match? edit: Okay, I was writting 0 instead of O that's why it wasn't working.

Anything 0 or more times backreferenced onto the end of the string "DO", is my guess. So, for example:

  DO
  DONUT
  DOG

Re: Regex Crossword

#62

Post by cataflam »

baby wrote: post #58

http://regexcrossword.com/challenges/intermediate/puzzles/5 Anyone understand what (.)*DO\1 should match? edit: Okay, I was writting 0 instead of O that's why it wasn't working.

. -> any character

(.) -> any character, grouped to reference it, since it's the first group it's referenced as \1

(.)* -> that, 0 or more times

(.)* DO -> any character 0 or more times, followed by DO

(.)* DO\1 -> any character 0 or more times, followed by DO, and the same character as in the beginning

Re: Regex Crossword

#63

Post by quink »

Bahamut wrote: post #43
Robadob wrote: post #16

My main problem with this is telling the difference between O and 0, the clue O's look more like 0 so I have to copy paste them. (Although I don't think I've had any numbers required for solutions yet).

The zeroes have a slash through them on my browser - does yours not have that?

Mine too. Although when you've got [0-3] and [^2O13] in the other, it's not too difficult to figure out that contradiction fairly quickly.

Re: Regex Crossword

#64

Post by mgraczyk »

toastedzergling wrote: post #57

I really dislike that patterns using * wildcard required using the letters beforehand. The game requires A* to match a row with zero or more A's, but this is absolutely incorrect, as A* will gladly match ANY string, like QQQQ.

That isn't how the Kleene star works.

A* is "the set of all strings over the alphabet {A}, including the empty string ε."

"QQQQ" is not a string over the alphabet {A} because it contains the symbol 'Q', which is not in {A}.

Re: Regex Crossword

#65

Post by throwaway_yy2Di »

These crosswords are NP-hard! D: Here's a short encoding of 3SAT:

Alphabet: [01]

Number of variables: N

Columns: one for each clause, i.e.:

    r/.0...|..1..|....1/
    
    (-x2 V x3 V x5)
They're disjunctions of three regexps of length N. Each alternative fixes one positional variable to either 0 or 1, and ignores the rest.

Rows: one for each variable, forcing it to be single-valued across the clauses:

    r/0+|1+/

Re: Regex Crossword

#66

Post by eridius »

toastedzergling wrote: post #57

I really dislike that patterns using * wildcard required using the letters beforehand. The game requires A* to match a row with zero or more A's, but this is absolutely incorrect, as A* will gladly match ANY string, like QQQQ.

That's not an issue with A*. Every regex here has an implied anchor to the start and end of the string.

Re: Regex Crossword

#68

Post by tlrobinson »

Edmontonian wrote: post #67

What does it mean when a reg ex ends with a `\1` (backslash 1) as in this example third beginner puzzle? (.)+\1 http://regexcrossword.com/challenges/beginner/puzzles/3

It's a backreference to the first capture group, which is denoted by the first set of parenthesis, e.x.

    (.*)+\1
would match "ABAB", or "ABCABC", etc.

"\2" would match the second capture group, e.x.

    (.*)(.*)\2\1
would match "ABBA", or "AABBBBAA", etc.
Post reply on HN