[HN Gopher] RegEx Crossword
___________________________________________________________________
RegEx Crossword
Author : andrelaszlo
Score : 164 points
Date : 2021-03-12 18:39 UTC (4 hours ago)
(HTM) web link (jimbly.github.io)
(TXT) w3m dump (jimbly.github.io)
| jedberg wrote:
| Oh man. This broke my brain just trying to get one of them
| without breaking all of the ones that crossed it. I love this.
| superfamicom wrote:
| These sort of games are great as an educational tool, a simpler
| one would be a nice intro before going to hard mode though.
| hk__2 wrote:
| See also https://regexcrossword.com/, which has been discussed a
| lot on HN.
| chaorace wrote:
| It took me just under 2.5 hours. How are you folks faring?
|
| Tip: Ctrl-Z is your friend ;)
| zermelo wrote:
| Yep, 1h5 hours for me!
| Minor49er wrote:
| This is awesome. I wish there was a way to rotate the cells so
| you could see them straightened out. Otherwise, this is like the
| final boss to every Regex Golf game I've seen
| carols10cents wrote:
| NY Times Mon < Tue < Wed < Thu < Fri < Sat < Sun < British
| Cryptic < RegEx
| eludwig wrote:
| I would put Sunday between Thursday & Friday, just way more
| annoying due to grid size
| phonebucket wrote:
| I thought I could handle RegEx, but this has given me a
| legitimate inferiority complex.
| ehsankia wrote:
| Small feature request for this implementation: Highlight/bold the
| three impacted regex when selecting a given hexagon, trying to
| trace it manually by eye is a bit of a pain.
|
| (I guess I could PR on github when I get some time later today)
| gotostatement wrote:
| Why doesnt the empty string satisfy `(DI|NS|TH|OM)*`?
| freeopinion wrote:
| Empty string does satisfy that. This puzzle gets it wrong.
| vitus wrote:
| 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 wrote:
| 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]
| freeopinion wrote:
| 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 wrote:
| 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 wrote:
| 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]
| danaliv wrote:
| % python3 >>> import re >>>
| re.search(r'R*D*M*', ' ') <re.Match
| object; span=(0, 0), match=''> >>>
| re.fullmatch(r'R*D*M*', ' ') >>>
|
| "Full match" means the pattern is found in the string,
| and the pattern accounts for the entire string. R*D*M* is
| not a full match for a string of eight spaces because the
| matched sequence--the empty string--is not the whole
| string.
| jcranmer wrote:
| 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
| "^R _D_ M*$".
| dec0dedab0de wrote:
| _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...
| zermelo wrote:
| nope, puzzle is fine.
| dandanua wrote:
| Awesome puzzle! Can be completed without guesses.
|
| Any ideas how it was invented?
| WarOnPrivacy wrote:
| Well, there went my weekend.
| Naac wrote:
| Any reason why this is implement as a hex instead of the
| traditional crossword style?
|
| There isn't a technical reason why the traditional crossword
| format can't have clues in the shape of regex right?
| lesquivemeau wrote:
| "Hexagons are the bestagons"
| neolog wrote:
| Does the hex mean each cell has more adjacencies?
| ehsankia wrote:
| There are plenty of normal regex crosswords out there. What
| makes this one special is the fact that it's in a hex format.
| If anything, regex is actually what allows people to even make
| hexagonal crosswords, I don't think it would possible to get
| any reasonably sized one with normal words.
|
| They just went the extra mile to make an special puzzle.
| ZeroGravitas wrote:
| Don't think there's a technical reason. I'd previously seen
| this site linked from here that does it slightly more
| traditionally:
|
| https://regexcrossword.com/
| freeopinion wrote:
| Lost interest on 3rd beginner puzzle when validation failed
| for multiple valid solutions.
| vitus wrote:
| 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.
| freeopinion wrote:
| Not so.
|
| Something as simple as "OO\nDO" should be valid. But also
| "OO\nDD" and myriad other solutions.
| minitoar wrote:
| IIRC the more advanced puzzles here are also hexagonal.
| kjhughes wrote:
| The hexagonal layout allows three regex constraints to be
| imposed on each cell rather than two for a rectangular layout,
| providing additional challenge.
| tzury wrote:
| Regex Golf used to be my game
|
| https://alf.nu/RegexGolf
| glsdfgkjsklfj wrote:
| 99pct of the challenge is counting the positions for things.
|
| Would be nice if they had a couple hand mande puzzles instead of
| random ones.
| heroHACK17 wrote:
| Omg
| nfoz wrote:
| This was fun :)
| anderskaseorg wrote:
| This puzzle was originally written by Dan Gulotta for the 2013
| MIT Mystery Hunt.
|
| https://web.mit.edu/puzzle/www/2013/coinheist.com/rubik/a_re...
| ufo wrote:
| Is it supposed to have an unique solution or are multiple
| solutions possible?
| sevencolors wrote:
| The solution:
| https://www.i-programmer.info/images/stories/News/2014/Dec/B...
|
| Aren't crosswords supposed to spell out a word? This feels like
| random characters. Unless i'm supposed to rotate it or
| something?
| [deleted]
| ladberg wrote:
| Just did it, there's a unique solution and you can get to it
| just by considering a few rules at a time (i.e. no long
| backtracking).
| hateful wrote:
| Also, are the answers real words, or random strings?
| ufo wrote:
| It has to be fake words. It's possible to see this because
| some of the words have to contain things like "cdd", "rrp"
| and "rxo", which aren't part of any real words.
| hateful wrote:
| Plus, now that I think about it, having a grid without the
| gaps usual crosswords have would be very complex to create
| with actual words. Even more so when using hexagons.
| ineptech wrote:
| This is an absolute classic! It is not just an exercise in tedium
| or repetition, it has an internal progression that makes it very
| satisfying to solve.
| onion2k wrote:
| If you fancy making an online crossword, I once made a nice
| traditional crossword layout using CSS Grid that makes a decent
| basis - https://codepen.io/onion2k/full/KRQeqm
| reificator wrote:
| So many of these start or end with an `x*`, `(x|y)`, `[xy]` or
| `[^xy]` that I only see two characters I can fill in before I
| need to start looking at multiple constraints for the same cell
| and either doing combinatorics or guess-and-check.
|
| This might be fine for hard mode, but as someone who considers
| themselves a regexpert it's not very approachable as a first
| puzzle IMO.
|
| A more gradual introduction to the format would be to give a few
| clues that give you confidence on specific characters, that then
| let you lock in some other characters in other hints, and so on.
|
| For instance, replacing `.*H.*V.*G.*` with `.{3}H.*V.*G.*` would
| go a long way because you could confidently place an `H`. And say
| that intersected with `(DI|NS|TH|OM)*` on the `H`, you could then
| place a `T` from the second clue because of what you learned from
| the first clue.
|
| It could just be that I'm missing something or not as good at
| regex as I thought, and please let me know if that's the case.
| Either way though, when I'm trying a new kind of puzzle I'd like
| to feel like I made _some_ sort of progress after trying for 5-10
| minutes, and here 2 chars does not feel like progress.
| afranchuk wrote:
| 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 wrote:
| Is the complexity basically NP-hard, equivalent to a SAT
| solver or even harder?
| dandanua wrote:
| Nonograms are np-complete, so this type of puzzles is also
| np-complete.
| ladberg wrote:
| Nope, it's basic regex so not NP-hard.
| teawrecks wrote:
| But it's a satisfiability problem. Seems NP-complete in
| the general case to me.
| ladberg wrote:
| Huh yeah that could be right... I'll have to think about
| it more.
| reificator wrote:
| 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.
| teawrecks wrote:
| 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)*.?
| vcxy wrote:
| 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
| reificator wrote:
| 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.
| ryangittins wrote:
| 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!
| [deleted]
| rav wrote:
| 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.
| anderskaseorg wrote:
| 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.
| ladberg wrote:
| Those are not equivalent, I think you're thinking of [XHH]
| instead of XHH.
| ryangittins wrote:
| Thanks, that's exactly how I read it.
| Guvante wrote:
| ("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".
| freeopinion wrote:
| Right away the red and green hints are wrong. Either that or this
| puzzle used RegEx rules that contradict those I am familiar with.
| Either way, they lost my attention.
| ladberg wrote:
| They seem to be accurate under all normal regex rules. Keep in
| mind that empty values are spaces and a full match is needed!
| freeopinion wrote:
| What does "full match" mean? Either it matches or it doesn't.
| ladberg wrote:
| 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.
| freeopinion wrote:
| 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.
| freeopinion wrote:
| .(C|HH)* should match against " " or against "A " or against
| "B" or against "ZZZZZZZ".
|
| But this puzzle doesn't recognize any of those as valid.
| ladberg wrote:
| That's not the case... .(C|HH)* matches with single
| character followed by any number of C's or HH's. So " " or
| "B" would work but in the puzzle the full line has to match
| so those aren't possible
| freeopinion wrote:
| Can you explain what you are seeing about "B" that does
| not match? Or about "_______"?
| ladberg wrote:
| I agreed that "B" does match. However, the puzzle needs
| to match the full line and not just a substring so
| "ZZZZZZ" or "B " don't.
| freeopinion wrote:
| You have not explained how those are not matching the
| full line. I assert that they are. Show me actual correct
| code that says otherwise.
| chaorace wrote:
| As you can see[1], the regex checker is based on the JS
| RegExp.match method. Each cell is always 1 character long
| (so, either a letter of some kind, or an empty space).
| The str parameter for the check function is assembled by
| concatenating these cells together[2], so the input
| string for an empty line will look something like this:
| "_______"
|
| Technically, the regex matches 7 times, once for each
| character, but getting multiple partial matches is _not_
| equivalent to getting just one perfect match, which is
| what the puzzle requires. Internally, the puzzle enforces
| this requirement by making each Regex rule require a full
| line match (see line 118: '^' + rule + '$').
|
| Personally speaking, I felt like that was the most
| intuitive way to interpret the mechanics of the game, so
| I'm willing to give the programmer a pass when they
| slightly modify the regex rule prior to evaluation.
|
| [1]:https://github.com/Jimbly/regex-
| crossword/blob/8b178f32eba37...
| [2]:https://i.imgur.com/PS0BmJ6.png
___________________________________________________________________
(page generated 2021-03-12 23:00 UTC)