Add C++ solution to challenge 007

3 files changed, 252 insertions, 16 deletions

diff --git a/challenge-007/paulo-custodio/c/ch-2.c b/challenge-007/paulo-custodio/c/ch-2.c
index 14782e2fd4..3da200001b 100644
--- a/challenge-007/paulo-custodio/c/ch-2.c
+++ b/challenge-007/paulo-custodio/c/ch-2.c
@@ -45,10 +45,8 @@ list.
 #include <stdbool.h>
 #include <stdio.h>
 #include <stdlib.h>
-#include <stdlib.h>
 
 #define MAXLINE         1024
-#define MAX_LADDER_SIZE 20
 
 // list of words
 typedef struct word_t {
@@ -128,10 +126,6 @@ void word_list_free(word_t** phead) {
     }
 }
 
-int word_list_size(word_t** phead) {
-    return HASH_COUNT(*phead);
-}
-
 const char* word_list_last_word(word_t** phead) {
     word_t* elem;
     word_t* tmp;
@@ -177,12 +171,6 @@ void word_list_print(word_t** phead) {
     printf(")");
 }
 
-void word_list_print_line(word_t** phead, const char* name) {
-    printf("%s : ", name);
-    word_list_print(phead);
-    printf("\n");
-}
-
 // queue of paths
 word_t* dequeue(queue_t** phead) {
     queue_t* elem = *phead;
@@ -232,10 +220,6 @@ word_t* find_shortest_ladder(const char* word1, const char* word2) {
     while (queue) {
         path = dequeue(&queue);         // current path being examined
 
-#ifdef DEBUG
-        word_list_print_line(&path, "path");
-#endif
-
         // check if finished
         const char* last_word = word_list_last_word(&path);
         if (strcmp(word2, last_word) == 0) {    // found shortest path
diff --git a/challenge-007/paulo-custodio/cpp/ch-1.cpp b/challenge-007/paulo-custodio/cpp/ch-1.cpp
new file mode 100644
index 0000000000..ce36d83869
--- /dev/null
+++ b/challenge-007/paulo-custodio/cpp/ch-1.cpp
@@ -0,0 +1,37 @@
+/*
+Challenge 007
+
+Challenge #1
+Print all the niven numbers from 0 to 50 inclusive, each on their own line.
+A niven number is a non-negative number that is divisible by the sum of its
+digits.
+*/
+
+#include <cassert>
+#include <iostream>
+using namespace std;
+
+bool is_niven(int n) {
+    assert(n > 0);
+    int sum = 0;
+    int rem = n;
+    while (rem > 0) {
+        int digit = rem % 10;
+        rem /= 10;
+        sum += digit;
+    }
+    if (n % sum == 0)
+        return true;
+    else
+        return false;
+}
+
+int main(int argc, char* argv[]) {
+    int max = 50;
+    if (argc == 2) max = atoi(argv[1]);
+    if (max < 1) return EXIT_FAILURE;
+    for (int n = 1; n <= max; n++)
+        if (is_niven(n))
+            cout << n << endl;
+    return EXIT_SUCCESS;
+}
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;
+}