This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

Find Longest Word Ladder

By: a guest on Dec 12th, 2012  |  syntax: C++  |  size: 5.49 KB  |  views: 75  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <iostream> // For cout
  2. #include <vector>   // For Vector
  3. #include <string>   // for string
  4. #include <fstream>  // for file reading
  5. #include <algorithm>// for binary_search fun
  6. #include <sstream>  // for string streams
  7.  
  8. using namespace std;
  9.  
  10. // Enumerators
  11. enum ALPHABET {a, b, c, d, e, f, g, h, i, j, k, l, m,
  12.                n, o, p, q, r, s, t, u, v, w, x, y, z};
  13.  
  14. // Global Variable Declarations
  15. vector<string> _Dictionary;
  16. char           _AlphabetList[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
  17.                                     'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
  18. int            _MaxSize = 0;
  19. vector<int>    _MaxVector;
  20.  
  21. // Node Structure
  22. struct node
  23. {
  24.   int word;
  25.   node* next;
  26.   node* last;
  27.  
  28.   node(int a_word)
  29.   {
  30.     word = a_word;
  31.   }
  32. };
  33.  
  34. // Function Declarations
  35. bool dictionary_create();
  36. bool word_exists(vector<string>::iterator a_begin, vector<string>::iterator a_end, string a_word)
  37.                 { return binary_search(a_begin, a_end, a_word); };
  38. void depth_search(int a_start, int a_stop);
  39. int index_of_alphabet(char a_char);
  40. int index_of_Dictionary(string a_word);
  41.  
  42. class Stack
  43. {
  44. public:
  45.   // Constructor and destructor's
  46.   Stack(node* a_top, node* a_target);
  47.   ~Stack();
  48.  
  49.   // Member Functions
  50.   void DepthFirstSearch(int a_start, int a_stop);
  51.   void node_parse(node* a_node);
  52.   void stack_addNode(node* a_node)  { nodeStack.push_back(a_node); wordStack.push_back(a_node->word); };
  53.   void stack_eraseTop();
  54.  
  55.   vector<node*> nodeStack;
  56.   vector<int>   wordStack;
  57. private:
  58.   node* root;
  59.   node* target;
  60.  
  61. };
  62.  
  63. Stack::Stack(node* a_root, node* a_target)
  64. {
  65.   root = a_root;
  66.   target = a_target;
  67.   nodeStack.push_back(root);
  68.   wordStack.push_back(root->word);
  69. }
  70.  
  71. Stack::~Stack()
  72. {
  73.   delete root;
  74.   delete target;
  75. }
  76.  
  77. void Stack::DepthFirstSearch(int a_start, int a_stop)
  78. {
  79.   node_parse(root);
  80.  // system("pause");
  81. }
  82.  
  83. void Stack::node_parse(node* a_node)
  84. {
  85.   for(int curChar = 0; curChar < 4; curChar = curChar + 1)
  86.     for(int curLetter = index_of_alphabet(_Dictionary[root->word][0]) + 1; curLetter != 26; curLetter = curLetter + 1)
  87.     {
  88.       string newWord = _Dictionary[a_node->word];
  89.       newWord[curChar] = _AlphabetList[curLetter];
  90.  
  91.       // Get rid of invalid or already existing words in chain, or if it's itself
  92.  
  93.       if(!word_exists(_Dictionary.begin(), _Dictionary.end(), newWord)) /// TODO: Replace needless functions with std::find(iterator, iterator, value);
  94.         continue;
  95.       if(find(wordStack.begin(), wordStack.end(), index_of_Dictionary(newWord)) != wordStack.end()) // if found
  96.         continue;
  97.       if(newWord == _Dictionary[a_node->word])
  98.         continue;
  99.  
  100.       // check for completion
  101.  
  102.       if(newWord == _Dictionary[target->word])
  103.       {
  104.         cout << "Solution found for " << _Dictionary[root->word] << " to " << _Dictionary[target->word] << " Size = " << wordStack.size() + 1 << endl;
  105.         if(wordStack.size() + 1 > _MaxSize)
  106.         {
  107.           _MaxSize = wordStack.size() + 1;
  108.           _MaxVector.clear();
  109.           for(int i = 0; i < wordStack.size(); i++)
  110.             _MaxVector.push_back(wordStack[i]);
  111.           _MaxVector.push_back(index_of_Dictionary(newWord));
  112.         }
  113.       }
  114.       nodeStack.push_back(new node(index_of_Dictionary(newWord)));
  115.       wordStack.push_back(index_of_Dictionary(newWord));
  116.       node_parse(nodeStack[nodeStack.size() - 1]);
  117.     }
  118. }
  119.  
  120. void Stack::stack_eraseTop()
  121. {
  122.   vector<node*>::iterator it = nodeStack.end();
  123.   delete *it;
  124.  // nodeStack.erase(it);
  125. }
  126.  
  127. int main()
  128. {
  129.   if(!dictionary_create()) // create dictionary file, if it fails, exit
  130.   {
  131.     cout << "File not good" << endl;
  132.     return 0;
  133.   }
  134.  
  135.   // iterate through the dictionary, and for every two pairs of words, run the algorithm.
  136.   for(int i = 0; i < _Dictionary.size(); i++)
  137.     for(int x = 0; x < _Dictionary.size(); x++)
  138.       if(i != x)
  139.       {
  140.         depth_search(i, x);
  141.       }
  142.   cout << "Program finished" << endl;
  143.   cout << "Max size = " << _MaxSize << endl;
  144.  
  145.   ofstream outputFile;
  146.   outputFile.open("data.txt", ios::trunc);
  147.   outputFile << "Max size = " << _MaxSize << endl;
  148.  
  149.   for(int i = 0; i < _MaxVector.size(); i++)
  150.     outputFile << _Dictionary[_MaxVector[i]] << endl;
  151. }
  152.  
  153. void depth_search(int a_start, int a_stop)
  154. {
  155.   node* myNode = new node(a_start);
  156.  
  157.   node* targetNode = new node(a_stop);
  158.  
  159.   Stack* DepthFirst = new Stack(myNode, targetNode);
  160.   DepthFirst->DepthFirstSearch(a_start, a_stop);
  161.  
  162.   delete DepthFirst;
  163. }
  164.  
  165. bool dictionary_create()
  166. {
  167.   ifstream dictionaryFile;
  168.   dictionaryFile.open("dictionary.txt", ifstream::in); // Create and open file
  169.  
  170.   if(!dictionaryFile.good()) // return false (thus closing the program) if problem
  171.     return false;
  172.   cout << "Opened file." << endl;
  173.  
  174.   string tempWord;
  175.   while(dictionaryFile.good()) // while not end of file, add current line to dictionary
  176.   {
  177.     getline(dictionaryFile, tempWord);
  178.     _Dictionary.push_back(tempWord);
  179.   }
  180.   cout << "Read all dictionary words from file." << endl;
  181.  
  182.   dictionaryFile.close();
  183.   cout << "Closed file." << endl;
  184.  
  185.   return true;
  186. }
  187.  
  188. int index_of_alphabet(char a_char)
  189. {
  190.     int i = 0;
  191.     while(_AlphabetList[i] != a_char)
  192.       i++;
  193.     return i;
  194. }
  195.  
  196. int index_of_Dictionary(string a_word)
  197. {
  198.   find(_Dictionary.begin(), _Dictionary.end(), a_word)
  199.   vector<string>::iterator it = _Dictionary.begin();
  200.   int i = 0;
  201.  
  202.   while(*it != a_word)
  203.   {
  204.     it++;
  205.     i++;
  206.   }
  207.   return i;
  208. }
clone this paste RAW Paste Data