From 2a0007c6def4cfb4949ff6d5d84ccdaba3c0ec26 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= <gusso230@student.liu.se>
Date: Sun, 16 Aug 2020 03:50:51 +0200
Subject: initial lab2 wordchain

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

(limited to 'lab2/wordchain/src')

diff --git a/lab2/wordchain/src/wordchain.cpp b/lab2/wordchain/src/wordchain.cpp
new file mode 100644
index 0000000..7463697
--- /dev/null
+++ b/lab2/wordchain/src/wordchain.cpp
@@ -0,0 +1,96 @@
+#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();
+}
+
+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) != 0) {
+                    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) {
+                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