Searching /usr/dict/words to find words with certain properties

Question

I would like to write a script to search through /usr/dict/words to find all words that meet some criteria I specify. For example, finding all palindromic words (like "racecar", "madam", etc.) or finding all words where the first and second halves reversed also form a word (like "german" and "manger"). The framework of the script would be a simple loop to read each word in the dictionary, and I could change the criteria depending on what I want to look for by substituting an expression or something similar.

I figure I would need to involve regular expressions somehow (or otherwise find a way to look at individual characters in each word). I would also need a way to compare the characters in my current word to the other words in the dictionary (such as with my second example above).

What would be the best tool(s) to use for this task?

Answer 1

The following perl script reads a list of words from stdin and/or filename(s) listed on the command line, and prints out all the palindromes and reversible words it finds. It ignores words less than 3 characters long (mostly because my /usr/share/dict/words file has a lot of such junk in it, like 'A' and 'Aa')

This is written in extremely simple perl, intended to be as easy to understand and modify as possible, without using any 'clever' perl tricks.

#! /usr/bin/perl

use strict;

my %dict = ();

print "Palindromes\n";
print "-----------\n";

while(<>) {
   chomp;
   next if (length($_) < 3);

   $dict{$_} = 1;
   print "$_\n" if ($_ eq reverse($_));
}


print "\n\nReversibles\n";
print "-----------\n";
foreach my $key (keys %dict) {

    my $len = length($key);
    my $firsthalf = '';
    my $secondhalf = '';

    if (($len / 2) == int($len/2)) {
        # even length words
        $firsthalf = substr($key,0,int($len/2));
        $secondhalf = substr($key,int($len/2));
    } else {
        # odd length words
        $firsthalf = substr($key,0,int($len/2)+1);
        $secondhalf = substr($key,int($len/2)+1);
    };

    my $rev = $secondhalf . $firsthalf;

    next unless (exists $dict{$rev});

    # don't print if reversed word is a palindrome
    next if ($rev eq $key);

    print  "$key => $rev\n";
}

Produces output like this:

$ ./find-P-and-R.pl /usr/share/dict/words
Palindromes
-----------
MGM
aba
abba
aga
aha
aia
aka
...
...
...


Reversibles
-----------
mode => demo
reenter => terreen
juba => baju
oon => noo
lave => vela
lassi => silas
updo => doup
air => rai
...
...
...

Answer 2

If all you need is to filter regular expressions, use grep. But what you want goes beyond regular expressions. You could use just about any programming language you're comfortable with. Awk is present on all POSIX systems and can easily process files line by line, but its programming features aren't top-notch. Perl makes it easy to do line-by-line processing and has better string processing as well as many available libraries. Python is easy to learn and has a very nice set of available libraries. There are many other possibilities.

To check for palindromes, on *BSD and Linux, you can use the rev utility in a pipeline. It reverses each line of a file. To find palindromes:

rev /usr/dict/words | paste /usr/dict/words - | sed -n 's/^\(.*\)\t\1$/\1/p'
perl -l -ne 'print if reverse($_) eq $_' /usr/dict/words

To find reversable words:

rev /usr/dict/words | grep -Fxf /usr/dict/words
perl -l -ne '$dict{$_} = 1; END {foreach (keys %dict) {print if $dict{reverse($_)}}}'

Answer 3

You can do quite a bit using backreferencing and subexpressions of the sed command. Here are two examples:

Example1: find 3-letter palindromic words in dictionary with o in the middle

  $ sed -E -n '/^(.)o\1$/p' /usr/share/dict/words
  bob
  mom
  non
  pop
  sos
  tot
  wow

Example 2: find 6-letter palindromic words

  $ sed -E -n '/^(.)(.)(.)\3\2\1$/p' /usr/share/dict/words
  redder