Breaking Eggs And Making Omelettes

Topics On Multimedia Technology and Reverse Engineering


Archives:

Brute Force Word Puzzle

March 24th, 2006 by Multimedia Mike

I used to think that it would be too far-fetched to write a computer program to determine the solution(s) to one of Pickover’s more linguistic puzzles, such as the puzzle for 2006/03/22; find letters to fill in positions 1, 3, and 5 to form an actual word:

1 n 3 i 5 n

I decided to call in the help of a program I had only heard of — Ispell — that I previously had no use for because I’m the most awesome spehlurr I personally know. However, I researched it, installed it, and determined that I could use it to come up with a list of plausible puzzle solutions.

There are only (263 = 17576) possible combinations (assuming an English alphabet here). The list of words takes a fraction of a second to generate using a custom C program on my x86. It takes much longer to run all of them through Ispell, however (just shy of 5 minutes on the same machine). My first run demonstrated that there apparently are 2 solutions to the puzzle. Only the process would not immediately reveal what they are (Ispell outputs a ‘*’ character if the word is okay):

 ./2006-03-22 | ispell -a | grep '*'
 *
 *

Hmm… that’s not terribly helpful. The best solution I could think of to get around this is to ask grep to print out the line numbers (‘-n’ option), capture a list of all the words, and correlate the numbers to the list.

 ./2006-03-22 | ispell -a | grep -n '*'
 6358:*
 10986:*

And the winning words are… jnkinn and qnjinn?! I want my money back. Oops, I just remembered that Ispell appears to double space its output so halving the numbers might yield something more useful. Word #3179 = ensign and word #5493 is indign. I’m not so sure about the latter word, but Dictionary.com approves. Let’s look at the official solutions: ensign and… Indian?! How did the program miss that? Ah, case matters and Indian is a proper noun. I’m not sure if Ispell has an option to ignore case. However, the man page indicates that it will not consider capitalization if the word is ALL CAPS (as in headers) so I modify the word generator to output just that. Now the process finds indian and it also find andian, which Dictionary.com cannot rationalize while Ispell believes it to be a proper noun.

So, with a little tweaking, the computer beats Pickover at his own puzzle. Or maybe we’ll just call it a draw.

Here is the code for the word generator:

#include <stdio.h>

int main(int argc, char *argv[])
{
    int letter1, letter3, letter5;

    for (letter1 = 'A'; letter1 <= 'Z'; letter1++) {
        for (letter3 = 'A'; letter3 <= 'Z'; letter3++) {
            for (letter5 = 'A'; letter5 <= 'Z'; letter5++) {
                printf ("%cN%cI%cN\n", letter1, letter3, letter5);
            }
        }
    }

    return 0;
}

Code colorized by the CodeColorizer.

Posted in Pickover Puzzles | 2 Comments »

2 Responses

  1. pengvado Says:

    ~> grep -i ‘^.n.i.n$’ /usr/share/dict/words
    ensign
    Indian
    indign

    … and took some small fraction of a second.

  2. Multimedia Mike Says:

    Awesome! That’s what this is all about– coming up with better solutions. Or rather, better methods for finding solutions.