Solving the hexagon problem using Perl

Here is a problem that I see quite often in one of the afternoon papers such as the "MidDay". You are shown a hexagon, all of whose sides are labelled with one English letter (see above). There is another letter at the centre of the hexagon. The challenge is to make as many words of four or more letters from the letters of the hexagon.

In making a word, each letter must be used once only. Each word must contain the central letter. There should be atleast one seven letter word. Plurals, foreign words & proper names are not allowed.

Given such a hexagon (encoded in some format of your choice) and a file consisting of all acceptable words (e.g. /usr/share/dict/words), can you write a program to solve this problem?

See the Perl program below that does this job quite elegantly. A small point - when I used the dictionary on my Redhat Linux (Fedora Core 3), I could not find the seven letter word because it was missing from the dictionary - I had to figure it out manually. The word was "website" and we are talking of the year 2006 A.D. :-)!

Here is the Perl program:

use strict;
my $regex = '^b{0,1}e{0,2}i{0,1}s{0,1}tw{0,1}$';

foreach my $word (<>)
{
chop $word;
my $newword = join "", (sort (split //, $word));
if ($newword =~ /$regex/ && length($word) >= 4){
print "${word}\n";
}
}
__END__
As you can see above, the regular expression from the image shown was hardcoded into the script but anyone who understands this program will be able to trivially modify it so that the regular expression can be constructed on the fly. Also one small optimization that is possible involves precompiling the regular expression.

- Rajendra Gokhale