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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
|
/*
Challenge 007
Challenge #2
Word Ladder
A word ladder is a sequence of words [w0, w1, �, wn] such that each word wi
in the sequence is obtained by changing a single character in the word wi-1.
All words in the ladder must be valid English words.
Given two input words and a file that contains an ordered word list,
implement a routine (e.g., find_shortest_ladder(word1, word2, wordlist))
that finds the shortest ladder between the two input words. For example,
for the words cold and warm, the routine might return:
("cold", "cord", "core", "care", "card", "ward", "warm")
However, there�s a shortest ladder:
(�cold�, �cord�, �card�, �ward�, �warm�).
Givens:
All words in the list have the same length.
All words contain only lowercase alphabetical characters.
There are no duplicates in the word list.
The input words aren�t empty and aren�t equal but they have the same length
as any word in the word list.
Requirements:
The routine must return a list of the words in the ladder if it exists.
Otherwise, it returns an empty list.
If any of the input words is the wrong length (i.e., its length is different
to a random from the word list) or isn�t in the word list, return an empty
list.
*/
#include <algorithm>
#include <cctype>
#include <climits>
#include <deque>
#include <fstream>
#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;
class Path {
public:
void push_back(const string& word) {
if (word_set.find(word) != word_set.end()) {
cerr << "Word " << word << " already in list" << endl;
exit(EXIT_FAILURE);
}
word_list.push_back(word);
word_set.insert(word);
}
bool contains(const string& word) const {
return word_set.find(word) != word_set.end();
}
string front() const { return word_list.front(); }
string back() const { return word_list.back(); }
vector<string>::iterator begin() { return word_list.begin(); }
vector<string>::iterator end() { return word_list.end(); }
vector<string>::const_iterator cbegin() const { return word_list.cbegin(); }
vector<string>::const_iterator cend() const { return word_list.cend(); }
void clear() {
word_list.clear();
word_set.clear();
}
void sort() {
::sort(word_list.begin(), word_list.end());
}
friend ostream& operator<<(ostream& os, const Path& path) {
os << "(";
string separator = "";
for (auto& word : path.word_list) {
os << separator << '"' << word << '"';
separator = ", ";
}
os << ")";
return os;
}
private:
vector<string> word_list;
set<string> word_set;
};
Path all_words;
bool word_is_lower(const string& word) {
for (size_t i = 0; i < word.size(); i++)
if (word[i] < 'a' || word[i] > 'z')
return false;
return true;
}
int word_diff(const string& word1, const string& word2) {
int diff = 0;
for (size_t i = 0; i < word1.size(); i++)
if (word1[i] != word2[i])
diff++;
return diff;
}
vector<string> next_words(const Path& path) {
vector<string> ret;
string last_word = path.back();
for (auto& word : all_words) {
if (word_diff(last_word, word) == 1)
if (!path.contains(word))
ret.push_back(word);
}
return ret;
}
// read all words with the given length
void read_words(int len) {
all_words.clear();
ifstream ifs("words.txt");
if (!ifs.is_open()) {
cerr << "cannot open words.txt" << endl;
exit(EXIT_FAILURE);
}
string word;
while (getline(ifs, word)) {
if (word.size() == len && word_is_lower(word))
all_words.push_back(word);
}
all_words.sort();
}
// find shortest ladder
Path find_shortest_ladder(const string& word1, const string& word2) {
// build initial path
Path path;
path.push_back(word1);
// build initial queue
deque<Path> queue;
queue.push_back(path);
while (!queue.empty()) {
// current path being examined
path = queue.front();
queue.pop_front();
// check if finished
if (path.back() == word2)
return path;
// find next step
auto words = next_words(path);
for (auto& word : words) {
Path new_path = path;
new_path.push_back(word);
queue.push_back(new_path);
}
}
// not found
path.clear();
return path;
}
int main(int argc, char* argv[]) {
if (argc != 3) {
cerr << "Usage: ch-2 word1 word2" << endl;
return EXIT_FAILURE;
}
string word1 = argv[1];
string word2 = argv[2];
if (word1.size() != word2.size()) {
cerr << "words must have the same length" << endl;
return EXIT_FAILURE;
}
if (word1 == word2) {
cerr << "words must be different" << endl;
return EXIT_FAILURE;
}
if (!word_is_lower(word1) || !word_is_lower(word2)) {
cerr << "words must have lower case letters only" << endl;
return EXIT_FAILURE;
}
// reads to all_words with same size
read_words(word1.size());
if (!all_words.contains(word1) ||!all_words.contains(word2)) {
cerr << "words not found in dictionary" << endl;
return EXIT_FAILURE;
}
// find sortest ladder
Path path = find_shortest_ladder(word1, word2);
cout << path << endl;
return EXIT_SUCCESS;
}
|
