Hacker News Reader

Comment by freeopinion | Hacker News Reader

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?

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.

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.

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*$".

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/crossw...

Not anymore, hah: https://github.com/Jimbly/regex-crossword/commit/0e603975f21...

Haha! Fantastic commit message

Glad someone appreciated it :D

Similar to "egrep -x".

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.

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]

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

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

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*', '        ')
    >>>

nope, puzzle is fine.

Reply on news.ycombinator.com