Slashdot Mirror
Can You Do the Regular Expression Crossword?
mikejuk writes "Programmers often say that regular expressions are fun ... but now they can be a whole lot of fun in a completely new way. Want to try your hand at a regular expression crossword? The idea is simple enough — create a crossword style puzzle with regular expressions are the 'clues.' In case you don't know what a regular expression is — it is a way of specifying what characters are allowed using wild-card characters and more. For example a dot matches any single character, an * any number of characters and so on. The regular expression crossword is more a sort of Sudoku puzzle than crossword however because the clues determine the pattern that the entries in a row have to satisfy. It also has to use a hexagonal grid to provide three regular expressions to control each entry. This particular regular expression crossword(pdf) was part of this year's MIT Mystery Hunt. This annual event is crammed with a collection of very difficult problems and the regular expression crossword, created by Dan Gulotta from an idea by Palmer Mebane, was just a small part of the whole — and yes there is a solution."
Most so called regex commands are really more powerful and define CFCs that aren't regular.
I'll post the solution as regular expression
*
^there you have the solution, the infinite plays of Monkey-Shakespeare, and the answer to life and the universe, and everything.
Solving it without going insane, on the other hand, is an entirely different story.
http://xkcd.com/1171/
No.
This is something better left for a computer to do.
It's a great idea, but the puzzle given is too complicated.
If they really want to popularize this concept among programmers, many of whom have forgotten regular expressions even if they had once mastered them, they should really create much simpler puzzles in a mounting order of difficulty.
Hopefully, someone enthused by the idea will create and publish such puzzles.
There's probably already a CPAN module for solving it...
Solved it a few days ago. It was fun. It's not as hard as it looks.
and yes there is a solution
In fact, there is exactly one solution.
Where are the rules? Just the grid isn't much help; for example the clue N.*X.X.X.*E on a length 9 line might be NXxXxXE (length 7). A colleague has just looked at the solution and my hypothesis is that each regex fully describes the line (i.e. /^clue$/) but it would be nice to be sure ...
Quick wafting zephyrs vex bold Jim
I have a flight from Seattle to Boston that stops in NYC tonight. Looks like I'll have something to do! Hope I remember all the regex syntax...
I put the 't' in electrical engineering.
and then my brain explode..
Is it just me or is a mostly (all?) spaces solution possible?
Yvonne Lee, Community Manager at Dice.com writes,
Python coder | PyQt Applications | Writer
No need to print out the puzzle, somebody made an interactive version:
http://twoevils.net/cross-regex.html
The article asks if anyone has composed other programming puzzles, like a parenthesis puzzle.
Any LISP program should qualify for that one.
I believe the lead is misleading:
'an * any number of characters' - IMHO this is incorrect - * means 0 or more repetitions of the preceding token.
In the first: .* does not match an empty string .* does match an empty string
in the second:
In case you don't know what a regular expression is — it is a way of specifying what characters are allowed using wild-card characters and more.
I mean... really?
Have trouble parsing them? I get that. We all do.
Not know what they are? Who in this audience?
William of Ockham had no beard. The most likely explanation is that it was chewed off by squirrels every morning.
If you have a programming problem that requires regular expressions, you now have two problems.
Either that or I need to brush up on my regular expressions.
For example ... an * [matches] any number of characters and so on.
No. That's shell expansion, not regular expression. To match any number of characters, you would use ".*".
... to find the solution. Two hours that I should have spent preparing for a presentation I'm supposed to give to my boss's boss tomorrow... :-(
In many places, there is /.*/
But shouldn't that be /.+/ ? Or am I to assume that it's accepting spaces? Most likely not.
Set up an amb for each square. Then use "require" with each regular expression defined across the grid.
Problem solved - generically - for all time!
It's not the most efficient solution in the world, but it'll probably still solve it faster than you?
It took me about an hour to solve it. I printed it out and additionally to filling in letters I marked the cells where I am not 100% sure that I had the correct letter. I had to do some rollbacks of a few marked cells. I'd say it is as hard as a medium sudoku.
I think the question is, can you not do it? Answer for me: No.
My strategy: I wrote a program which read in a grid of letters (it actually just ignored spaces, so I laid them out in a hex shape), did the collating to produce the strings for each direction, then did, for each clue, four matches: ^re$, ^re, re$, and re. It then displayed the best match it had found. I'd post what this looks like, but the Slashdot comment system won't let me. (Apparently, "too many junk characters", and also no way to make spaces work.)
And it produced one of these dumps for each of the three sets of clues.
Then I ran that in another window in a loop, once a second, and started solving. Was super fun. Got it done early enough to sleep some, too. A++. Fun. Would solve more.
My blog: http://www.seebs.net/log/ --- My iPhone/iPad app: http://www.seebs.net/seebsfrac/
Most of the regex are qulified with a star *, which mean 0 or more times. So since the regex allows 0 matches I can put in whatever I like. Maybe they meant + ? I'm not going to look at the solution. I will just concentrate on the few chars that are not suffixed by a * .
It took me less than 10 minutes to complete that crossword. It's actually easy, because the clues always give enough information to immediately place a letter somewhere with minor thinking; no tracking back is ever needed (unlike in some Sudoku grids where it's often easier to "try" a number, then cancel if an inconsistency appears).
Actually most of the clues can be easily translated to natural language and make the puzzle understandable to the average people: [^M]*M[^M]* means "there is one and only one M in this line", (RX|[^R])* means "every R in this line must be followed by an X", etc.
God, root, what is difference ?
Can google googles solve it like suduku's?
And here I was thinking the crossword clues would be as normal, but the answers in the grid would themselves be regular expressions.
What do you mean they cut the power? How can they cut the power, man? They're animals!
Took about an hour to solve, but I'm already insane.
http://hjohn.home.xs4all.nl/RegEx-Solution.jpg
...that "regular expressions are fun"?! Because I think we just discovered a Venn diagram with 100% overlap between those programmers and "people we should be launching into the Sun in rockets ASAP"!
I'm joking of course... or am I? No, of course I am... but really... am I?
Hmm.
There are 2 clues in this puzzle that say .* (dot star). So each space in the line can be any character. Really? That's pretty weak and a cop out.
This was part of the mystery hunt, so that would imply the solution means something (i.e. gives a clue for some subsequent puzzle). While I had fun solving it, the resulting jumble of letters doesn't appear to have much significance... Anyone out there have more context to give for the solution?
Lacking a printer, I threw together an interactive version: http://jimbly.github.com/regex-crossword/ Enjoy!