From f906c5d984c5f39f7b9d152bb57fba8459914e22 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= <gustav@sornas.net>
Date: Fri, 11 Sep 2020 00:20:38 +0200
Subject: wip L2 and L1 const

---
 labb2/wordchain/src/wordchain.cpp | 100 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 100 insertions(+)
 create mode 100644 labb2/wordchain/src/wordchain.cpp

(limited to 'labb2/wordchain/src/wordchain.cpp')

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;
+}
-- 
cgit v1.2.1