/*! @file boggle-trie.cpp
 *  Solving Boggle using a naive trie
 *
 *  fluffy(at)beesbuzz(dot)biz
 */

#include <ctype.h>
#include <iostream>
#include <set>
#include <stdio.h>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

typedef std::unordered_set<std::string> Results;
typedef std::vector<char> Line;
typedef std::vector<Line> Grid;
typedef std::pair<int, int> Position;
typedef std::set<Position> Visited;

class Dictionary {
    std::unordered_map<char, Dictionary> children;
    bool complete;
public:
    Dictionary(): complete(false) {}

    void insert(const std::string& suffix) {
        if (suffix.length()) {
            Dictionary& child = children[suffix[0]];
            child.insert(suffix.substr(1));
        } else {
            complete = true;
        }
    }

    const Dictionary* find(const std::string& suffix) const {
        if (suffix.length()) {
            auto child = children.find(suffix[0]);
            if (child != children.end()) {
                return child->second.find(suffix.substr(1));
            }
            return nullptr;
        }
        return this;
    }

    bool is_word() const {
        return complete;
    }
};

void search(const Grid& grid,
            const Dictionary& words,
            Results& found,
            unsigned int x, unsigned int y,
            std::string stem,
            Visited& visit)
{
    //! Visit this square
    Position here(x, y);
    visit.insert(here);
    stem += grid[y][x];

    const Dictionary* pfx = words.find(stem);
    if (!pfx) {
        visit.erase(here);
        return;
    }
    if (pfx->is_word() && stem.length() >= 3) {
        found.insert(stem);
    }

    for (int a = -1; a <= 1; a++) {
        unsigned int xp = x + a;
        for (int b = -1; b <= 1; b++) {
            unsigned int yp = y + b;
            if (yp < grid.size()
                && xp < grid[yp].size()
                && visit.find(std::make_pair(xp, yp)) == visit.end()) {
                search(grid, words, found, xp, yp, stem, visit);
                //! Special case for q - also check out qu
                if (grid[y][x] == 'q') {
                    search(grid, words, found, xp, yp, stem + 'u', visit);
                }
            }
        }
    }

    visit.erase(here);
}

int main(int argc, char* argv[])
{
    const char* dict = "/usr/share/dict/words";
    if (argc > 1) {
        dict = argv[1];
    }

    FILE* fp = fopen(dict, "r");
    if (!fp) {
        perror(dict);
        return 1;
    }

    Dictionary words;

    char buf[1024];
    while (fgets(buf, 1024, fp)) {
        bool valid = true;
        std::string word;
        for (char* c = buf; *c; ++c) {
            if (islower(*c)) {
                word += *c;
            } else if (!isspace(*c)) {
                valid = false;
            }
        }
        if (valid && word.length()) {
            words.insert(word);
        }
    }

    fclose(fp);

    if (argc > 2) {
        fp = fopen(argv[2], "r");
        if (!fp) {
            perror(argv[2]);
        }
    } else {
        fp = stdin;
    }

    Grid grid;
    while (fgets(buf, 1024, fp)) {
        Line line;
        for (char* c = buf; *c; ++c) {
            if (isalpha(*c)) {
                line.push_back(*c);
            }
        }
        if (line.size()) {
            grid.push_back(line);
        }
    }

    Results found;
    Visited visit;
    for (unsigned int y = 0; y < grid.size(); y++) {
        for (unsigned int x = 0; x < grid[y].size(); x++) {
            search(grid, words, found, x, y, "", visit);
        }
    }

    for (auto result : found) {
        std::cout << result.length() << ' ' << result << std::endl;
    }

    return 0;
}