Manlier Word Game

Posted on by on January 6th, 2013 | 0 Comments »

Overview

Saw this problem in the newspaper and it caught my eye as an interesting way to play with permutations.  Here is the problem and the rules:

Manlier: Having more of the good qualities associated with men.

Problem

Can you find 69 or more words in MANLIER?

Rules

  1. Words must be four or more letters.
  2. Words which acquire four letters by the addition of "s," such as "bats" or "dies," are not used.
  3. Only one form of a verb is used. For example, either "pose" or "posed," not both.
  4. Proper nouns are not used.
  5. Slang words are not used.
  6. Time limit 60 minutes.

Work

Explanation

I generated permutations of 4 to 7 letters (using only letters in MANLIER) and compared the results to a scrabble dictionary, and then stored the results in a list of unique words which I finally printed.

Source Code

////////////////////////////////////////////////////////////////////////////////
/**
 *  @file manlier.cpp
 *  @brief Can you find 69 or more words in MANLIER?
 *
 *  @title Manlier
 *  @author Nicholas Guthrie
 *  @email nick@nickguthrie.com
 *  @web http//nickguthrie.com
 *  @created January 6, 2013
 * 
 *  Compile with: g++ -g -o ./manlier manlier.cpp
 */
////////////////////////////////////////////////////////////////////////////////
//
// Manlier (MAN-lee-er): Having more of the good qualities associtated with men.
//
// ---------- Rules of the Game ----------
// 1. Words must be four or more letters.
// 2. Words which acquire four letters by the addition of "s," such as "bats" or
//    "dies," are not used.
// 3. Only one form of a verb is used.
//    For example, either "pose" or "posed," not both.
// 4. Proper nouns are not used.
// 5. Slang words are not used.
// 6. Time limit 60 minutes.
// 
////////////////////////////////////////////////////////////////////////////////
//------------------------------------------------------------------ :Libraries:
//                      _    _ _                 _        
//                     | |  (_) |__ _ _ __ _ _ _(_)___ ___
//                     | |__| | '_ \ '_/ _` | '_| / -_|_-<
//                     |____|_|_.__/_| \__,_|_| |_\___/__/
//                                                        
// -----------------------------------------------------------------------------
// Input-Output
#include <iostream>             /* input-output stream - necessary for cout */
#include <fstream>              /* to use file stream */
using namespace std;            /* to not need std:: on all io */  
#include <string>               /* to use strings */
#include <vector>
#include <algorithm>            /* use sort and find */

bool stringCompare( const string &left, const string &right )
{
    for(
	string::const_iterator lit = left.begin(),
	    rit = right.begin(); lit != left.end()
	    && rit != right.end(); ++lit, ++rit )
    {
	if( tolower( *lit ) < tolower( *rit ) )
	{
	    return true;
	}
	else if( tolower( *lit ) > tolower( *rit ) )
	{
	    return false;
	}
    }
    if( left.size() < right.size() )
    {
	return true;
    }
    return false;
}
////////////////////////////////////////////////////////////////////////////////
/**
 *  @class Hangman
 *  @brief A fun hangman game for a person to play.
 */
////////////////////////////////////////////////////////////////////////////////
class Puzzle
{
public:
    //Initializes
    Puzzle();
    void read_dictionary();
    bool parse_word(string & word);
    bool find_word(string str);
    void permute_words();
    void add_word(string str);
    //Mutators
    //Printing
    void print_found_words();
    int get_solutions();
    
private:
    vector<string> mv_dictionary;
    vector<string> f_words;
    string m_puzzle;
    int num_solutions;
};
//----------------------------------------------------------------------- :Main:
//                              __  __      _      
//                             |  \/  |__ _(_)_ _  
//                             | |\/| / _` | | ' \ 
//                             |_|  |_\__,_|_|_||_|
//                                                 
// -----------------------------------------------------------------------------
int main ( int argc, char* argv[] )
{
    //////////////////////////////
    // Input 
    //////////////////////////////
    Puzzle man;
    man.read_dictionary();
    man.permute_words();
    
    //////////////////////////////
    // Output
    //////////////////////////////
    man.print_found_words();
    cout << man.get_solutions() << " solutions found." << endl;
      
    //////////////////////////////
    // Exititing
    //////////////////////////////
    return 0;
}
//------------------------------------------------------------------ :Functions:
//                      ___             _   _             
//                     | __|  _ _ _  __| |_(_)___ _ _  ___
//                     | _| || | ' \/ _|  _| / _ \ ' \(_-<
//                     |_| \_,_|_||_\__|\__|_\___/_||_/__/
//                                                        
//
//-----------------------------------------------------------------------------
Puzzle::Puzzle()
{
    num_solutions = 0;
}
////////////////////////////////////////////////////////////////////////////////
/**
 * @brief Reads a file "dictionary.txt" which contains all valid words
 */
////////////////////////////////////////////////////////////////////////////////
void Puzzle::read_dictionary()
{
    ifstream f_in;
    string str;

    // Open File
    f_in.open("dictionary.txt");

    // Error Checking
    if (f_in==NULL)
    {
	cout << "ERROR opening file.\n"
	     << "  Must have a file called hangmand-words.txt.\n"
	     << "  Exiting Program." << endl;
	exit(1);
    }

    //@condition while able to read lines from the file
    while( getline (f_in,str) )
    {
	//@condition - parsed a new valid puzzle
	if( parse_word( str ) )
	{
	    mv_dictionary.push_back( str );
	}
    }
}
////////////////////////////////////////////////////////////////////////////////
/**
 * @brief Checks for a valid word
 * @param[in] The word to check for validity.
 * @return True if the word is valid and not empty.
 */
////////////////////////////////////////////////////////////////////////////////
bool Puzzle::parse_word(string & word)
{
    //@condition Is not a valid puzzle, empty or too small.
    if(word == "" || word.size() < 4 )
	return false;

    string::iterator its = word.begin();

    //@condition for all characters in the word
    while( its != word.end() )
    {
	//@condition Is a letter, make it lowercase.
	if(isalpha(*its))
	    *its = tolower(*its);
	its++;
    }
    //@condition Is a valid puzzle (has more than nothing)
    return true;
}
////////////////////////////////////////////////////////////////////////////////
/**
 * @brief Searches if the word is stored in the valid dictionary.
 * @param[in] The word to search for in the dictionary.
 * @return True if the word is found in the dictionary.
 */
////////////////////////////////////////////////////////////////////////////////
bool Puzzle::find_word(string str)
{
    vector<string>::iterator it;
    it = find (mv_dictionary.begin(), mv_dictionary.end(), str);

    //@condition return false if not found, true otherwise
    if( it == mv_dictionary.end() )
	return false;
    else
	return true;
}
////////////////////////////////////////////////////////////////////////////////
/**
 * @brief Finds all permutations of manlier and searches valid dictionary.
 */
////////////////////////////////////////////////////////////////////////////////
void Puzzle::permute_words()
{
    //////////////////////////////
    // Variables
    //////////////////////////////
    string alpha = "", beta, charlie, delta; //words of size 4,5,6,7;
    string temp[10] = {"m", "a", "n", "l", "i", "e", "r"};
    vector<string> x(temp,temp+7);

    do
    {
	for(int i=0; i<7; i++)
	{
	    int a = i%7;
	    int b = (i+1)%7;
	    int c = (i+2)%7;
	    int d = (i+3)%7;
	    int e = (i+4)%7;
	    int f = (i+5)%7;
	    int g = (i+6)%7;

	    
	    alpha = x[a] + x[b] + x[c] + x[d];
	    beta = alpha + x[e];
	    charlie = beta + x[f];
	    delta = charlie + x[g];

	    add_word(alpha);
	    add_word(beta);
	    add_word(charlie);
	    add_word(delta);
	}

    } while (next_permutation(x.begin(), x.end()));
}
////////////////////////////////////////////////////////////////////////////////
/**
 * @brief Prints all of the found words. 
 */
////////////////////////////////////////////////////////////////////////////////
void Puzzle::print_found_words()
{
    sort( f_words.begin(), f_words.end(), stringCompare );
    
    ofstream ostream;
    ostream.open ("solution.txt");
    for( int i=0; i < f_words.size(); i++ )
    {
	int j = i+1;
	if (j < 100)
	{
	    cout << "0"; ostream << "0";
	}
	if (j < 10)
	{
	    cout << "0"; ostream << "0";
	}
	cout << j << " " << f_words.at(i) << "\n";
	ostream << j << " " << f_words.at(i) << "\n";
    }
    ostream.close();
}
////////////////////////////////////////////////////////////////////////////////
/**
 * @brief Adds a found word to the list if it doesn't exist already.
 */
////////////////////////////////////////////////////////////////////////////////
void Puzzle::add_word(string str)
{
    vector<string>::iterator it;
    it = find (f_words.begin(), f_words.end(), str);

    //@condition if it is a valid word, add it to the list.
    if( find_word(str) && it == f_words.end() )
    {
	f_words.push_back(str);
	num_solutions++;
    }
	
}
////////////////////////////////////////////////////////////////////////////////
/**
 * @brief Returns the number of solutions found.
 */
////////////////////////////////////////////////////////////////////////////////
int Puzzle::get_solutions()
{
    return num_solutions;  
}

Solution/Output

I was able to find 104 solutions:
001 aimer
002 airmen
003 airn
004 alien
005 aline
006 aliner
007 alme
008 almner
009 amen
010 amie
011 amin
012 amine
013 amir
014 anil
015 anile
016 anime
017 ariel
018 aril
019 earl
020 earn
021 elain
022 elan
023 emir
024 ilea
025 inarm
026 lain
027 lair
028 lame
029 lamer
030 lane
031 lari
032 larine
033 lean
034 lear
035 learn
036 leman
037 liane
038 liar
039 lien
040 lier
041 lima
042 liman
043 lime
044 limen
045 limn
046 limner
047 line
048 linear
049 liner
050 lira
051 lire
052 mail
053 maile
054 mailer
055 main
056 mair
057 male
058 maline
059 mane
060 manlier
061 mare
062 marine
063 marl
064 marlin
065 marline
066 meal
067 mean
068 menial
069 merl
070 merlin
071 mien
072 mile
073 miler
074 mina
075 minae
076 mine
077 miner
078 mineral
079 mire
080 nail
081 nailer
082 name
083 namer
084 near
085 nema
086 rail
087 rain
088 rale
089 rami
090 ramie
091 rani
092 real
093 realm
094 ream
095 rein
096 remail
097 remain
098 reman
099 renail
100 renal
101 rial
102 riel
103 rile
104 rime
104 solutions found.
Othello’s Green I’d Monster
A Simple ls Program

Categorized Under

BlogC++Programming

About Nick Guthrie

» has written 38 posts

Leave a Reply

You must be logged in to post a comment.

History