#include "word_ladder.h"

using word_t = std::shared_ptr<std::string>;
using words_t = std::vector<word_t>;

namespace {

// Returns valid words which neighbour current by one letter.
// Performs caching on neighbours so future lookups of the same arguments are
// not computed unnecessarily.
auto get_neighbours(const std::string& current, const std::string& from,
                    const std::unordered_set<std::string>& readable,
                    std::unordered_map<std::string, words_t>& neighbours)
    -> std::unordered_map<std::string, words_t>::iterator {
    if (const auto it = neighbours.find(current); it != std::end(neighbours)) {
        return it;
    }

    words_t lookup_neighbours{};
    for (std::size_t pos = 0; pos < std::size(from); ++pos) {
        std::string potential = current;

        for (char c = 'a'; c <= 'z'; ++c) {
            potential[pos] = c;

            if (!readable.contains(potential)) {
                continue;
            }

            lookup_neighbours.emplace_back(
                std::make_shared<std::string>(potential));
        }
    }
    return neighbours.emplace(current, std::move(lookup_neighbours)).first;
}

// Performs a breadth first search using only words found in lexicon. Words are
// considered connected if they differ by one character only.
auto do_bfs(const std::string& to, const std::string& from,
            const std::unordered_set<std::string>& lexicon)
    -> std::vector<std::vector<std::string>> {
    std::vector<std::vector<std::string>> results{};

    // Optimisation where we copy strings from the lexicon into our own set. By
    // reducing the size of the hashmap to words of only size from/to, we get
    // faster lookup. Also we can remove words and avoid unnecessary neighbour
    // calculations later by ignoring them (treating them as if they did not
    // exist in the lexicon entirely avoids a second hashing).
    std::unordered_set<std::string> readable = std::accumulate(
        std::begin(lexicon), std::end(lexicon),
        std::unordered_set<std::string>{}, [&](auto&& l, const auto& word) {
            if (std::size(word) == std::size(to)) {
                l.emplace(word);
            }
            return l;
        });

    std::unordered_map<std::string, words_t> neighbours{};

    std::queue<words_t> paths_queue{
        {words_t{std::make_shared<std::string>(from)}}};

    while (!paths_queue.empty()) {
        const words_t path = paths_queue.front();
        const std::string& current = *path.back();
        paths_queue.pop();

        readable.erase(current);

        if (const auto it = std::begin(results);
            it != std::end(results) && std::size(path) >= std::size(*it)) {
            continue;
        }

        const auto lookup = ::get_neighbours(current, to, readable, neighbours);

        for (const auto& neighbour : lookup->second) {
            const auto concatenate_path = [&]() {
                words_t new_path{};
                // Vector optimisation where we allocate exactly as needed,
                // reducing syscalls asking for more memory.
                new_path.reserve(std::size(path) + 1);
                std::copy(std::begin(path), std::end(path),
                          std::back_inserter(new_path));
                new_path.emplace_back(neighbour);
                return new_path;
            };

            if (*neighbour == to) {
                const std::vector<word_t> result_path = concatenate_path();
                results.emplace_back(std::accumulate(
                    std::rbegin(result_path), std::rend(result_path),
                    std::vector<std::string>{}, [](auto&& v, const auto& ptr) {
                        v.emplace_back(*ptr);
                        return v;
                    }));
                continue;
            }

            if (!readable.contains(*neighbour)) {
                continue;
            }

            paths_queue.push(concatenate_path());
        }
    }

    return results;
}

}  // namespace

namespace word_ladder {

auto read_lexicon(const std::string& path) -> std::unordered_set<std::string> {
    std::ifstream in{path};
    if (!in.is_open()) {
        throw std::runtime_error("unable to open file '" + path + "'");
    }

    std::unordered_set<std::string> words{};

    std::stringstream contents{std::string{std::istreambuf_iterator<char>{in},
                                           std::istreambuf_iterator<char>{}}};
    for (std::string line; std::getline(contents, line);) {
        if (line.empty()) {
            continue;
        }

        words.emplace(std::move(line));
    }

    return words;
}

auto generate(const std::string& from, const std::string& to,
              const std::unordered_set<std::string>& lexicon)
    -> std::vector<std::vector<std::string>> {
    std::vector<std::vector<std::string>> results = ::do_bfs(from, to, lexicon);

    // Sorts results lexicographically (avoiding large string concatenation).
    std::sort(std::begin(results), std::end(results),
              [](const auto& a, const auto& b) {
                  for (std::size_t i = 0; i < std::size(a); ++i) {
                      const auto result = a[i].compare(b[i]);
                      if (result == 0) {
                          continue;
                      }
                      return result < 0;
                  }
                  return false;
              });

    return results;
}

}  // namespace word_ladder