Nicks Mind Portal
Insight into something.
Manlier Word Game
Posted on by Nick Guthrie 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
- Words must be four or more letters.
- Words which acquire four letters by the addition of "s," such as "bats" or "dies," are not used.
- Only one form of a verb is used. For example, either "pose" or "posed," not both.
- Proper nouns are not used.
- Slang words are not used.
- 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 rime104 solutions found.
Related Posts
-
TA Lab Program (Stacks & Queues)
Downloads: Assignment : assignment.pdf Source Code : bigint.c Compiled Executables : Windows (to-add) Linux (to-add) Documentation : Doxygen (to-add) Sample Test Files : Official Sample… Read more »
-
Test 1 – Multiple Choice Answer Program (Review)