1 files changed, 215 insertions, 0 deletions
diff --git a/challenge-007/paulo-custodio/cpp/ch-2.cpp b/challenge-007/paulo-custodio/cpp/ch-2.cpp
new file mode 100644
index 0000000000..000b0ec258
--- /dev/null
+++ b/challenge-007/paulo-custodio/cpp/ch-2.cpp
@@ -0,0 +1,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;
+}