Can You Do the Regular Expression Crossword? 115
Posted
by
samzenpus
from the game-time dept.
from the game-time dept.
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."
Solution (Score:1, Interesting)
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.
Re:Solution (Score:5, Informative)
I think you mean .*
Re: (Score:1)
Re:Solution (Score:5, Informative)
The article summary was wrong about * and so are you. At least the language in the summary leaves much to be desired, although they are correct about it being a numerator, they leave off the part that it matches the previous character or subexpression. * = the previous character or subexpression zero or more times. As Stradenko pointed out to get ANY character you need . (period). To get any character zero or more times you need .* (period asterix). To get the solution to anything with more than one line you need [\s\S]*.
So you're pretty far off the mark as far as 42 [wikipedia.org] goes.
Re: (Score:2)
To get any character zero or more times you need .* (period asterix). To get the solution to anything with more than one line you need [\s\S]*.
That depends on the RE dialect; some treat newline as an ordinary whitespace character by default.
Just solving it is easy. (Score:2, Funny)
Solving it without going insane, on the other hand, is an entirely different story.
Re: (Score:2)
Tell me about it
Why the hey did they have to put 2/3 of the clues upside down? That was cruel.
(And yes, I realize it was an attempt at uniformity, to have every line take the form of clue-answer. Still, it is impossible to retain that form without having most of the clues upside down no matter how you turn the page. If it's merely to slow down students in the competition, I call unnecessary roughness. Judging students ability to read math upside down is worthless compared to the value of a good puzzle.)
Re: (Score:2)
It being up side down was less of an issue than the fact I kept losing my place on the page, because the problem does not have an at-a-glance orientation. I solved that by drawing a couple (four, actually) of arrows.
Shachar
Solution (Score:2)
Took about an hour to solve, but I'm already insane.
http://hjohn.home.xs4all.nl/RegEx-Solution.jpg [xs4all.nl]
Re: (Score:2)
Sorry, your solution is wrong.
"HCXRCMIIIHXLS" doesn't fit the regexp.
Try http://twoevils.net/cross-regex.html [twoevils.net]
Re: (Score:2)
You're right. The center row should be "HRXRCMIIIHXLS".
I also preferred doing it on the print out, much easier for this kind of puzzle.
Re: (Score:2)
I hate you.
I taught my son regexes so he could help me, and he is walking around mumbling 'I hate .* '
Obligatory xkcd (Score:2, Funny)
Re: (Score:1)
And here I thought it was going to be: http://xkcd.com/356/ [xkcd.com]
Re: (Score:1)
I got nerd sniped. Luckily I wasn't in the road. Only took about 2 hours.
Re: (Score:2, Funny)
http://xkcd.com/1171/ [xkcd.com]
Better Obligatory xkcd
http://xkcd.com/208/ [xkcd.com]
Re:Obligatory xkcd (Score:5, Insightful)
Randall should draw a comic about obligatory xkcd references.
Re: (Score:1)
That would just result in obligatory obligatory xkcd reference references being posted whenever an obligatory xkcd reference is posted.
Re: (Score:2)
http://xkcd.com/356/ [xkcd.com]
I haven't gotten anything useful done all morning!
Re: (Score:2)
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.
Re: (Score:2)
Re: (Score:1)
29766
Re: (Score:2)
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
Great idea, but... (Score:4, Insightful)
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.
Re: (Score:1, Insightful)
I don't know a single programmer who has forgotten regular expressions. Who are the "many" you speak of?
Besides, rather than the puzzle being too complicated, maybe your brain is too simple?
Re: (Score:2, Funny)
s/forgotten/never learned/g
Re: (Score:2)
You're right. My brain must be too simple.
Nothing gets by you.
Re: (Score:2)
Are your still in your 20s or something? You'll forget anything you don't use in a while. When I did web scraping I got quite good at regex. Now, I have to look some things up, especially when dealing with look aheads and look behinds and other slightly more esoteric features. I am working through the puzzle, though.
Re: (Score:2)
Sorry, didn't mean to imply that the regexs in this puzzle used lookaheads or behinds. There's nothing even remotely esoteric about the ones in the puzzle.
Re: (Score:2)
Ruby, for example.
Re: (Score:2)
Re: (Score:1)
(n.b. you have to put back-slashes before parenthese to make them meta-characters in emacs)
Re:Great idea, but... (Score:5, Funny)
The only thing difficult about the puzzle is the format in which it is presented. How many people have printers? Of those, how many have working printers? And, of those, how many also have paper?
Re:Great idea, but... (Score:5, Funny)
How many people have printers? Of those, how many have working printers? And, of those, how many also have paper?
I have all of those........but no ink.
Re: (Score:3)
You could always squirt out some more ink, I mean, you are an octopus, right?
... and if you aren't, just use black paper...
Re: (Score:2)
Re: (Score:3)
It takes about an hour to solve. It isn't terribly complicated.
Re: (Score:2)
It's a great idea, but the puzzle given is too complicated
The puzzle was obviously designed by a program - so the solution should also come from a software.
Re: (Score:2)
Yes. This.
I use regex (pcre) on a daily basis. This? This hurt my head. Holy shit that puzzle is hard. (Granted, I hate crossword puzzles... maybe I'm not old enough yet.)
Re: (Score:2, Insightful)
Really? I'm about as far from a Regex Guru as you can get and frequently advocate against using them for anything but the simplest task and I was able to solve it in about 45 minutes or so. When you first sit down with it, it looks near impossible, but there are a handful of hexes that can be deduced immediately and after getting a few more it's not that much harder than a sudoku.
I though the puzzle was challenging, but not overwhelmingly so in any way and would love to see more of them.
Re: (Score:2)
I think you haven't actually given it a try. The clues are written as regexes, which require to know the syntax, but it's actually a pretty easy logic puzzle.
Re: (Score:1)
simple? (Score:5, Funny)
There's probably already a CPAN module for solving it...
Apologies to Betteridge (Score:4, Interesting)
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.
Re:Apologies to Betteridge (Score:4, Funny)
Re: (Score:2)
The "?" means match zero or one times, not any single character. In this context, it means the 1 is optional.
Rules? (Score:1)
Re: (Score:2)
I haven't seen any part of this puzzle other than the grid itself, but if you interpret every clue as a match for the full line like you said, there is exactly one solution.
Re: (Score:1)
If they wanted to fully describe a line, they'd wrap each expression in start-of-line (^) and end-of-line ($) metacharacters.
What gets me though, are clues like "(O|RHH|MM)*" . That's basically saying: there's an O or an RHH or an MM ... and _zero_ or more combinations of these. Functionally equivalent to a ".*". Essentially a useless clue. The crossword is littered with these types.
Re: (Score:2, Insightful)
The rules are anchored to the ends. Printing a ^ and $ on each clue is redundant and silly, when a moderately intelligent person could easily figure that part out for themselves.
Re: (Score:2)
Not useless. It has to match the whole line. If the regular expression matches zero characters, then the rest of the line is left as the next token in the string. You're thinking of it as a parser... think of it as the results of a parser -- the parser ran, and it returned the complete line of characters as a token when given this regular expression. Does that help you understand why this works?
Re: (Score:2)
That makes more sense. You're right, I was trying to match the regular expression to the line, instead of the line as a result of the regular expression. Still, it would have been nice to remove the ambiguity and wrap each clue with ^ and $. No matter how redundant or silly it seems to Anonymous Cowards.
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
^ has multiple meanings in regexes.
Re:Rules? (Score:5, Informative)
Everywhere ^ is used in the puzzle it means that it matches anything not in the group. For example [^abc] would match any character except a, b and c
Re: (Score:2)
Re: (Score:1)
Mystery hunt tradition is that many puzzles have no rules, you have to figure out what to do as well as solve the puzzle...
I have a flight from Seattle to Boston (Score:2)
Re: (Score:2)
I am pretty sure that it is implicitly "all letters".
Re: (Score:2)
Breaking news. (Score:5, Funny)
Yvonne Lee, Community Manager at Dice.com writes,
Interactive (Score:5, Informative)
No need to print out the puzzle, somebody made an interactive version:
http://twoevils.net/cross-regex.html [twoevils.net]
Re: (Score:1)
Re: (Score:2)
nhpeha sdiomomthfoxn xaxphmmommmmrhhm cxnmmcrxemcmccccm mmmmmh rxrcmiiihxlsoreoreoreorev cxcchhmxccrrrrhhhrru ncxdxexlerrddmmmmgcchhcc
Upcased and without spaces is the solution.
Parenthesis puzzle (Score:2)
The article asks if anyone has composed other programming puzzles, like a parenthesis puzzle.
Any LISP program should qualify for that one.
Re: (Score:2)
I must have missed the day that 0 stopped being part of the set of "any number"
Re: (Score:2)
Sorry, I just figured out you're talking about the missing '.' which is of course a mistake in the description
glad that's cleared up (Score:1)
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?
The problem with expression (Score:1, Funny)
That's not right (Score:3)
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 ".*".
Shouldn't that be... (Score:1)
Re: (Score:2)
No, they mean ".*". A .* is zero or more characters. In some cases, yes, that means zero.
amb in Lisp (Score:2)
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?
Re: (Score:2)
I've not dealt with Lisp, so I only think I know what you're saying. I made a Sudoku solver once. It worked immediately. All the time. Every puzzle. There are still people out there who derive enjoyment out of solving Sudoku puzzles.
This puzzle idea is far more interesting than Sudoku. The fact that a computer solver can be written without great effort doesn't really diminish it.
solved (Score:1)
What do you mean "Can you do..."? (Score:2)
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 spac
star * (Score:2)
Re: (Score:3)
If you put a space anywhere in the puzzle, at least one of the clues will fail. The only solution that works is made entirely of the capital letters found in the clues. Don't believe me? Try to find a complete solution with a space in it.
And yes, they really do mean .* There are several of those that match empty strings, so you need to be on your guard. There is a single + in the puzzle, right where it needs to be.
It's actually easy (really) (Score:3)
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.
Re: (Score:2)
If you're being honest, 10 minutes is impressive.
It took me 2h10m, and I still need to finish (i.e. begin) a paper due tomorrow.
Re: (Score:2)
It took me 2 hours. Nothing about it was very hard but most cells can only be filled in after quite a few other cells in the row are already filled in. This makes the number of logically deducable cells avialable at any given time somewhat low.
goggles google? (Score:1)
Inversion (Score:2)
And here I was thinking the crossword clues would be as normal, but the answers in the grid would themselves be regular expressions.
Interactive version (Score:1)