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

41–50 of 160 posts

Re: RegEx Crossword

#41

Post by Guvante »

ryangittins wrote: post #32
reificator wrote: post #18

So many of these start or end with an `x*`, `(x|y)`, `[xy]` or `[^xy]` that I only see two characters I can fill in before I need to start looking at multiple constraints for the same cell and either doing combinatorics or guess-and-check. This might be fine for hard mode, but as someone who considers themselves a regexpert it's not very approachable as a first puzzle IMO. A more gradual introduction to the format wo…

Agreed. Some of them can be simplified quite a bit, which leads to a lot of clutter. For instance, (XHH|[^XH])* is equivalent to just .* EDIT: It looks like I read the regex wrong. I guess I need to do the puzzle after all!

("The sequence XHH" or "any character by X or H") repeated 0 or more times. Is not the same thing.

It is "If any of X or H appear they appear in a sequence exactly matching XHH".

Re: RegEx Crossword

#42

Post by ladberg »

freeopinion wrote: post #33

Right away the red and green hints are wrong. Either that or this puzzle used RegEx rules that contradict those I am familiar with. Either way, they lost my attention.

They seem to be accurate under all normal regex rules. Keep in mind that empty values are spaces and a full match is needed!

Re: RegEx Crossword

#43

Post by ladberg »

ufo wrote: post #16

Is it supposed to have an unique solution or are multiple solutions possible?

Just did it, there's a unique solution and you can get to it just by considering a few rules at a time (i.e. no long backtracking).

Re: RegEx Crossword

#44

Post by ryangittins »

ladberg wrote: post #40
ryangittins wrote: post #32

Earlier quoted context omitted.

Agreed. Some of them can be simplified quite a bit, which leads to a lot of clutter. For instance, (XHH|[^XH])* is equivalent to just .* EDIT: It looks like I read the regex wrong. I guess I need to do the puzzle after all!

Those are not equivalent, I think you're thinking of [XHH] instead of XHH.

Thanks, that's exactly how I read it.

Re: RegEx Crossword

#45

Post by ladberg »

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?

Nope, it's basic regex so not NP-hard.

Re: RegEx Crossword

#47

Post by rav »

ryangittins wrote: post #32
reificator wrote: post #18

So many of these start or end with an `x*`, `(x|y)`, `[xy]` or `[^xy]` that I only see two characters I can fill in before I need to start looking at multiple constraints for the same cell and either doing combinatorics or guess-and-check. This might be fine for hard mode, but as someone who considers themselves a regexpert it's not very approachable as a first puzzle IMO. A more gradual introduction to the format wo…

Agreed. Some of them can be simplified quite a bit, which leads to a lot of clutter. For instance, (XHH|[^XH])* is equivalent to just .* EDIT: It looks like I read the regex wrong. I guess I need to do the puzzle after all!

I found other patterns that I thought were unsimplified, but (spoiler alert) in the end it turned out that all of the seemingly-unnecessary details were important for the solution! E.g.

    [^C]*[^R]*
LOOKS unsimplified, but it actually means that if the string contains an R, the preceding characters CANNOT be C.

Re: RegEx Crossword

#48

Post by teawrecks »

reificator wrote: post #25
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.

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…

All the ones that start/end with a constant can be filled in immediately. This forces some others that can only be certain strings, ex. (RR|HHHH)*.?

Re: RegEx Crossword

#49

Post by freeopinion »

vitus wrote: post #38
freeopinion wrote: post #34

Earlier quoted context omitted.

Empty string does satisfy that. This puzzle gets it wrong.

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.)

8 spaces also matches. I don't know what you mean by a full match. Do you mean that you are using a different RegEx than the one displayed?
Post reply on HN