Can You Do The Regular Expression Crossword?
Written by Lucy Black   
Tuesday, 12 February 2013

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, and .* any number (including zero) of characters and so on.

The regular expression crossword is more a sort of Sudoku style puzzle than crossword however because the clues determine the pattern the the entries in a row have to satisfy.

For example the first row has the regular expression

.*H.*H.*

which means, roughly, any letters followed by an H, then any letters followed by another H and any sequence of letters to finish. In other words the row has two Hs in it. 

If you were to use a regular (no pun intended) crossword layout this would mean that that two regular expressions determined each entry. This isn't enough to make the problem interesting so a regular expression crossword is arranged on a hexagonal grid providing three expression per entry. This is much more  fun.

The puzzle is more like Sudoku than a crossword because the clues provide constraints on what you can put in any particular entry and you have to satisfy all of the constraints. There may  be local solutions that don't belong in complete solution. In other words, the local constraints don't necessarily determine what should be in a given entry.

See if you can get very far:

regcross

PDF download

This particular regular expression crossword was part of this year's MIT Mystery Hunt, and if you don't know anything about it then good - because it could waste a lot of time. 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.

If you want to see a solution then visit:  Regular Crossword Solution

I'm not sure if there have been regular expression crosswords before - if you know of any then add a comment.

What must have occurred to any programmer well before this point is the question of how difficult it would be to write a program that solves any regular expression crossword. An even more interesting question is what would it take to build a program that generated interesting puzzles of this kind?

Also are there any more programming puzzles that we haven't thought up - a  parenthesis puzzle perhaps?

 

 

More Information

PDF download

Regular Crossword Solution

2013 MIT Mystery Hunt

Related Articles

No 16-Clue Sudoku!

.NET Regular Expressions in depth

Master JavaScript Regular Expressions

The Chaos Within Sudoku - A Richter Scale

Picture-Hanging Puzzles

Rubik's cube - the order of God's Number

The maximum overhang algorithm

 

To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, Facebook, Google+ or Linkedin,  or sign up for our weekly newsletter.

 

blog comments powered by Disqus

 

Banner


This Year's Not-To-Miss AI Movie
24/08/2014

A new robot movie will be released soon and it provides a much deeper look at the robot future we are building for ourselves. It is worth seeing the trailer and tracking it down when it comes out.



Racket 6.1
06/08/2014

A new version has been released of Racket, an open source language in the Lisp-Scheme family.


More News

Last Updated ( Thursday, 14 February 2013 )
 
 

   
RSS feed of news items only
I Programmer News
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.