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

RegEx Crossword

jimbly.github.io

Post reply on HN
Print view View original

71–80 of 160 posts

Re: RegEx Crossword

#71

Post by [deleted] »

freeopinion wrote: post #63
nxrabl wrote: post #60

Earlier quoted context omitted.

I assume by 'full match' they mean: - the pattern is found in the input - the start of the match is the start of the input - the end of the match is the end of the input By this definition, 8 spaces does not match the pattern.

I don't know what any of your three statements actually mean. R*D*M* does not specify anything that has to be found in the string. Nor does any pattern of ()* or []* no matter what you put between the parens or brackets. In all of those cases, any possible string matches the regex starting at the beginning of the string and ending at the end of the string. Your clarification doesn't clarify anything for me.

[deleted]

Re: RegEx Crossword

#73

Post by dandanua »

EGreg wrote: post #24
afranchuk wrote: post #21

Earlier quoted context omitted.

I just completed it, and can say with certainty that it is solvable by only taking into consideration two constraints at any given time, with the exception of 3 at just one point early on (and they were the easier constraints in the puzzle). That being said, the nature of regex means you kind of need to jump around as far as which constraints you combine.

Is the complexity basically NP-hard, equivalent to a SAT solver or even harder?

Nonograms are np-complete, so this type of puzzles is also np-complete.

Re: RegEx Crossword

#76

Post by jcranmer »

freeopinion wrote: post #63
nxrabl wrote: post #60

Earlier quoted context omitted.

I assume by 'full match' they mean: - the pattern is found in the input - the start of the match is the start of the input - the end of the match is the end of the input By this definition, 8 spaces does not match the pattern.

I don't know what any of your three statements actually mean. R*D*M* does not specify anything that has to be found in the string. Nor does any pattern of ()* or []* no matter what you put between the parens or brackets. In all of those cases, any possible string matches the regex starting at the beginning of the string and ending at the end of the string. Your clarification doesn't clarify anything for me.

The regex crossword is working on the basis of matching the entire input string (of " "), not on finding a substring that matches the regex. You can prefer to think of it as having all regexes have an implicit ^ and $, i.e., you're attempting to find a substring that matches "^RDM*$".

Re: RegEx Crossword

#77

Post by chaorace »

freeopinion wrote: post #64
ladberg wrote: post #59

Earlier quoted context omitted.

That's not the case... .(C|HH)* matches with single character followed by any number of C's or HH's. So " " or "B" would work but in the puzzle the full line has to match so those aren't possible

Can you explain what you are seeing about "B" that does not match? Or about "_______"?

As you can see[1], the regex checker is based on the JS RegExp.match method. Each cell is always 1 character long (so, either a letter of some kind or an empty space). The str parameter for the check function is assembled by concatenating these cells together[2], so the input string for an empty line will look something like this: "_______"

Assuming an empty 7-cell row, the regex in question will match 7 times, once for each character. A result of multiple partial matches is not equivalent to getting just one perfect match, which is what the puzzle requires. Internally, the puzzle enforces this requirement by making each Regex rule require a full line match (see line 118: '^' + rule + '$').

Personally speaking, I felt like that was the most intuitive way to interpret the mechanics of the game, so I'm willing to give the programmer a pass when they slightly modify the regex rule prior to evaluation.

[1]:https://github.com/Jimbly/regex-crossword/blob/8b178f32eba37... [2]:https://i.imgur.com/PS0BmJ6.png

Re: RegEx Crossword

#78

Post by reificator »

vcxy wrote: post #52
reificator wrote: post #25

Earlier quoted context omitted.

I don't doubt that, and I don't doubt it's a good puzzle, especially if you're already familiar with the format. But since this is my first introduction to this kind of puzzle, I need some anchor points at the beginning so I feel like I have something to work off of. I'm not even asking for a whole row, just an easier set of known chars at the start of the round so I have a hint at which of the 39 constraints I shoul…

I did complete and enjoy it, but I'm both very competent with regex like you, but also big into sudoku variants (as in the youtube channel cracking the cryptic! [1]) so this felt like it was designed for me to enjoy. Considering it took me about half an hour, I'd expect someone who isn't into these kinds of odd puzzles already to basically have exactly your reaction. [1] https://www.youtube.com/c/CrackingTheCryptic

I don't watch regularly (and I would consider myself a sudoku dabbler) but I've seen some Cracking the Cryptic videos in the past and enjoyed them greatly.

Re: RegEx Crossword

#79

Post by dec0dedab0de »

jcranmer wrote: post #76
freeopinion wrote: post #63

Earlier quoted context omitted.

I don't know what any of your three statements actually mean. R*D*M* does not specify anything that has to be found in the string. Nor does any pattern of ()* or []* no matter what you put between the parens or brackets. In all of those cases, any possible string matches the regex starting at the beginning of the string and ending at the end of the string. Your clarification doesn't clarify anything for me.

The regex crossword is working on the basis of matching the entire input string (of " "), not on finding a substring that matches the regex. You can prefer to think of it as having all regexes have an implicit ^ and $, i.e., you're attempting to find a substring that matches "^R D M*$".

You can prefer to think of it as having all regexes have an implicit ^ and $

That is literally what is happening: https://github.com/Jimbly/regex-crossword/blob/master/crossw...

Re: RegEx Crossword

#80

Post by utborin »

freeopinion wrote: post #61
vitus wrote: post #38

Earlier quoted context omitted.

That's because it's not empty string in the puzzle, it's 8 spaces. (and on top of that, we're doing a full match.)

R*D*M* should match empty string or a string of 8 spaces. or any combination of characters. It should be impossible not to match. Edit: Fix HN oddity

A full match has to exhaust all of the characters in the string. R*D*M* is indeed a match for a string of eight spaces, but it isn't a full match, because there are still eight spaces left over after matching.

    % python3
    >>> import re
    >>> re.search(r'R*D*M*', '        ')
    
    >>> re.fullmatch(r'R*D*M*', '        ')
    >>>
Post reply on HN