wordsquare_finder.cpp

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
#include <cassert>

using namespace std;

template <typename IT>
auto first_longer(IT begin, IT end)
{
    auto it (adjacent_find(begin, end,
        [](const auto &a, const auto &b) { return a.length() != b.length(); }));
    if (it != end) {
        ++it;
    }
    return it;
}

template <typename IT>
vector<string> prefix_matches(const string &prefix, IT begin, const IT end)
{
    auto pred ([prefix](const auto &s) { return 0 == s.find(prefix); });

    vector<string> ret;

    auto it = begin;
    while ((it = find_if(it, end, pred)) != end) {
        ret.push_back(*it);
        ++it;
    }

    return ret;
}

template <typename IT>
vector<vector<string>> get_word_squares(
        const vector<string> &previous,
        IT b_it, const IT e_it)
{

    string prefix;
    for (size_t i {0}; i < previous.size(); ++i) {
        prefix += previous[i][previous.size()];
    }
    const auto next_words (prefix_matches(prefix, b_it, e_it));

    if (next_words.size() == 0) {
        return {};
    }

    vector<vector<string>> ret;

    const auto len (next_words[0].length());
    for (const auto &w : next_words) {
        auto copy (previous);
        copy.push_back(w);
        if (len == 1 + prefix.length()) {
            ret.push_back(copy);
        } else {
            const auto c (w[len]);
            string next_prefix {prefix + c};
            const auto r (get_word_squares(copy, b_it, e_it));

            for (const auto &v : r) {
                ret.push_back(v);
            }
        }

    }

    return ret;
}

int main()
{
    vector<string> word_list {
        "abc",
        "ctyvg",
        "bde",
        "hexe",
        "xapb",
        "a",
        "ecbd",
        "abcde",
        "bxtuf",
        "cef",
        "exac",
        "duvzh",
        "efghi",
        "b",
    };

    sort(begin(word_list), end(word_list),
            [](const auto &a, const auto &b) { return a.length() < b.length(); });

    auto old_it (begin(word_list));
    decltype(old_it) it;
    do {
        it = first_longer(old_it, end(word_list));
        const auto len (old_it->length());
        std::cout << "======= length: " << len << "\n";

        const auto sq (get_word_squares({}, old_it, it));

        for (const auto &i : sq) {
            std::cout << "Found wordsquare:\n";
            copy(begin(i), end(i), ostream_iterator<string>(cout, "\n"));
        }
        old_it = it;
    } while (it != end(word_list));
}