NY Times Mon < Tue < Wed < Thu < Fri < Sat < Sun < British Cryptic < RegEx
I would put Sunday between Thursday & Friday, just way more annoying due to grid size
[deleted]
RegEx Crossword
81–90 of 160 posts
Re: RegEx Crossword
#82It took me 1 hour 30 minutes. Have to say, this is so well designed. Love it.
Re: RegEx Crossword
#83Earlier 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?
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.
Re: RegEx Crossword
#84Earlier quoted context omitted.
What solutions were you trying? As far as I can tell, the puzzle is fully constrained. From the start, the bottom-left cell as well as the right column can be solved just from the starting hints, and then you can derive the top-left cell per the backreference. In particular, you can reframe the right column's hint as (AB|OO|OR), and only one of those satisfies the bottom row's hint.
Not so. Something as simple as "OO\nDO" should be valid. But also "OO\nDD" and myriad other solutions.
Ah. The difference is that you're trying partial matches, as opposed to full matches from the specified patterns.
edit: and by full match (since this seems to be the source of some confusion in another subthread), I explicitly mean anchored with your \A...\Z or whatever you want to use.
Re: RegEx Crossword
#85Earlier quoted context omitted.
I think some people may have thought you just have to match any substring within it, so I was clarifying that the whole line has to be a match.
Some people would be correct to think that. That is what those regexes mean. If you are secretly prepending a ^ and appending a $, then you are not using the regex displayed.
Sorry, but you're wrong. There's nothing about regular expressions that means you have to use them to search for matching substrings. That's just one particular operation that uses regular expressions. It's not a quality inherent to regular expressions themselves. There are many different operations you can perform with a regular expression besides a substring search.
Python, for example, has a fullmatch method.[0]
libicu's matches() function returns true "if the pattern matches the entire string, from the start through to the last character."[1]
PCRE has various flags that change what it means for a regular expression to match, including PCRE2_ANCHORED and PCRE2_ENDANCHORED. Used together, these options would require a full match with no change to the regular expression itself.[2]
0. https://docs.python.org/3/library/re.html
1. https://unicode-org.github.io/icu/userguide/strings/regexp.h...
Re: RegEx Crossword
#86Brilliant. I wonder how it was made?
I solved this in about 1.5 hours by starting at the top left, entering any string that satisfied at least one condition, then moving on to the next condition and “fixing up” any previous entries. I was fearful that I might arrive at a nearly correct solution that I would have to massively backtrack from, but it didn’t happen - I only needed a few short backtracks. I think the large number of constraints helps a lot.
Re: RegEx Crossword
#87Awesome puzzle! Can be completed without guesses. Any ideas how it was invented?
Look at the original MIT Mystery Hunt page (and solution). It was part of a puzzle hunt. (I was one of the people who successfully solved it on my team during that very event back in 2013...)
See this comment for the link to the original, including the author's name and the puzzle in context with its official solution:
https://news.ycombinator.com/item?id=26439598
(I wish that other comment would get upvoted to the top -- this was written by an identifiable person for a specific identifiable puzzle event, so it's not like mysterious anonymous Internet folklore or something.)
Re: RegEx Crossword
#88Brilliant. I wonder how it was made? I solved this in about 1.5 hours by starting at the top left, entering any string that satisfied at least one condition, then moving on to the next condition and “fixing up” any previous entries. I was fearful that I might arrive at a nearly correct solution that I would have to massively backtrack from, but it didn’t happen - I only needed a few short backtracks. I think the larg…
See this comment
https://news.ycombinator.com/item?id=26439598
for proper credit to the original author (and place of publication).
Re: RegEx Crossword
#89What a game! Thanks for this.
It took me close to three hours to solve this, hahaha
Re: RegEx Crossword
#90Earlier quoted context omitted.
What solutions were you trying? As far as I can tell, the puzzle is fully constrained. From the start, the bottom-left cell as well as the right column can be solved just from the starting hints, and then you can derive the top-left cell per the backreference. In particular, you can reframe the right column's hint as (AB|OO|OR), and only one of those satisfies the bottom row's hint.
Not so. Something as simple as "OO\nDO" should be valid. But also "OO\nDD" and myriad other solutions.
[deleted]