diff options
| -rw-r--r-- | challenge-007/paulo-custodio/c/ch-2.c | 16 | ||||
| -rw-r--r-- | challenge-007/paulo-custodio/cpp/ch-1.cpp | 37 | ||||
| -rw-r--r-- | challenge-007/paulo-custodio/cpp/ch-2.cpp | 215 |
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; +} |