Hacker News Reader

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 should start with.

To be honest I'm not even saying this puzzle should change so much as I am looking for a different puzzle to dip my toes.

I don't have any interest in starting the puzzle if I don't feel like I can put a foot down somewhere. It's like trying your first Minesweeper game, making two random clicks, and getting two `7`s. Where do you go from there? Or learning Sudoku from the hardest difficulty level, without having built up a library of patterns from the easier difficulties.

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.

Yeah I definitely get that. I've never done a puzzle of this type before, but I have done a hell of a lot of logic puzzles (thanks to the Simon Tatham collection among others) so I was able to figure out a good attack vector. I agree, it wasn't easy to find where to start nor where to make progress in the beginning. Lots of data to ingest.

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

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

It's clearly in NP. One way to solve it is to order the squares in some order and combine all the NFAs in some nasty wreath product construction. Then we seek an accepting string. While this has an exponential state size blowup you may be able to construct lazily in the BFS and perhaps that keeps the complexity down.

Depends what you think N is doesn't it? What would be a variable parameter in this puzzle? The number of letters in the alphabet? The size of the regex expressions? The size of the board?

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

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

But it's a satisfiability problem. Seems NP-complete in the general case to me.

Huh yeah that could be right... I'll have to think about it more.

I fully agree. I think it's a really interesting concept but it's missing a bit of game design skill so far.

I had the same experience when I tried it yesterday. There doesn't seem to be any good "starting point", like there is on a traditional crossword puzzle or sudoku.

I think from a game design perspective it is really interesting though: Like sudoku, this kind of puzzle gives you a wide range of options to archive different player experiences and difficulty levels: You can make easy levels by mostly using constant-width regexes and non-conditional letters and you can slowly increase the difficulty level by making regexes less constrained and more ambiguous. A designer could even craft specific "paths" through the puzzle by combining easy and hard regexes.

Finally, a designer could gradually introduce more complex regex features (or other patterns, like multiple constraints) over successive leves.

There are actually four spaces that can be filled by accounting for only a single pattern. Two of those are at the end instead of the beginning.

I agree it definitely feels imposing when you first look at it, but stick with it. Look for spaces that have a very small set of possibilities, and then try to map out what neighboring spaces could have for each possibility. If you really feel stuck, take a screenshot and mark it up.

https://regexcrossword.com/ have a lot of great puzzles with a gentler learning curve but I liked the challenge of this one, so I think it would have spoiled the fun a bit for me.

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.

Or if the string contains a C, a subsequent character can't be an R?

Doesn't it really just mean a string can't contain a C followed by an R?

Yes, those are three ways of saying the same thing. :)

Not really. Maybe I'm being overly pedantic, but my point was that the first two ways of describing it are overly specific and don't include all the strings that can be matched. Only the third option really describes all the possibilities.

What is an example of a string that can be matched which does not meet the first or second description?

Sorry, you're right. I'm not sure what I was thinking.

("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".

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

Thanks, that's exactly how I read it.

No, (X|H|H|[^XH])*` or ([XHH]|[^XH])* would be equivalent to .*, but (XHH|[^XH])* requires that XHH appear consecutively in that order whenever they appear at all.