Programming Assignment Bulls and Cows
This project is about a modified version of Bulls and Cows. Instead of playing the game by using 4-letter words, the number of letters in a word in this modified version for the player to guess ranges from 1 to 21 letters. The modified version of the game plays as follows:
• A player (Host) comes up with a valid secret word from the word list.
• Another player (Guesser) tries to come up with a probe word.
• The Host responds by giving the Guesser the number of bulls and cows for the probe word. "Bulls" gives information about how many letters in the probe word match the letters in the secret word in the right position while "Cows" gives information about how many letters in the probe word match the letters in the secret word in the wrong position. The number of letters counted in "Bulls" cannot be double counted in "Cows" though.
• If the Guesser correctly guessed the secret word, then the game is over. Otherwise,the Guesser needs to come up with another probe word and obtains feedback from the Host until the Guesser correctly guesses the secret word.
For example, if the secret word is apocalypse and the probe word is abstract, then the Host should respond 1 "Bulls" and 3 "Cows". If the secret word is apocalypse and the probe word is a, then the Host should respond 1 "Bulls" and 0 "Cows". If the secret word is abstract and the probe word is abstain, then the Host should respond 4 "Bulls" and 1 "Cows".
Your task for this project will be to implement a Bulls and Cows solver that, given a secret word in the test program, will produce as few number of probe words as possible that lead the Guesser to correctly guess the secret word. Because we may give you a large word list, you will want to come up with an efficient way of generating as few number of probe words as possible that correctly guess the secret word. It is possible that your algorithm might correctly guess the secret word in 1 step, but the probability is 1/60000 given a word list with 60,000 words.
Here is the interface for a Game class (Game.h) that lets you initialize a word list we provide in the constructor, set up a a secret word, determine the length of the secret word, and determine the "Bulls" (nInRightPlace) and "Cows" (nInWrongPlace) from the probe word provided by the Player:
class Game
{
public:
Game(const vector &words); bool setSecretWord(const string &sw); int secretWordLength() const;
void probe(const string &probeWord, int &nInRightPlace, int &nInWrongPlace);
~Game(); private:
// Prevent people from copying Game objects. Game(const Game&);
Game& operator=(const Game&);
// Define your own data structure here
// ...
string secretWord;
};
• The constructor stores the given word list in a data structure of your choice as private data member. setSecretWord() takes in a secret word and checks against the word list to determine if the given secret word is in the word list. If it is, return true, otherwise return false.
• secretWordLength() returns the length of the secret word.
• probe() takes in a probe word provided by the Player, determines "Bulls" and "Cows", stores the correct value of "Bulls" in nInRightPlace, and stores the correct value of "Cows" in nInWrongPlace
• The destructor does whatever is necessary to clean up.
Here is the interface for a Player class (Player.h).
class Player
{
public:
Player(const vector &words); string generateProbeWord();
void learn(string probe, int nInRightPlace, int nInWrongPlace);
~Player(); private:
// Prevent people from copying Player objects. Player(const Player&);
Player& operator=(const Player&);
// Define your own data structure here
};
• The constructor stores the given word list in a data structure of your choice as private data member. You may also need to build a data structure inside the constructor that allows you to efficiently search for the next probe word to return when generateProbeWord() is called.
• generateProbeWord() returns a probe word chosen by the Player.
• learn() tells the Player how many bulls and cows are in the probe word; that information presumably comes from a previous call to Game::probe(). The Player object does what is necessary to update its data structures in light of that information.
• The destructor does whatever is necessary to clean up your data structures.
None of these member functions may read from cin or write to cout. (They can write debugging information to cerr, which we will ignore.)
Here is a very simple working solution for a Player class that does not meet the requirement for this project as it performs a linear search through the word list.
class Player
{
public:
Player(const vector &words) { wordlist = words;
n = 0;
}
string generateProbeWord() { return wordlist[n++];
}
void learn(string probe, int nInRightPlace, int nInWrongPlace) { }
~Player() { } private:
// Prevent people from copying Player objects.
Player(const Player&);
Player& operator=(const Player&);
// Define your own data structure here vector wordlist;
int n;
};
When we test your code, we will use a large word list file of about 60,000 words that we will provide you here. (The file came from an open-source wordlist project that is hosted at wordlist.sourceforge.net. If you're interested in building a freeware or open-source application that requires a large list of English words, this is a great place to get a wordlist for it.) Here's a small example of some tests:
#include
#include
...
using namespace std;
const char* filename = " ";
// A Windows user might have the path be "C:/CS32/P4/wordlist.txt"
// A Mac user might have it be "/Users/fred/CS32/P4/wordlist.txt"
void play(Game& g, Player &p)
{
int secretLength = g.secretWordLength(); int nTurns = 0;
for(;;)
{
int nInRightPlace, nInWrongPlace; string probe = p.generateProbeWord();
g.probe(probe, nInRightPlace, nInWrongPlace);
// repeat probes until word is guessed nTurns++;
if (nInRightPlace == secretLength) break;
p.learn(probe, nInRightPlace, nInWrongPlace);
}
cerr << "The Player probed " << nTurns << " times!" << endl;
}
int main()
{
ifstream wordlistfile(filename); if (!wordlistfile)
{
cerr << "Cannot open " << filename << "!" << endl; return 1;
}
vector words;
string w;
while (wordlistfile >> w)
words.push_back(w);
Player player(words); Game g(words);
if (!g.setSecretWord("apocalypse")) // Supply the secret word
{
cerr << "Secret word is not in word list!" << endl;
return 1;
}
play(g, player);
}
Here are some requirements your program must meet:
• You must not add any public members to Game or Player. You are allowed to add private data members and private member functions if you wish.
• Your program should be efficient enough to generate as few number of probe words as possible that lead the Player (Guesser) to correctly guess the secret word. A linear search solution provided above will guarantee to fail the performance requirement for this project. In order to satisfy this performance requirement, your Player constructor is allowed to run up to 25 seconds on the SEASnet Linux server, and your generateProbeWord and learn functions are allowed to run up to 5 seconds each on the SEASnet Linux server.
• You may design interesting data structures of your own, but the only containers from the C++ standard library you may use are vector, list, stack, and queue (and string). If you want anything fancier, implement it yourself. (It'll be a good exercise for you.) If you decide to use a hash table, it must not have more than 100000 buckets. (Using a hash table is a good way to get reasonable speed with a large word list.) Although we're limiting your use of containers from the library, you are free to use library algorithms (e.g., sort).
• During execution, your program must not perform any undefined actions, such as dereferencing a null or uninitialized pointer.
Attachment:- Wordlist.rar