5 ms·
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
by afranchuk 6y ago
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.
- EGreg 6y agoIs the complexity basically NP-hard, equivalent to a SAT solver or even harder?
- ladberg 6y agoNope, it's basic regex so not NP-hard.
- dandanua 6y agoNonograms are np-complete, so this type of puzzles is also np-complete.
- wbl 6y agoIt'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.
- cammil 6y agoDepends 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?
- reificator 6y agoI 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.
- teawrecks 6y agoAll 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)*.?
- vcxy 6y agoI 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 https://www.youtube.com/c/CrackingTheCryptic
- reificator 6y agoI 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.
- afranchuk 6y agoYeah 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.