Forgot your password?

Close
typodupeerror
Programming Games News

Can You Do the Regular Expression Crossword? 115

Posted by samzenpus
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."
This discussion has been archived. No new comments can be posted.

Can You Do the Regular Expression Crossword? More

Can You Do the Regular Expression Crossword?

Comments Filter:

  • Solution (Score:1, Interesting)

    by Anonymous Coward

    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)

      by Stradenko (160417) on Wednesday February 13, 2013 @09:46PM (#42891037) Homepage

      I think you mean .*

    • Re:Solution (Score:5, Informative)

      by Coolhand2120 (1001761) on Wednesday February 13, 2013 @10:09PM (#42891229)

      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)

        by dkf (304284)

        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)

    by Anonymous Coward

    Solving it without going insane, on the other hand, is an entirely different story.

    • Re: (Score:2)

      by gd2shoe (747932)

      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)

        by Sun (104778)

        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

    • Took about an hour to solve, but I'm already insane.

      http://hjohn.home.xs4all.nl/RegEx-Solution.jpg [xs4all.nl]

  • Great idea, but... (Score:4, Insightful)

    by stephanruby (542433) on Wednesday February 13, 2013 @09:54PM (#42891103)

    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)

      by Anonymous Coward

      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)

        by Anonymous Coward

        s/forgotten/never learned/g

      • You're right. My brain must be too simple.

        Nothing gets by you.

      • Re: (Score:2)

        by MightyYar (622222)

        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:Great idea, but... (Score:5, Funny)

      by Anonymous Coward on Wednesday February 13, 2013 @10:03PM (#42891181)

      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: (Score:3)

      by Goaway (82658)

      It takes about an hour to solve. It isn't terribly complicated.

    • 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)

      by CAIMLAS (41445)

      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)

      by Anonymous Coward

      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)

      by Sam H (3979)

      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)

      by UCFFool (832674)
      I was inspired, so I made an easier one. http://mariolurig.com/crossword/ [mariolurig.com]

  • simple? (Score:5, Funny)

    by bitingduck (810730) on Wednesday February 13, 2013 @09:54PM (#42891105) Homepage

    There's probably already a CPAN module for solving it...

  • Apologies to Betteridge (Score:4, Interesting)

    by MtHuurne (602934) on Wednesday February 13, 2013 @09:57PM (#42891121) Homepage

    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 ...

    • Re: (Score:2)

      by MtHuurne (602934)

      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)

      by deek (22697)

      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)

        by Anonymous Coward

        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.

      • 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)

          by deek (22697)

          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.

    • Seeing as some have .* at the start and end, it strongly implies that it must match the entire line.

    • Re: (Score:1)

      by Anonymous Coward

      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 that stops in NYC tonight. Looks like I'll have something to do! Hope I remember all the regex syntax...

  • Breaking news. (Score:5, Funny)

    by mutube (981006) on Wednesday February 13, 2013 @10:16PM (#42891297) Homepage

    Yvonne Lee, Community Manager at Dice.com writes,

    ^\\([^ ()]+\\)\\(([0-9]+\\),\\([0-9]+\\))"

  • Interactive (Score:5, Informative)

    by Ozan (176854) on Wednesday February 13, 2013 @10:29PM (#42891447) Homepage

    No need to print out the puzzle, somebody made an interactive version:
    http://twoevils.net/cross-regex.html [twoevils.net]

    • Re: (Score:1)

      by Garridan (597129)
      Gee, thanks. I made a hex grid in gedit and solved it in that referencing the pdf for the clues. And NOW you post the widget. On the puzzle: that was a blast! I want more! My only disappointment with the puzzle is that a certain amount of meta-puzzling (this part of that clue provides no info unless...) proved to be useful -- I never used that knowledge 'just in case', but it was never wrong. I prefer puzzles with misleading meta-hints to trap fools. (instead of me being made the fool)

    • nhpeha sdiomomthfoxn xaxphmmommmmrhhm cxnmmcrxemcmccccm mmmmmh rxrcmiiihxlsoreoreoreorev cxcchhmxccrrrrhhhrru ncxdxexlerrddmmmmgcchhcc

      Upcased and without spaces is the solution.

  • The article asks if anyone has composed other programming puzzles, like a parenthesis puzzle.

    Any LISP program should qualify for that one.

  • 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?

  • If you have a programming problem that requires regular expressions, you now have two problems.

  • That's not right (Score:3)

    by iYk6 (1425255) on Thursday February 14, 2013 @02:35AM (#42892883)

    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 ".*".

  • In many places, there is /.*/ But shouldn't that be /.+/ ? Or am I to assume that it's accepting spaces? Most likely not.

    • Re: (Score:2)

      by seebs (15766)

      No, they mean ".*". A .* is zero or more characters. In some cases, yes, that means zero.

  • 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)

      by gd2shoe (747932)

      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.

  • 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 spac

  • 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 * .

    • Re: (Score:3)

      by gd2shoe (747932)

      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)

    by Sam H (3979) <sam@zoy.org> on Thursday February 14, 2013 @06:41AM (#42893913) Homepage

    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.

    • 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.

    • 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.

  • 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.

  • Lacking a printer, I threw together an interactive version: http://jimbly.github.com/regex-crossword/ [github.com] Enjoy!

The economy depends about as much on economists as the weather does on weather forecasters. -- Jean-Paul Kauffmann

Close