6 ms·

Why doesnt the empty string satisfy `(DI|NS|TH|OM)*`?

• freeopinion 6y ago
  Empty string does satisfy that. This puzzle gets it wrong.
  • vitus 6y ago
    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.)
    • freeopinion 6y ago
      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?
      • nxrabl 6y ago
        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.
        • freeopinion 6y ago
          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 6y ago
            [deleted]
          • deleted 6y ago
            [deleted]
          • jcranmer 6y ago
            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*$".
            • dec0dedab0de 6y ago
              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/crossword.js#L118 https://github.com/Jimbly/regex-crossword/blob/master/crossw...
              • ladberg 6y ago
                Not anymore, hah: https://github.com/Jimbly/regex-crossword/commit/0e603975f21116718c6ed58328ae6d1ac7249628 https://github.com/Jimbly/regex-crossword/commit/0e603975f21...
                • dec0dedab0de 6y ago
                  Haha! Fantastic commit message
                  • Jimbly 6y ago
                    Glad someone appreciated it :D
            • schoen 6y ago
              Similar to "egrep -x".
      • mypalmike 6y ago
        8 spaces does not in any way match the language described by that regex. Not a partial match, not a full match. Plugging the first space into a DFA described by the regex is an immediate failure - there is no exit from the initial state initiated by the space character. It's a non match. Regex engines will say they do match because they are by default checking for for substrings that match the language (such as the initial empty string of each line of grep), not for strings that match the language. *edit: added last paragraph.
      • adrianmonk 6y ago
        The issue is two different types of regex notation. Some regex notations include "^" and "$", and some don't. A lot of software (the grep command, for example) uses the kind that does support "^" and "$". This puzzle uses the other kind. Essentially, when a notation includes "^" and "$", it allows writing cleaner more concise patterns. These notations add an implicit "." at the beginning and end of every pattern unless you use "^" or "$" to turn that off. As for how you're supposed to know this, the puzzle tell you, but there is a very strong clue, which is that many of the patterns have a leading/trailing ".". This would be totally superfluous in one type of notation, so it must be the other kind. Here are some patterns from the puzzle's notation: .*H.*H.* (DI|NS|TH|OM)* F.*[AO].*[AO].* and here are how they'd look in a notation that uses "^" and "$": H.*H ^(DI|NS|TH|OM)*$ ^F.*[AO].*[AO]
        • Jimbly 6y ago
          To be fair, the puzzle didn't tell them at the time of their post, I added the "must be a full match" line after seeing confusion here, and it was not in the original puzzle (people doing puzzle hunts are expected to deduce more than random people on the internet, I guess!).
    • freeopinion 6y ago
      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
      • deleted 6y ago
        [deleted]
      • danaliv 6y ago
        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.Match object; span=(0, 0), match=''> >>> re.fullmatch(r'R*D*M*', ' ') >>>
  • zermelo 6y ago
    nope, puzzle is fine.