Regex Crossword | Hacker News Reader

Regex Crossword

regexcrossword.com

330 pointsanewhnaccount108 comments

How about you save my progress in a cookie?

You might find this hard to believe, but I don't have a Facebook account.

I do have a Facebook account, but I'm not interested in using it here just to save. So, another vote for a cookie.

Also do not have a facebook account and was bummed to see my progress gone.

Off topic, but god I just wish Facebook would disappear. It's ironic that such a popular company with such a huge valuation would produce an immediate and significant benefit to me if it just disappeared overnight.

It begs the question, do you mean Facebook the social network, or Facebook the company? Because there are surely many benefits coming from the company that don't necessarily depend on the social network.

It's hard to imagine one existing without the other

I think one existing without the other could certainly be the case in the nearish future. Not everything they're doing is tied into the Facebook site.

Why not create one but never post onto it? That's what I did. I don't see any detrimental effects if I create an account but never use it to its full capabilities.

Yeah same here. Clicked to a puzzle curious to play with it, saw the notice saying I need to log in to facebook, closed the tab.

Or, if you want to motivate this particular developer:

"How about you store my progress in a regex! (Which can be put into a browser cookie as an afterthought.)"

This is fantastic work. Many thanks. One request though: please add one or more alternate logins than Facebook.

Yeah, this. Especially for something like regexes where a large amount of your users will be more technical, and facebook is becoming less and less popular among technical people.

Personally, I don't have a facebook account and I will not create one just so I can log in on your website. The disability to save my progress also made me give up on trying to progress since it'd just be lost anyway.

My main problem with this is telling the difference between O and 0, the clue O's look more like 0 so I have to copy paste them. (Although I don't think I've had any numbers required for solutions yet).

Yeh just swapped 0 for O in a puzzle to win.

Perhaps the hint font should be different from the answer font. Or at least better zero's.

The zeroes have a slash through them on my browser - does yours not have that?

Mine too. Although when you've got [0-3] and [^2O13] in the other, it's not too difficult to figure out that contradiction fairly quickly.

You can copy/paste the Os and 0s if you're not sure.

Came across same thing. I did: Cmd + F; "O".

These crosswords are NP-hard! D: Here's a short encoding of 3SAT:

Alphabet: [01]

Number of variables: N

Columns: one for each clause, i.e.:

    r/.0...|..1..|....1/
    
    (-x2 V x3 V x5)

They're disjunctions of three regexps of length N. Each alternative fixes one positional variable to either 0 or 1, and ignores the rest.

Rows: one for each variable, forcing it to be single-valued across the clauses:

    r/0+|1+/

Well, that sure cured me of the intuition that these square grid regexp crossword puzzles were inherently easier than the original hexagonal grid version!

Nice work overall. That was fun.

Just a heads-up though: There are some typos and grammar mistakes in your explanations, so if you plan to share professionally, you might want to have someone proofread it. Also, your Facebook OAuth window that pops up upon page load is being caught by Chrome's built-in popup blocker. Either way though, I'm always disappointed when Facebook OAuth is the only login method. I get that it's easy to implement, but I can't imagine this is a very security-sensitive app in terms of user-accounts. I would like to save my progress, but it's not worth the risk or analysis required to hook up my Facebook.

The ability to rotate was really sweet. Fun challenge, some syntax I wasn't sure about (back referencing) but now probably will remember.

Nice, but the answers being phrases ruins it for me, because you start seeing the answers without needed to check the regular expressions.

Really nicely designed though. Clean UI. Wouldn't mind if it was enlarged to use more of the screen real estate (tiny fonts are hard to read). I had fun with this.

I thought about this too- the phrases- but, isn't that how normal crossword puzzles are? You can gather clues from the context of surrounding words when doing one of those puzzles.

Not really, because rather than using an entire coherent phrase that goes from the top to the bottom of the puzzle, crossword puzzles use discrete and often unrelated words throughout.

It's most like a theme clue -- in an American-style crossword you often have 1 to 4 extra-long answers, almost always horizontal, that are related to a theme (they might be puns, or proverbial sayings, or together spell out a longer quote). It's sometimes possible to solve a theme clue in a crossword when you have only a few letters, if you understand the theme well enough.

In this case, the "suddenly solving the whole thing given only 40% or 50% of the letters" effect can be kind of cool, or annoying if you were enjoying the logic puzzle aspect. In the original MIT Mystery Hunt hexagonal regular expression crossword, most of the grid did not spell anything recognizable, so it was clearly a logic puzzle through-and-through. I guess whether people appreciate that depends on whether they were expecting a pure logic puzzle or a combined logic+word puzzle.

+1. This is especially true for "Experienced #5" which required me to figure out about 4 letters out of 16 using the regex, the rest being obvious from the clue and the other 4 letters.

All the hitchhikers ones are pretty obvious though.

It would be nice to be switched to the next level automatically.

I was also expecting it to advance me automatically to the next level.

A bit of customisation of the default bootstrap look would have been nice too.

In case there is someone out there who never saw MIT's entry into the RegEx competition: http://rampion.github.io/RegHex/

This is the web incarnation of that hexagon puzzle.

The MIT puzzle (from the 2013 Mystery Hunt) was called "A Regular Crossword" and its credit says "Dan Gulotta, based on an idea by Palmer Mebane".

(Just so it's not credited to MIT in general; each year's Mystery Hunt is written by a specific puzzle team, and indeed each puzzle is written by specific puzzlers!)

This new site is super-awesome and challenging, but a great thing about the hexagonal grid in "A Regular Crossword" was that each hexagon was constrained by three intersecting regular expressions rather than two. That meant that the constraints could be trickier or vaguer in some ways, and comparatively more dependent on the sequence of elements within a regular expression rather than on the process of elimination between two intersecting sets.

Elsewhere in this thread, a commenter points out that the square grid regular expression puzzle can encode 3SAT instances, so I was wrong to call these easier than the hexagonal version.

I liked this puzzle too and I also made a web based version: http://stardrifter.org/regexp/ . Yours looks nicer but I do miss one feature from my version which is the ability to click a clue to rotate it into view.

Thanks, that was fun and not as tricky as the blank grid initially made it appear! And the implementation was nice (although a little twitchy if you rotate twice quickly).

I really dislike that patterns using * wildcard required using the letters beforehand. The game requires A* to match a row with zero or more A's, but this is absolutely incorrect, as A* will gladly match ANY string, like QQQQ.

That isn't how the Kleene star works.

A* is "the set of all strings over the alphabet {A}, including the empty string ε."

"QQQQ" is not a string over the alphabet {A} because it contains the symbol 'Q', which is not in {A}.

I have no idea what you're talking about. My point is more pragmatic the regex /A/ will match the string "QQQQ" and this tool doesn't take that into account. E.g., I type this into my javascript console:
/A*/.test('QQQQ'); > true
Showing that yes, /A/ does match 'QQQQ'

Actually this is wrong, when you use A* in vim for example you're not looking exactly for A* but for substring containing an A* since this also matches "" programs like vim will match anything.

Just because these tools use regex this way doesn't mean that's how regex really works.

No, it doesn't. It matches the empty string at the beginning of 'QQQQ', not the Qs themselves:

    /A*/.exec('QQQQ')
    [""]

When computer scientists discuss what a regular express does and does not "match", they are saying that strings which are "matched" by a regex are those strings which are members of the regular language defined by the regex. QQQQ is not a string in the language defined by /A* /, so /A* / does not match QQQQ.

If we look at things your way, we would have to say that the regex /A/ matches "AQQQQ". It does not. It matches "A".

That's not an issue with A*. Every regex here has an implied anchor to the start and end of the string.

Fair enough, but implied anchors are not part of the regex standard

* is not a wildcard, it indicates that the preceding token occurs zero or more times.

Yes, that's exactly my point. By occuring zero times, it means the preceeding token is irrelevant, and will match any arbitrary string.

So you are saying that // will match any arbitrary string?

As I saw, the regexps are all implicitly anchored. When you read `A`, you need to be thinking `\AA\Z`.

Fun! When I saw the title, I was expecting the opposite: a normal cross word with the usual "42 Across (4): It gets things done" style hints, but the answers were valid regex's. Someone make that too!

Regular crossword entries (that only have letters in them) are already valid regexen.

Pretty cool but I don't feel like I am actually learning regex. I think the explanations/definitions need to be more clear and probably the answers less easy to guess.

That was fun (in a really nerdy way)! I'm currently trying to educate one of my team member about regular expressions, this could be a fun way to get him practicing.

What's wrong on beginner / 01? :D http://imgur.com/eJBJYSx

It's not mentioned explicitly, but the given patterns should match the entire answer, not just part of it. In your screenshot, "O+" means "one or more letters `O`" , it does not mention any `E` s, so OE is not a valid answer.

When you're testing your answers, add explicit start/end anchors and implicit grouping to get better results:

    var r = /^(?:HE|LL|O+)$/;
    console.log("OE".match(r));
    console.log("OO".match(r));

So I had a bunch of important stuff to get done today, but now I know what I'll do instead. This is so much fun, well done!

I made it to http://regexcrossword.com/challenges/experienced/puzzles/4 before I opted to keep my sanity for the remainder of the day instead of continuing :) very well done. As noted, add non-FB login options!

Cool!

I had a lot of fun writing a solver in Haskell for a crossword like this a few months ago. Apologies for the self promotion but here's a link to the article I wrote about it http://almostobsolete.net/regex-crossword/part1.html

This is good homework/quiz stuff if you're teaching people regexes, just to spice things up a little bit.

I want to be able to return later, but it's a bit too much to register a Facebook account (which you presumably can't do with a throwaway address?).

I'd be happy to donate more than whatever Facebook pays you for every newly registered account if you would implement a simpler method.

How is this too much? FB reg is the simplest way possible online to create an account anywhere.

There are lots of people who simply don't want to give anything to FB. You don't have to be one of them but you at least have to recognize them.

Wish there were an offline open source version.

With the exception of DHH, do they believe in Open Source in Denmark? (jk)

http://regexcrossword.com/challenges/intermediate/puzzles/5

Anyone understand what (.)*DO\1 should match?

edit: Okay, I was writting 0 instead of O that's why it wasn't working.

Anything 0 or more times backreferenced onto the end of the string "DO", is my guess. So, for example:

  DO
  DONUT
  DOG

Wouldn't the characters have to come first, in order to be referenced in the first place? I.e. "DOG" would read "GDOG," no?

yes, parent is wrong.

. -> any character

(.) -> any character, grouped to reference it, since it's the first group it's referenced as \1

(.)* -> that, 0 or more times

(.)* DO -> any character 0 or more times, followed by DO

(.)* DO\1 -> any character 0 or more times, followed by DO, and the same character as in the beginning

By the way, the backreferences make the game non-regular.

What does it mean when a reg ex ends with a `\1` (backslash 1) as in this example third beginner puzzle? (.)+\1

http://regexcrossword.com/challenges/beginner/puzzles/3

It's a backreference to the first capture group, which is denoted by the first set of parenthesis, e.x.

    (.*)+\1

would match "ABAB", or "ABCABC", etc.

"\2" would match the second capture group, e.x.

    (.*)(.*)\2\1

would match "ABBA", or "AABBBBAA", etc.

so in your first example, "AB" was in the capture group and the \1 repeats it?

Correct. The following

    (.*)\1+

Would also match "ABABAB", for example.

Look at the Help button (top right); that explains all their syntax.

The help button doesn't really explain that point ( I don't think) at least not in a very clear way for someone inexperienced with regex

Speaking of that puzzle how come [COBRA]+ and (.)+\1 give back result 'O'? Why not C or B or A?

(.)+\1 means the last letter has to be equal to the first letter.

(AB|O|OR)+ dictates that the last letter of the first row has to be A or O

[^ABRC]+ makes it so that the lower right square can't be B therefore the upper right square can't be A

I got the solution but didn't understand it for the beginner "naughty" puzzle ... http://regexcrossword.com/challenges/beginner/puzzles/2

I learned regex this way about a year ago. First I went through the tutorials on http://regexone.com/, then started working the puzzles to burn it in. Really easy and useful once you understand it!

This highlights how crossword puzzles are a valuable way to stretch the mind laterally. This is a way to think about regexes that rarely comes up in practice: comparing one regex against another unrelated one.

Cool game, it really helped me brush up my regex skills.

I think I found an error in “The Lektor Device“: The “I“ in “WITH” could also be a “T” from the rules, but only the “I” is accepted.

The "I" can't be "T" because the regex on the bottom (.(\sSAI).*) forces it to be "I".

No in this case the regex on the bottom only applies the . to the square in question while the \sSAI in question applies to the second square. It seems that it could be a I or a T.

(\sSAI) is a group, not a character class. It matches the fixed string " SAI" and stores it in a group. If it were [\sSAI], you'd be correct.

This is fun! I feel like it is also good practice for logic programming too. Combine the regexes and put one or all possible solutions into each cell of the matrix :)

No facebook account here either. Would be nice to be able to sign up with email or log in with google.

I reluctantly logged in with Facebook and lost all my progress .

Closed as soon as I saw the Facebook login needed prompt.

Funny, instructive.

Good to practise regular expressions.

i don't know how to solve beginner 4? shouldn't you be able to put anything into it?

    * *
    / /

/ isn't a special character and * isn't special when inside a character class

Now here's a puzzle where the "post your solutions in ROT13 to avoid spoilers" conventional wisdom wouldn't help!

ROT47 solves this exact problem.

Wow, thanks for the reference! I had no idea.

Challenging and impressive.

That was pretty fun!

"Notice! In order to save your progress you have to login with Facebook."

Yeah, maybe... let me check: NOPE.

I really wish Facebook's Anonymous Login would make it out of beta so this wouldn't be an issue: https://developers.facebook.com/products/anonymous-login/

still facebook will know where you have been. "Anonymous" and "Facebook" do not really fit together ;)

They already do. They have Like buttons everywhere on the web.

But Facebook does have a good security track record. This random website does not. I don't trust them with any more information than needed. In this case, that is only a single anonymized token.

Don't you still need a facebook login for that?

A site knowing my facebook account is a small issue, facebook knowing a visited that site is the big one.

There is a good chance that Facebook already knows you visited a particular site because that site is already serving Facebook content (via a like button, for example).

This is exactly why I use a different browser for Facebook than any other web browsing. As far as they are concerned, the only site I ever visit is Facebook.

Same with Google properties. I only use Chrome to visit Google properties.

I'm sorry to be rude, but that strikes me as legitimately paranoid. Why do you care so much if Facebook knows that you visit sites other than Facebook?

I guess it depends on why someone uses Facebook. I (finally) got an account a while ago in order stay in contact with friends and former colleagues. My usecase of Facebook does not include me wanting Facebook to know everything I do.

Hence, Facebook lives in its own VirtualBox machine.

It's much easier to just block Facebook stuff with browser addons, and you can easily nuke every other tracker as well while you're at it.

As crazy as it sounds, I actually like the other trackers, because then I get more relevant ads. I'm also one of those crazy people that things adblock ruins the web (this opinion may be because I worked for a website that survived on ad revenue for a long time).

> that site is already serving Facebook content

  $ ping facebook.com
  connect: Invalid argument

Not so much, no.

Nope, I use browser addons to protect my privacy.

I like this enough that it prompted me to whittle my FB account down to nothing except a login provider for things like this.

Reply on news.ycombinator.com