Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream> // For cout
- #include <vector> // For Vector
- #include <string> // for string
- #include <fstream> // for file reading
- #include <algorithm>// for binary_search fun
- #include <sstream> // for string streams
- using namespace std;
- // Enumerators
- enum ALPHABET {a, b, c, d, e, f, g, h, i, j, k, l, m,
- n, o, p, q, r, s, t, u, v, w, x, y, z};
- // Global Variable Declarations
- vector<string> _Dictionary;
- char _AlphabetList[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
- 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
- int _MaxSize = 0;
- vector<int> _MaxVector;
- // Node Structure
- struct node
- {
- int word;
- node* next;
- node* last;
- node(int a_word)
- {
- word = a_word;
- }
- };
- // Function Declarations
- bool dictionary_create();
- bool word_exists(vector<string>::iterator a_begin, vector<string>::iterator a_end, string a_word)
- { return binary_search(a_begin, a_end, a_word); };
- void depth_search(int a_start, int a_stop);
- int index_of_alphabet(char a_char);
- int index_of_Dictionary(string a_word);
- class Stack
- {
- public:
- // Constructor and destructor's
- Stack(node* a_top, node* a_target);
- ~Stack();
- // Member Functions
- void DepthFirstSearch(int a_start, int a_stop);
- void node_parse(node* a_node);
- void stack_addNode(node* a_node) { nodeStack.push_back(a_node); wordStack.push_back(a_node->word); };
- void stack_eraseTop();
- vector<node*> nodeStack;
- vector<int> wordStack;
- private:
- node* root;
- node* target;
- };
- Stack::Stack(node* a_root, node* a_target)
- {
- root = a_root;
- target = a_target;
- nodeStack.push_back(root);
- wordStack.push_back(root->word);
- }
- Stack::~Stack()
- {
- delete root;
- delete target;
- }
- void Stack::DepthFirstSearch(int a_start, int a_stop)
- {
- node_parse(root);
- // system("pause");
- }
- void Stack::node_parse(node* a_node)
- {
- for(int curChar = 0; curChar < 4; curChar = curChar + 1)
- for(int curLetter = index_of_alphabet(_Dictionary[root->word][0]) + 1; curLetter != 26; curLetter = curLetter + 1)
- {
- string newWord = _Dictionary[a_node->word];
- newWord[curChar] = _AlphabetList[curLetter];
- // Get rid of invalid or already existing words in chain, or if it's itself
- if(!word_exists(_Dictionary.begin(), _Dictionary.end(), newWord)) /// TODO: Replace needless functions with std::find(iterator, iterator, value);
- continue;
- if(find(wordStack.begin(), wordStack.end(), index_of_Dictionary(newWord)) != wordStack.end()) // if found
- continue;
- if(newWord == _Dictionary[a_node->word])
- continue;
- // check for completion
- if(newWord == _Dictionary[target->word])
- {
- cout << "Solution found for " << _Dictionary[root->word] << " to " << _Dictionary[target->word] << " Size = " << wordStack.size() + 1 << endl;
- if(wordStack.size() + 1 > _MaxSize)
- {
- _MaxSize = wordStack.size() + 1;
- _MaxVector.clear();
- for(int i = 0; i < wordStack.size(); i++)
- _MaxVector.push_back(wordStack[i]);
- _MaxVector.push_back(index_of_Dictionary(newWord));
- }
- }
- nodeStack.push_back(new node(index_of_Dictionary(newWord)));
- wordStack.push_back(index_of_Dictionary(newWord));
- node_parse(nodeStack[nodeStack.size() - 1]);
- }
- }
- void Stack::stack_eraseTop()
- {
- vector<node*>::iterator it = nodeStack.end();
- delete *it;
- // nodeStack.erase(it);
- }
- int main()
- {
- if(!dictionary_create()) // create dictionary file, if it fails, exit
- {
- cout << "File not good" << endl;
- return 0;
- }
- // iterate through the dictionary, and for every two pairs of words, run the algorithm.
- for(int i = 0; i < _Dictionary.size(); i++)
- for(int x = 0; x < _Dictionary.size(); x++)
- if(i != x)
- {
- depth_search(i, x);
- }
- cout << "Program finished" << endl;
- cout << "Max size = " << _MaxSize << endl;
- ofstream outputFile;
- outputFile.open("data.txt", ios::trunc);
- outputFile << "Max size = " << _MaxSize << endl;
- for(int i = 0; i < _MaxVector.size(); i++)
- outputFile << _Dictionary[_MaxVector[i]] << endl;
- }
- void depth_search(int a_start, int a_stop)
- {
- node* myNode = new node(a_start);
- node* targetNode = new node(a_stop);
- Stack* DepthFirst = new Stack(myNode, targetNode);
- DepthFirst->DepthFirstSearch(a_start, a_stop);
- delete DepthFirst;
- }
- bool dictionary_create()
- {
- ifstream dictionaryFile;
- dictionaryFile.open("dictionary.txt", ifstream::in); // Create and open file
- if(!dictionaryFile.good()) // return false (thus closing the program) if problem
- return false;
- cout << "Opened file." << endl;
- string tempWord;
- while(dictionaryFile.good()) // while not end of file, add current line to dictionary
- {
- getline(dictionaryFile, tempWord);
- _Dictionary.push_back(tempWord);
- }
- cout << "Read all dictionary words from file." << endl;
- dictionaryFile.close();
- cout << "Closed file." << endl;
- return true;
- }
- int index_of_alphabet(char a_char)
- {
- int i = 0;
- while(_AlphabetList[i] != a_char)
- i++;
- return i;
- }
- int index_of_Dictionary(string a_word)
- {
- find(_Dictionary.begin(), _Dictionary.end(), a_word)
- vector<string>::iterator it = _Dictionary.begin();
- int i = 0;
- while(*it != a_word)
- {
- it++;
- i++;
- }
- return i;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement