Regex Crossword | Hacker News Reader

Regex Crossword

regexcrossword.com

409 pointsgrzm59 comments

I thought this was kinda neat so I taught a computer how to do it: https://github.com/lvh/regex-crossword/blob/master/src/lvh/r...

Right now, it works using a logic programming engine (core.logic, essentially miniKanren), generating a bunch of strings that match the regex, and then applying them as constraints.

If I were to improve it, I'd parse the regex, walk the parse tree, and assign constraints that way. (There's already a regex parser in there: that's how the string generation works.) That was my first thought, but that's more complex than what I want to tackle before work :)

Right now there's a bug where if e.g. a regex AB|CD will get applied character-wise, so it might erroneously try AC or BD. The way to fix that is to make sure the answers actually match the regex all the way at the end.

Using a constraint engine has the cool feature that it can show you multiple answers if they exist. (That's not true for my current implementation, because the string generation is randomized, so there's no guarantee it will visit each possible string.)

Someone else has pointed out that there are a lot of clues in the titles, e.g. that the answers are palindromes. That would be easy to add:

    (map (fn [vars] (l/== vars (reverse vars))) (concat rows cols))

(Read: "for each row and col, create a constraint that the row/col must be equal to itself reversed".)

A while back I wrote a little Rust library that does exactly what you say: parses a regex to use as a text generator. It was a lot of fun, and really gives you an appreciation for just how much bigger than ASCII matching the regex world can be! Writing a constraint-based solver that uses the generator library sounds like an amusing project as well!

Link: https://github.com/CryptArchy/regex_generate

Ah, this brings me back. I remember coming across these a few years ago and spending a ton of time solving them. I wound up taking a crack at writing a regex crossword solver. Suprisingly a solver that used basic constraint satisifcation[0] was enough to solve every problem I threw at it.

The core idea was for each cell, keep track of a list of possible letters that can go there. Initially you start with the full alphabet, and as the solver repeatedly narrows down the list for each cell as it gets closer and closer to completion. To hone in on the solution, the solver would iterate through each regex and see what characters could go in that row or column to match the regex.

For example if you have the regex "(a|b)" against an cell, you can constrain the list of possible values to the cell to just the letters "a" and "b". For a slightly more complex example, if you are matching a regex "(abc|def)", and you know the middle character has to be an "a" or a "b", you know the string in that row or column is "abc". By repeatedly checking each regex, the solver gets closer and closer to the solution until it eventually solves it.

Of course there's a chance the solver will get stuck. As a last resort, you can always resort to backtracking. I wound up finding implementing backtracking wasn't necessary since the approach I mentioned above was enough to solve every puzzle I threw at the solver.

[0] https://en.wikipedia.org/wiki/Constraint_satisfaction_proble...

Not very surprising when you consider that it's a constraint satisfaction problem

I don't know if Lisp is to blame, but we had exactly the same thought, and I gave it a shot: https://github.com/lvh/regex-crossword

I did the somewhat bruteforcy generate-strings-and-learn-from-that way, instead of working off the parse tree. The latter is clearly more efficient, but also not something I can implement in <1h before work -- and it has the logic engine in the center, meaning it's not a dead end if I want to pick it up again :-)

> In order to remember which puzzles you have solved, we need to identify you in some way.

No, that's a lie. No need for identification in order to save progress, you can use: cookie, browser storage, etc.. for that.

Please be honest about why you are using social media for login. Because when I login with Facebook for example, you can see a large portion of my Facebook profile and depending on the plan you have way more than that.

Or they just Show a Progress-hash or something that i can store for myself if i wish to. To require a Login is annoying nowadays.

Anyway the Idea is good and it is really fun to solve.

I like when this kind of sites allow you to copy-paste your sessions (as in a cookie clicker game), but (serious question) what they say is true if you want synchronized saves from multiple browsers/devices?

For saving your settings, Duck Duck Go gives you a random unique "passphrase" that is both identity and authentication, and also uses cookies so you don't have to input it every visit. It seems to work well.

Using cookies is brittle because they can get purged. They also don't sync. You could display some base64 encoded data to copy and paste between sessions but that would be quite unpleasant.

One way would be to auto-generate accounts and display some random identifier to keep. Or maybe just offer e-mail to which they would send you a login link... There are other options but login with OAuth is not the worst.

So use the browser's local storage feature and realize it's just a little toy and not so important that it needs bulletproof data retention.

> Please be honest about why you are using social media for login.

Without speaking for Regex Crossword (I'm in no way affiliated with them):

I suspect the reason may at least in part be security. Passwords are dangerous to keep around, hard to handle, computationally expensive if done right, and if an attacker gets at the database, people get angry. A social network provider (especially the options here, Facebook, Google, Twitter, GitHub and Windows Live) is much more likely to get security (against third party attackers) a lot more right.

That's just foolish - you don't need passwords of any kind. In fact you don't need accounts. You can just store cookies, accessible from this browser only, which tells you what have you solved.

That doesn't solve login in from a different device. And if you cleanup cookies for whatever reason, you lost the progress. So no, cookies don't solve the same problem as a user account (with login from a "trusted" provider) solves for saving the state of progress by a user on this game.

That's a game, an exercise for several nights

Maybe allow both options for people who want to keep their saves across multiple devices and one for users that use the same browser. It is a pretty trivial thing to do.

They already do.

The website already uses cookies to store what you have solved. The cookie has 1 year expiry. Account creation is optional.

Which disappears cross device or cross browser, making users flood your inbox with support emails asking where their progress went.

Not everyone has nefarious plans. Some people want to simplify the process for both parties. You have valid points, but there's no need to be so aggressive.

I'm not so certain, supporting saving data to a URL hash is pretty trivial to do, much easier than going with SSO integration - so I'm surprised the site doesn't support both at least.

URL hashing is annoying. It ends up transferring to someone else if you copy+share the link, and it disappears if you leave the site and come back later.

Better to just save to a cookie.

It already saves your answers in local storage, when you open the page in a new tab your progress is gone but your solutions are still there. You just have to click "Validate" for each of them. So the authors know it's a lie.

This is a great, fun way to learn! Two points for improvement, in case the creators are reading:

1) It's not clear which flavour/implementation is needed. I was using https://regex101.com/ to check until the puzzle where /+ is used, which that site claims is invalid in JS and PHP but OK in Python.

2) It would be great if filling a cell automatically moved you to an adjacent cell, as in most (regular) crossword apps.

mentioned in about page [1] that Javascript regex flavor is used

[1] https://regexcrossword.com/about

Ah, I missed that. That really compounds the question though: I see that they explicitly recommend regex101, which claims that the clue is invalid JS regex

probably they intended the user to choose JS on regex101

not sure about the question you hit a snag, can you post the details here? you might get your doubt cleared

One of the clues on Beginner puzzle 4 is /+

Pasting that into regex101, with flavour Ecmascript, yields "Pattern Error" (rightly, since forward slashes enclose patterns, and thus need to be escaped).

oh ok, got it

and yeah, agree with you, this should either be escaped or some explanation added regarding delimiters

I like it as a puzzle, but am concerned that it promotes "cleverness" in writing regexes.

Don't do that people. Just. Don't.

Keep regexes simple and stupid! Remember other people will have to read them someday.

I also like this larger hexagonal one: https://rampion.github.io/RegHex/

I've made an open-source clone of this as an android app. It needs some onboarding and maybe a guide.

Perhaps I have some time in 2-3 weeks to develop it further, does anybody have advice on what to include?

https://play.google.com/store/apps/details?id=de.chagemann.r...

Will you put it on f-droid? I avoid the play store.

I will have a look at f-droid! Not sure if it's easy to integrate. Right now I can publish the app to the play store via a gradle task.

Good one. Reminds me of the Regex Golf: https://alf.nu/RegexGolf

Previous discussion: https://news.ycombinator.com/item?id=6941231

I remember this one the first time round!

Previous discussion: https://news.ycombinator.com/item?id=8674039

There was an earlier one too: https://news.ycombinator.com/item?id=6056011

This is great but I think it would be more interesting the other way round: write regex to capture complex input. Maybe add some steps constraints to up the difficulty.

Maybe it's just me but I find it immensely more difficult to solve the ones where the regex is rotated 90 degrees. Something about trying to write a thing left-to-right and mentally match it with a thing reading top-to-bottom is exercising a (clearly untouched) part of my mental pathways. I'd love for the top row to not be rotated it'd be much more fun.

The site does provide tooltips on the clues. But the text rendering is difficult to read, yes; smaller characters seem to nearly vanish.

On my browser at least there's a pair of arrows to rotate the grid so different equations will be "upright".

Lots of Hitchhiker's Guide to the Galaxy references:

https://en.wikipedia.org/wiki/The_Hitchhiker%27s_Guide_to_th...

Now I've got 2 problems!

:iseewhatyoudidthere:

I'm doing the tutorial and having never really understood regex, i just fill in 'A' everytime, and i pass all the tests. Not learning anything though.

Not sure how you're managing that, A is the answer to the first tutorial, but doesn't work for the second one.

If you click Validate it'll shake and turn red, though you can skip ahead all you want, you want it to turn green and add a checkmark next to the title.

I wasn't entirely truthfull. Still, 4, 6, 7, 8 are all 'A' solutions. I went back over them and googled some words, now I do understand those.

I guess all I showed was that if you don't want to learn, you're not gonna learn.

Agreed. I blazed through the tutorial without thinking much, and then when I started Beginner #1 I had to go back and look up most of it again.

Yeah, some of the puzzles in Beginner seem to imply they need more than one character entered, but you can only enter a single character. `EP|IP|EF` matches those pairs literally, so I'm not sure what it wants me to enter if it only accepts one character.

I'm no regex beginner but this overall presentation is pretty confusing.

That example you gave is from the first Beginner puzzle, correct? There are two spaces to fill in. So one of those three sequences is the answer to that column (or row if you've rotated the puzzle). There's not an error.

If you find the interface confusing, start with the tutorial levels which begin with a single character solution and progress to larger solutions. Each cell is clearly meant to be one character in a string, with the row/column being the entire string.

as mentioned in about page [1], this site covers Javascript regex flavor

surprised that this resource wasn't mentioned in a recent thread [2] about regex

[1] https://regexcrossword.com/about

[2] https://news.ycombinator.com/item?id=20614847

I love Regexcrossword. For anybody just learning regex, to to regexcrosswords as soon as you’ve completed your first tutorial!

After that, keep regex101.com handy for testing and checking your regexes.

This is both new to me and exactly up the street of someone I know, so really glad to have come across it!

should make the input 1st focus and jump to the next in fewer seconds (or after double enter)

I used it to learn regexp a long time ago and then for fun, because, regex are fun!

Please add " (2014)" to the end of the title.

Nice!

When done, go to http://alf.nu/RegexGolf to sharpen up your skill!

Aaaaaaaaand there goes my morning

Reply on news.ycombinator.com