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."
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/
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.
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.
If you have a programming problem that requires regular expressions, you now have two problems.
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 ".*".
My first thought when seeing the crossword was that to make sure there aren't two or more answers, you place the clue between egrep and /usr/share/dict/words . . . and that effectively cured me of any desire of actually doing the crossword.
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/
I am pretty sure that it is implicitly "all letters".
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!
Except this isn't actually a crossword puzzle. It doesn't make any words, only odd series of letters. As the summary said, it's more like Sudoku, with a crossword bent.
I won't join Slashcott. OTOH, If Beta goes live, I just won't be back until it's fixed. Sorry Dice.
Nope. In fact, there can be no spaces. (It's not a rule, there just aren't any, deductively. Consider it a free hint.)
I won't join Slashcott. OTOH, If Beta goes live, I just won't be back until it's fixed. Sorry Dice.
Took about an hour to solve, but I'm already insane.
http://hjohn.home.xs4all.nl/RegEx-Solution.jpg
29766
-- sudon't
Air-ride Equipped
I'm assuming since most of the clues begin and end with .* that they're all intended to be anchored to the start and end of the word. So that particular clue matches an 8 character string consisting only of (zero or more) Rs followed by (zero or more) Ds followed by (zero or more) Ms. I don't think you'll find anything in the word list completely matching that
I must have missed the day that 0 stopped being part of the set of "any number"
Sorry, I just figured out you're talking about the missing '.' which is of course a mistake in the description
Lacking a printer, I threw together an interactive version: http://jimbly.github.com/regex-crossword/ Enjoy!