Build a one-word search generator The word BANANA appears exactly once in this word search:

B A N A A N B B
A B A N A B A N
A N A B N N A A
N N B A A A N N
N A A N N N B A
A N N N B A N A
N A A B A N A N
B A N A N B B A


The word search above contains only one occurrence of the word BANANA looking up, down, left, right, or diagonally, but it has lot of similar words, like BANANB, BANNANA, BNANA, etc.

Your job is to build a program that will generate infuriating word searches like this one.

Your program will take as input:


One word, in all capital letters, containing from three to seven unique letters with at least four letters total.
One number, to represent the dimension of the square grid for the word search. The number must be at least the number of letters in the word.


And then, output a word search using only the letters in the word, that contains exactly one occurrence of the input word, and as many infuriators as possible.

An infuriator is defined as a string that has a Damerau-Levenshtein distance of one from the target word and begins with the same letter as the word. For BANANA, this would include words like:


BANBNA, where one of the letters was substituted.
BANNANA or BANAANA, where an extra letter was added.
BANAN, BNANA, where a letter was deleted, but not ANANA, since there's no longer a B.
BAANNA or BANAAN, where two consecutive letters were switched.


When counting infuriators on a word search grid, they may overlap, but you cannot count a large string if it completely contains a smaller string you've already counted, or vice versa. (If you have BANANB, you can't count it again if you've already counted the BANAN or the backwards BNANA inside it.) You also cannot count any strings that completely contain or are completely contained by the target word itself (you cannot count the specific BANAN that is part of BANANA, nor BANANAA or BANANAN.)



Your program will be tested on a specific word list composed of the words that fit the input word requirement (to be given later once I've generated it), on a grid size equal to double the length of the word, and will be scored on the number of infuriators present in each grid. Please post your results for the inputs BANANA 12, ELEMENT 14, and ABRACADABRA 22 for verification.
C++

I wrote this one up today. It is not the most efficient way and does not always generate the most random looking word searches but it gets the job done and it does it relatively quick.

Bonus: Supports Palindromes too!!!

It works by taking input for the word and the size of the word search. It then generates infurators by dropping letters, inserting letters, or flipping letters. It then adds those to the grid as well as the correct word. It then checks all instances of the first letter in every direction for the word. If 1 instance is not found ( 2 for palindromes ) it brute forces the cycle over. It then outputs the word search to console as well as a file.

Here it is at 213 lines of code with whitespace and comments.

#include &lt;fstream&gt;
#include &lt;iostream&gt;
#include &lt;string&gt;
#include &lt;vector&gt;

#include &lt;stdio.h&gt;
#include &lt;time.h&gt;

// Keep Track of Coordinates
struct XY {

public:
    int X;
    int Y;
};

// Just in case someone breaks the rules
std::string ToUppercase( const std::string&amp; pWord ) {
    char *myArray = new char[ pWord.size() + 1 ];
    myArray[ pWord.size() ] = 0;
    memcpy( myArray, pWord.c_str(), pWord.size() );

    for ( unsigned int i = 0; i &lt; pWord.size(); i++ ) {
        if ( (int) myArray[ i ] &gt;= 97 &amp;&amp; (int) myArray[ i ] &lt;= 122 ) {
            myArray[ i ] = (char) ( (int) myArray[ i ] - 32 );
        }
    }   

    return std::string( myArray );
}

// Random number between a max and min inclusively 
int RandomBetween( int pMin, int pMax ) {
    return rand() % ( pMax - pMin + 1 ) + pMin;
}

// Find all instances of a character
std::vector&lt;XY&gt; FindHotspots( const std::vector&lt;char&gt; &amp;pWordSearch, char pFirstChar, unsigned int pLength ) {
    std::vector&lt;XY&gt; myPoints;
    for ( unsigned int i = 0; i &lt; pLength; i++ ) {
        for ( unsigned int j = 0; j &lt; pLength; j++ ) {
            if ( pWordSearch[ i * pLength + j ] == pFirstChar ) {
                XY myXY;
                myXY.X = i;
                myXY.Y = j;
                myPoints.push_back( myXY );
            }
        }
    }
    return myPoints;
}

// Searchs each index from specific point in certain direction for word
// True if word is found
bool Found( const std::vector&lt;char&gt; &amp;pWordSearch, const std::string &amp;pWord, int pRow, int pCol, int pX, int pY, int pLength ) {
    for ( unsigned int i = 0; i &lt; pWord.length(); i++ ) {
        if ( pRow &lt; 0 || pCol &lt; 0 || pRow &gt; pLength - 1 || pCol &gt; pLength - 1 ) 
            return false;
        if ( pWord[ i ] != pWordSearch[ pRow * pLength + pCol ] )
            return false;
        pRow += pX;
        pCol += pY;
    }
    return true;
}

// Goes through all the hotspots and searchs all 8 directions for the word
int FindSolution( const std::vector&lt;char&gt; &amp;pWordSearch, const std::string &amp;pWord, unsigned int pLength ) {
    std::vector&lt;XY&gt; myHotspots = FindHotspots( pWordSearch, pWord[ 0 ], pLength );

    int mySolutions = 0;
    for ( unsigned int i = 0; i &lt; myHotspots.size(); i++ ) {
        if ( Found( pWordSearch, pWord, myHotspots[ i ].X, myHotspots[ i ].Y, 1, 0, pLength ) )
            mySolutions++;
        if ( Found( pWordSearch, pWord, myHotspots[ i ].X, myHotspots[ i ].Y, 1, 1, pLength ) )
            mySolutions++;
        if ( Found( pWordSearch, pWord, myHotspots[ i ].X, myHotspots[ i ].Y, 0, 1, pLength ) )
            mySolutions++;
        if ( Found( pWordSearch, pWord, myHotspots[ i ].X, myHotspots[ i ].Y, -1, 1, pLength ) )
            mySolutions++;
        if ( Found( pWordSearch, pWord, myHotspots[ i ].X, myHotspots[ i ].Y, -1, 0, pLength ) )
            mySolutions++;
        if ( Found( pWordSearch, pWord, myHotspots[ i ].X, myHotspots[ i ].Y, -1, -1, pLength ) )
            mySolutions++;
        if ( Found( pWordSearch, pWord, myHotspots[ i ].X, myHotspots[ i ].Y, 0, -1, pLength ) )
            mySolutions++;
        if ( Found( pWordSearch, pWord, myHotspots[ i ].X, myHotspots[ i ].Y, 1, -1, pLength ) )
            mySolutions++;
    }
    return mySolutions;
}

// Generate words that are similar
//
// 1. Word with last character same as first
// 2. Word with 1 character removed
// 3. Word with 1 character added
std::vector&lt;std::string&gt; GenerateInfurators( const std::string &amp;pWord ) {
    std::vector&lt;std::string&gt; myInfurators;
    for ( unsigned int i = 0; i &lt; pWord.size() / 2; i++ ) {
        char myReplace = '0';
        do { 
            myReplace = pWord[ RandomBetween( 0, pWord.size() - 1 ) ];
        } while ( myReplace == pWord[ pWord.size() - 1 ] );
        myInfurators.push_back( pWord.substr( 0, pWord.size() - 2 ) + myReplace );
    }

    for ( unsigned int i = 1; i &lt; pWord.size() - 2; i++ ) {
        myInfurators.push_back( pWord.substr( 0, i ) + pWord.substr( i + 1 ) ); 

        std::string myWord = pWord;
        myInfurators.push_back( myWord.insert( i, 1, pWord[ i - 1 ] ) );
    }

    return myInfurators;
}

// Adds word in random position in word search
void AddWordRandomly( std::vector&lt;char&gt; &amp;pWordSearch, const std::string &amp;pWord, unsigned int pLength ) {
    int myXDirec = 0;
    int myYDirec = 0;
    do { 
        myXDirec = RandomBetween( -1, 1 );
        myYDirec = RandomBetween( -1, 1 );
    } while ( myXDirec == 0 &amp;&amp; myYDirec == 0 );

    int myRow = 0;
    if ( myXDirec == 0 ) {
        myRow = RandomBetween( 0, pLength - 1 );
    } else if ( myXDirec &gt; 0 ) {
        myRow = RandomBetween( 0, pLength - pWord.size() - 1 );
    } else {
        myRow = RandomBetween( pWord.size(), pLength - 1 );
    }

    int myCol = 0;
    if ( myYDirec == 0 ) {
        myCol = RandomBetween( 0, pLength - 1 );
    } else if ( myYDirec &gt; 0 ) {
        myCol = RandomBetween( 0, pLength - pWord.size() - 1 );
    } else {
        myCol = RandomBetween( pWord.size(), pLength - 1 );
    }

    for ( unsigned int i = 0; i &lt; pWord.size(); i++ ) {
        pWordSearch[ myRow * pLength + myCol ] = pWord[ i ];
        myRow += myXDirec;
        myCol += myYDirec;
    }
}

// Checks for palindromes
bool WordIsPalindrome( const std::string &amp;pWord ) {
    for ( unsigned int i = 0; i &lt; pWord.size(); i++ ) {
        if ( pWord[ i ] != pWord[ pWord.size() - 1 - i ] ) 
            return false;
    }
    return true;
}

int main() {
    // Handle all input
    std::string myWord;
    std::cin &gt;&gt; myWord;
    myWord = ToUppercase( myWord );

    std::string myStrLength;
    std::cin &gt;&gt; myStrLength;
    unsigned int mySideLength = std::stoi( myStrLength );

    // Setup variables
    // New time seed
    // Generate infurators
    // Add words
    std::vector&lt;char&gt; myWordSearch;
    srand( ( unsigned int ) time( 0 ) );
    std::vector&lt;std::string&gt; myWords = GenerateInfurators( myWord );
    myWords.push_back( myWord );

    bool myWordIsPalindrome = WordIsPalindrome( myWord );

    // Brute force words until 1 instance only
    // 2 instances for palindromes
    do {
        for ( unsigned int i = 0; i &lt; mySideLength * mySideLength; i++ ) {
            myWordSearch.push_back( myWord[ RandomBetween( 0, myWord.size() -1 ) ] );
        }

        for ( unsigned int j = 0; j &lt; 10; j++ ) {
            for ( unsigned int i = 0; i &lt; myWords.size() - 1; i++ ) {
                AddWordRandomly( myWordSearch, myWords[ i ], mySideLength );
            }
        }
        AddWordRandomly( myWordSearch, myWord, mySideLength );
    } while ( ( FindSolution( myWordSearch, myWord, mySideLength ) != 1 &amp;&amp; !myWordIsPalindrome ) || 
            ( FindSolution( myWordSearch, myWord, mySideLength ) != 2 &amp;&amp; myWordIsPalindrome ) );

    // Output to console &amp;&amp; text file
    std::ofstream myFile( "word_search.txt" );
    for ( unsigned int i = 0; i &lt; mySideLength; i++ ) {
        for ( unsigned int j = 0; j &lt; mySideLength; j++ ) {
            myFile &lt;&lt; myWordSearch[ i * mySideLength + j ] &lt;&lt; "";
            std::cout &lt;&lt; myWordSearch[ i * mySideLength + j ] &lt;&lt; " ";
        }
        myFile &lt;&lt; "\n";
        std::cout &lt;&lt; "\n" &lt;&lt; std::endl;
    }
    myFile.close();

    system( "pause" );
    return 0;
}


I am far from a C++ expert so I'm sure there's places where this code could be improved but I was happy with how it ended up. 

Here's the outputs.

BANANA-12:
BBBBBABANABB
BBANAAANANBB
BABAANABBABA
BNAANAAANABN
BANNNNNANBBB
AANABNNANNAA
NAANANAAAABA
ANNNBAANNNBN
ABABNAANABNA
BNNANNAAANNB
BBABAAANBBAB
BBANANNBBABB

ELEMENT-14:
MLELEMEEETNEET
EMTTELTEETELEE
EMNNELEENLNTEL
TLTNEEMEEELMTM
TLEMLNLMEEEETE
TTEEEEEENLNTLE
NETNENEEMTTMEN
ELELTETEEMNMEE
MTEEMTNEEEENEM
ELENEEEMMENNME
ELLEELELTMLETL
ETLTNEMEEELELE
EELTLLLLLMNEEE
EEEELEMNTLEEEE

ABRACADABRA-22:
ACRABAACADABBADBRRAAAA
BBABAABAARBAAAARBAABAA
RARRARBAAABRRRRAAABBRA
DABARRARABBBBABABARABR
BRBACABBAAAABAARRABDAD
ABRRCBDADRARABAACABACR
DCAAARAABCABRCAAAARAAA
AAABACCDCCRACCDARBADBA
CAARAAAAAACAAABBAACARA
ADRABCDBCARBRRRDAABAAR
RARBADAARRAADADAABAAAB
BBRRABAABAAADACACRBRAA
ARBBBDBRADCACCACARBABD
CAARARAAAACACCDARARAAA
ARABADACRARCDADABADBBA
RARAADRRABADBADAABBAAA
RAAAABBBARRDCAAAAAARRA
BABBAAACRDBABCABBBRAAR
AARARAARABRAAARBRRRAAB
BAAAARBRARARACAARAAAAA
ADCBBABRBCBDBRARAARBAA
AARBADAAAARACADABRAABB

Bonus: RACECAR-14:
RRACEARCECARAR
RRRRRRRRRCARAR
RARRAACECARAAA
CCACECRREAECAR
RECEAEEAAECEAE
RCRRREACCCCEAR
RRRARCERREERRR
CCARAAAAECCARC
ECECARRCCECCRR
CARRRACECCARAC
ACRACCAAACCCAR
ARRECRARRAAERR
RRCRACECARRCRR
RRRRACECRARRRR


I may update this to generate slightly more "random" looking word searches.