1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
#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, const string &path) {
ifstream input;
input.open(path);
string word;
while (input >> word) {
words.insert(word);
}
input.close();
}
/*
* Populate `neighbours` with all valid word neighbours
* (words with only one char differing) from `words`.
*/
void getValidNeighbours(forward_list<string> &neighbours, const string &word, const 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);
}
}
}
}
}
/*
* Find the shortest word chain between `w1` and `w2`
* and store it in `chain`.
*/
void wordchain(stack<string> &chain, const string &w1, const string &w2, const 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;
}
|
