/*! @file boggle-sortedvector.cpp
 *  Solving Boggle using a sorted word list
 *
 *  fluffy(at)beesbuzz(dot)biz
 */

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

typedef std::vector<std::string> Dictionary;
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;

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];

    auto pfx = std::lower_bound(words.begin(), words.end(), stem);
    if (pfx == words.end() || pfx->substr(0, stem.length()) != stem) {
        visit.erase(here);
        return;
    }

    if (*pfx == stem && 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.push_back(word);
        }
    }
    std::sort(words.begin(), words.end());

    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;
}