word chain solver

wordchain.cpp

// g++ -g -Wall -Werror -Wextra -pedantic -pedantic-errors -std=c++11 -g -O2 -c wordchain.cpp
// g++ -o wordchain wordchain.o
// example: wordchain cause north

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>
#include <memory>

static const std::string ALPHA = "abcdefghijklmnopqrstuvwxyz";
static const size_t ALPHA_LEN = ALPHA.length();

// a naive word distance
int dist(const std::string &a, const std::string &b) {
    size_t l = a.length();
    if (l != b.length()) return INT_MAX;
    int d = 0;
    for (size_t i = 0; i < l; i++) {
        if (a[i] != b[i]) d++;
    }
    return d;
}

bool in_dict(const std::vector<std::string> &words,const std::string &w) {
    return std::binary_search(words.begin(),words.end(),w);
}

bool in_vec(const std::vector<std::string> &chain,const std::string &w) {
    for (auto& c:chain) if (c == w) return true;
    return false;
}

// replace letters to find new candidates. at this point we only insist that they be words
std::vector<std::string> chain_candidates(const std::string &src,
                                          const std::string &dest,
                                          const std::vector<std::string> &words) {
    std::vector<std::string> candidates;
    size_t l = src.length();
    for (size_t i = 0; i < l; i++) {
        if (src[i] != dest [i]) {
            for (size_t j = 0; j < ALPHA_LEN; j++) {
                std::string c{src};
                c.replace(i,1,std::string{ALPHA[j]});
                if (in_dict(words,c)) candidates.push_back(c);
            }
        }
    }
    return candidates;
}

// given a list of candidate words that may form the next link in the chain,
// assert that they actually are new (not seen before), and that they 
// represent progress (distance to dest is lower
// than dest_dist, the distance to dest for the last word in the chain),
// and then sort them by this distance, so we can choose candidates that
// have the shortest distance to dest first.
std::vector<std::string> viable(const std::vector<std::string> &candidates,
                                const std::string &dest,
                                size_t dest_dist,
                                const std::vector<std::string> &chain,
                                const std::vector<std::string> &seen) {
    std::vector<std::pair<int,std::string>> pv;
    for (auto& c:candidates) {
        size_t d = dist(c,dest);
        if ((!in_vec(chain,c)) && (!in_vec(seen,c)) && (d <= dest_dist)) {
            pv.push_back(std::pair<int,std::string>{d,c});
        }
    }
    std::vector<std::string> v;
    // no candidates, so return empty vector
    if (pv.empty()) return v;
    // reverse (descending) sort so lowest (closest) distance is at the end 
    std::sort(pv.begin(),pv.end(),
              [](const std::pair<int,std::string> &a,const std::pair<int,std::string> &b) { 
                  return a.first > b.first; });
    for (auto& a: pv) {
        v.push_back(a.second);
    }
    return v;
}

// try to make a word chain from src to dest.
// algorithm: maintain two arrays, chain and candidates.
// the chain will represent the progress so far
// the candidates will represent those words which progress from the end of chain
// to the destination, meaning they are "closer" by chars (our dist function)
// to the destination string. when candidates are considered, they are added to 
// the end of the chain. if a candidate reaches the destination string, we are done.
// if a candidate does not make progress, it is removed from the candidates list 
// and the chain. this is loosely described as a depth-first-search.
std::vector<std::string> make_chain(const std::string &src,
                                    const std::string &dest,
                                    const std::vector<std::string> &words) {
    std::vector<std::string> candidates{src};
    std::vector<std::string> seen{src};
    std::vector<std::string> chain{};

    while (!candidates.empty()) {
        auto b = candidates.back();
        chain.push_back(b);
        if (b == dest) return chain;
        candidates.pop_back();
        std::vector<std::string> cs = viable(chain_candidates(b,dest,words),
                                             dest,
                                             dist(b,dest),
                                             candidates,
                                             seen);
        if (cs.empty()) {
            // no viable candidates could be found to move forward in the chain. 
            // so we should get rid of the current last link, it is a dead end
            chain.pop_back();
        } else {
            // we have some candidates. we received them back from the viable
            // func in descending order of distance to dest, so the last word
            // in the candidates vector is the one we want to try next
            for (auto& c:cs) {
                candidates.push_back(c);
                seen.push_back(c);
            }
        }
    }
    return std::vector<std::string>{}; // no chain!
}

int main(int argc,char **argv) {
    if (argc != 3) {
        std::cerr << "use: wordchain src dest" << std::endl;
        std::exit(1);
    }

    // lowercase both args
    std::string src{argv[1]};
    std::string dest{argv[2]};
    std::transform(src.begin(), src.end(), src.begin(),::tolower);
    std::transform(dest.begin(), dest.end(), dest.begin(),::tolower);    

    // read in the local dictionary
    const std::string dict_fn{"/etc/dictionaries-common/words"};
    std::ios_base::sync_with_stdio(false);
    std::ifstream dict(dict_fn);
    if (!dict.is_open()) {
        std::cerr << "cannot open dict file" << std::endl;
        std::exit(1);
    }
    std::string line;
    std::vector<std::string> words;
    while (dict >> line) {
        words.push_back(line);
    }
    dict.close();

    // must be the same length
    if (src.length() != dest.length()) {
        std::cerr << src << " and " << dest << " must be the same length" << std::endl;
        std::exit(1);
    }
    if (!(in_dict(words,src) && in_dict(words,dest))) {
        std::cerr << src << " and " << dest << " must be in the dictionary" << std::endl;
        std::exit(1);
    }

    // try to make the chain
    std::vector<std::string> ch = make_chain(src,dest,words);
    if (ch.empty()) {
        std::cout << "no chain" << std::endl;
    } else {
        for (auto &c:ch) {
            std::cout << c << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}