diff options
| author | Gustav Sörnäs <gustav@sornas.net> | 2020-09-11 00:20:38 +0200 |
|---|---|---|
| committer | Gustav Sörnäs <gustav@sornas.net> | 2020-09-11 09:19:15 +0200 |
| commit | f906c5d984c5f39f7b9d152bb57fba8459914e22 (patch) | |
| tree | eaa5803c52381d4a707395ff447365cd17109174 /labb2/wordchain/src/wordchain.cpp | |
| parent | bc5ec9a8a0027d6c6801fdc48a065a54a97856dc (diff) | |
| download | tddd86-f906c5d984c5f39f7b9d152bb57fba8459914e22.tar.gz | |
wip L2 and L1 const
Diffstat (limited to 'labb2/wordchain/src/wordchain.cpp')
| -rw-r--r-- | labb2/wordchain/src/wordchain.cpp | 100 |
1 files changed, 100 insertions, 0 deletions
diff --git a/labb2/wordchain/src/wordchain.cpp b/labb2/wordchain/src/wordchain.cpp new file mode 100644 index 0000000..5eb44c6 --- /dev/null +++ b/labb2/wordchain/src/wordchain.cpp @@ -0,0 +1,100 @@ +#include <forward_list>
+#include <fstream>
+#include <iostream>
+#include <queue>
+#include <set>
+#include <stack>
+#include <string>
+
+using namespace std;
+
+const string ALPHABET = "abcdefghijklmnopqrstuvwxyz";
+
+void openDictionary(set<string> &words, string path) {
+ ifstream input;
+ input.open(path);
+ string word;
+ while (input >> word) {
+ words.insert(word);
+ }
+ input.close();
+}
+
+/*
+ * Populates `neighbours` with all valid word neighbours from `words`.
+ */
+void getValidNeighbours(forward_list<string> &neighbours, string &word, set<string> &words) {
+ for (int i = 0; i < word.length(); i++) {
+ string new_word = word;
+ char cur_c = word[i];
+ for (char new_c: ALPHABET) {
+ if (new_c != cur_c) {
+ new_word[i] = new_c;
+ if (words.count(new_word)) {
+ neighbours.push_front(new_word);
+ }
+ }
+ }
+ }
+}
+
+void wordchain(stack<string> &chain, string w1, string w2, set<string> &words) {
+ stack<string> firstChain;
+ firstChain.push(w1);
+
+ queue<stack<string>> chains;
+ chains.push(firstChain);
+
+ set<string> seenWords;
+ while (!chains.empty()) {
+ stack<string> curChain = chains.front();
+ chains.pop();
+ forward_list<string> validNeighbours;
+ getValidNeighbours(validNeighbours, curChain.top(), words);
+ for (string &w: validNeighbours) {
+ if (w == w2) {
+ // done
+ chain.push(w);
+ while (!curChain.empty()) {
+ chain.push(curChain.top());
+ curChain.pop();
+ }
+ return;
+ }
+ if (seenWords.count(w) == 0) {
+ seenWords.insert(w);
+ stack<string> newChain = curChain;
+ newChain.push(w);
+ chains.push(newChain);
+ }
+ }
+ }
+}
+
+int main() {
+ cout << "Welcome to TDDD86 Word Chain." << endl;
+ cout << "If you give me two English words, I will transform the" << endl;
+ cout << "first into the second by changing one letter at a time." << endl;
+ cout << endl;
+
+ cout << "Please type two words: ";
+
+ string word1, word2;
+ cin >> word1 >> word2;
+
+ cout << "Reading valid words..." << endl;
+ set<string> words;
+ openDictionary(words, "res/dictionary.txt");
+ cout << "Done." << endl;
+
+ cout << "Searching..." << endl;
+ stack<string> chain;
+ wordchain(chain, word1, word2, words);
+ cout << "Done." << endl;
+
+ while (!chain.empty()) {
+ cout << chain.top() << " ";
+ chain.pop();
+ }
+ cout << endl;
+}
|