Question

Suppose that you are given a set of words; and two words from the set: word 1 and word 2.

Write a program which will transform word 1 into word 2 by changing a single letter in word 1 at a time.

Every transition that word 1 takes will have to be in the set of words.

You must output the smallest sequence of transitions possible to convert word 1 into word 2.

You may assume that all the words in the dictionary are the same length.

The first line will be word 1 and word 2 separated by a comma, followed by the set of words. The set of words will be terminated by a ‘-1’.

Input:

DOG,GOD

DOG

BOG

GOG

ABH

GOD

THU

IOP

-1

Output:

DOG -> GOG -> GOD

I have a code that does this but its all done in a textfile, I need it to be all on the console(using cin,cout and not the fstream)

#include
#include
#include
#include
#include
#include
#include

using namespace std;

class WordLadder {

private:
list dict; //list of possible words in ladder
void printstack(stack stack, ofstream &outfile);
bool wordcompare(string word, string dictword);

public:
WordLadder(const string &file);
void outputLadder(const string &start, const string &end, const string &outputFile);
};
WordLadder::WordLadder(const string &file) {
string word;
ifstream infile;
infile.open(file.c_str());
if (infile.is_open()) {
while (!infile.eof()) {
getline(infile,word);
if (word.size() != 5) {
cout << "Warning: Word longer than 5 characters detected in dictionary." << endl;
}
dict.push_back(word.c_str());
}
infile.close();
return;
} else {
cout << "Error opening input file." << endl;
return;
}
}
void WordLadder::outputLadder(const string &start, const string &end, const string &outputFile) {

cout << "Finding word ladder from " << start << " to " << end << ": ";
ofstream outfile;
outfile.open(outputFile.c_str());
if (!outfile.is_open()) {
cout << "Opening output file failed." << endl;
return;
}
// set up the stuff
queue< stack > queue;
stack< string > stack;
string word;
list::iterator it;
bool startgood = false, endgood = false;

// initial validity tests
for (it=dict.begin();it!=dict.end();++it) {
if (*it == start) {
startgood = true;
}
if (*it == end) {
endgood = true;
}
}
if (!startgood || !endgood) {
cout << "Starting or ending word was not found in the dictionary." << endl;
return;
}
if (start == end) {
outfile << start;
return;
}
stack.push(start);
queue.push(stack);

// find the first word, delete it
dict.remove(start);
while(!queue.empty()) {
// get the word off of the top of the front stack
word = queue.front().top();
for (it=dict.begin();it!=dict.end();++it) {
// wordcompare will decide if the word is off by one from the dictionary word.
if (wordcompare(word,*it)) {
if (*it == end) {
// if the off by one word is the last word
// the ladder contains the entire stack -- output and return.
queue.front().push(end);
//print the stack
printstack(queue.front(),outfile);
//cout << "Operations: " << opers << endl << endl;
return;
}
// otherwise, create a copy of the front stack and push the
// off by one word from dictionary
stack = queue.front();
stack.push(*it);
queue.push(stack);
it = dict.erase(it);
// decrement iterator by one to correct for the advanced iterator
// returned by the std::list::erase function
it--;
}
}
queue.pop();
}
// if a word ladder is not found, then do this
if (outfile.is_open()) {
outfile << "No Word Ladder Found!!";
cout << "No Word Ladder Found!!";
}
}

bool WordLadder::wordcompare(string word, string dictword) {
int hits = 0;
for (int i=0; i<5; i++) {
if (word[i] == dictword[i]) { hits++; }
}
if (hits == 4) {
return true;
} else {
return false;
}
}

void WordLadder::printstack(stack stack, ofstream &outfile) {

int i = 0;
vector ladder;
while (!stack.empty()) {
ladder.push_back(stack.top());
stack.pop();
i++;
}

if (outfile.is_open()) {
while (i!=0) {
i--;
outfile << ladder.at(i);
cout << ladder.at(i);
if (i!=0) {
outfile << " ";
cout << " ";
}
}
cout << endl;
}
}

int main() {
string dictFile, wordBegin, wordEnd, outFile;
cout << "Enter the name of the dictionary file: ";
cin >> dictFile;
cout << endl;
cout << "Enter the name of the output file: ";
cin >> outFile;
cout << endl;
cout << "Enter the first word: ";
cin >> wordBegin;
cout << endl;
while (wordBegin.size() != 5) {
cout << "Word must have exactly 5 characters." << endl
<< "Please reenter the first word: ";
cin >> wordBegin;
cout << endl;
}
cout << "Enter the last word: ";
cin >> wordEnd;
cout << endl;
while (wordEnd.size() != 5) {
cout << "Word must have exactly 5 characters." << endl
<< "Please reenter the last word: ";
cin >> wordEnd;
cout << endl;
}
WordLadder wl(dictFile);
wl.outputLadder(wordBegin, wordEnd, outFile);
return 0;
}

Answer 1

CODE:

#include <list>
#include <stack>
#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

class WordLadder {

private:
   list<string> dict; //list of possible words in ladder
   void printstack(stack<string> stack);
   bool wordcompare(string word, string dictword);

public:
   WordLadder(const string& file);
   void outputLadder(const string& start, const string& end);
};
WordLadder::WordLadder(const string& file) {
   string word;
   ifstream infile;
   infile.open(file.c_str());
   if (infile.is_open()) {
       while (!infile.eof()) {
           getline(infile, word);
           if (word.size() != 5) {
               cout << "Warning: Word longer/smaller than 5 characters detected in dictionary." << endl;
           }else

// Add to dictionary only if character length is matched
           dict.push_back(word.c_str());
       }
       infile.close();
       return;
   }
   else {
       cout << "Error opening input file." << endl;
       return;
   }
}
// Removed the outfile logic completely
void WordLadder::outputLadder(const string& start, const string& end) {

   cout << "Finding word ladder from " << start << " to " << end << ": ";

   // set up the stuff
   queue<stack<string>> queue;
   stack<string> stack;
   string word;
   list<string>::iterator it;
   bool startgood = false, endgood = false;

   // initial validity tests
   for (it = dict.begin(); it != dict.end(); ++it) {
       if (*it == start) {
           startgood = true;
       }
       if (*it == end) {
           endgood = true;
       }
   }
   if (!startgood || !endgood) {
       cout << "Starting or ending word was not found in the dictionary." << endl;
       return;
   }
   if (start == end) {
       return;
   }
   stack.push(start);
   queue.push(stack);

   // find the first word, delete it
   dict.remove(start);
   while (!queue.empty()) {
       // get the word off of the top of the front stack
       word = queue.front().top();
       for (it = dict.begin(); it != dict.end(); ++it) {
           // wordcompare will decide if the word is off by one from the dictionary word.
           if (wordcompare(word, *it)) {
               if (*it == end) {
                   // if the off by one word is the last word
                   // the ladder contains the entire stack -- output and return.
                   queue.front().push(end);
                   //print the stack
                   printstack(queue.front());
                   //cout << "Operations: " << opers << endl << endl;
                   return;
               }
               // otherwise, create a copy of the front stack and push the
               // off by one word from dictionary
               stack = queue.front();
               stack.push(*it);
               queue.push(stack);
               it = dict.erase(it);
               // decrement iterator by one to correct for the advanced iterator
               // returned by the std::list::erase function
               it--;
           }
       }
       queue.pop();
   }
}

// same logic as before, no change
bool WordLadder::wordcompare(string word, string dictword) {
   int hits = 0;
   for (int i = 0; i < 5; i++) {
       if (word[i] == dictword[i]) { hits++; }
   }
   if (hits == 4) {
       return true;
   }
   else {
       return false;
   }
}

// Removed the writing to outfile logic completely
// Now, this prints only to cout
void WordLadder::printstack(stack<string> stack) {

   int i = 0;
   vector<string> ladder;
   while (!stack.empty()) {
       ladder.push_back(stack.top());
       stack.pop();
       i++;
   }
       cout << endl;
       while (i != 0) {
           i--;
           cout << ladder.at(i);
           if (i != 0) {
               cout << " ";
           }
       cout << endl;
   }
}

// Removed the outfile logic completely, outFile removed
// cin to take in the outfile removed
int main() {
   string dictFile, wordBegin, wordEnd;
   cout << "Enter the name of the dictionary file: ";
   cin >> dictFile;
   cout << endl;
   cout << "Enter the first word: ";
   cin >> wordBegin;
   cout << endl;
   while (wordBegin.size() != 5) {
       cout << "Word must have exactly 5 characters." << endl
           << "Please reenter the first word: ";
       cin >> wordBegin;
       cout << endl;
   }
   cout << "Enter the last word: ";
   cin >> wordEnd;
   cout << endl;
   while (wordEnd.size() != 5) {
       cout << "Word must have exactly 5 characters." << endl
           << "Please reenter the last word: ";
       cin >> wordEnd;
       cout << endl;
   }
   WordLadder wl(dictFile);
   // parameter to pass the outfile is removed
   wl.outputLadder(wordBegin, wordEnd);
   return 0;
}

INPUT DICTIONARY FILE:

DOGOD
DDOGO
DOGDO
DGOOD
DGGOD
DOGOO
DGOTD
IOPOO
-1

RESULT: