Challenge 77 Difficult

module main;
import std.stdio, std.algorithm, std.file, std.conv, std.datetime, std.string;

struct node {
    node*[26] letters; //a-z in alphabet, not ascii numbered order
    bool terminal; //A complete word finishes in this node
}

void branchnode(node* current, string word, uint pos) {
    if(pos == word.length) { //Finished the current word
        current.terminal = true;
        return;
    }
    if(current.letters[word[pos] - 97] == null) //If no node then add one
        current.letters[word[pos] - 97] = new node;
    branchnode(current.letters[word[pos] - 97], word, pos + 1);
}

string[] trieSearch(char[][] bog, int y, int x, string s, bool[][] block, node* current) {
    block[y][x] = true; //Block against retracing steps
    s ~= bog[y][x]; //Add square's letter to current string
    string[] words = current.terminal? [s] : []; //Complete word?

    //Test the 8 adjacent squares for the continuation of the word
    foreach(i;[[y + 1, x], [y - 1, x], [y, x + 1], [y + 1, x + 1], [y - 1, x + 1], [y, x - 1], [y - 1, x - 1], [y + 1, x - 1]])
        if(i[0] >= 0 && i[0] < bog.length && i[1] >= 0 && i[1] < bog[i[0]].length) //In bounds
            if(block[i[0]][i[1]] == false && current.letters[bog[i[0]][i[1]] - 97] != null)
                words ~= trieSearch(bog, i[0], i[1], s, block, current.letters[bog[i[0]][i[1]] - 97]);

    block[y][x] = false;
    return words;
}

void main() {
    StopWatch sw, search;
    sw.start;

    node* start = new node;
    foreach(word; read("enable1.txt").to!string.split) //Create trie structure
        branchnode(start, word, 0);

    string[] letters = "T N L E P I A C N M
                        T R E H O C F E I W
                        S C E R E D A M E A
                        A O M O G O O F I E
                        G A C M H N L E R X
                        T D E R J T F O A S
                        I T A R T I N H N T
                        R N L Y I V S C R T
                        A X E P S S H A C F
                        I U I I I A I W T T".toLower.split;

    char[][] bog;
    foreach(i;0..10) {
        ++bog.length;
        foreach(j;i * 10..i * 10 + 10)
            bog[$ - 1] ~= letters[j];
    }

    //100x100 version
    foreach(ref line;bog) {
        char[] temp;
        foreach(i;0..10)
            temp ~= line;
        line = temp;
    }

    char[][] temp = bog;
    foreach(i;0..9)
        bog ~= temp;

    string[] words;
    bool[][] block;
    foreach(line;bog)
        block ~= new bool[line.length];

    sw.peek.msecs.writeln("msecs setup time");
    search.start;

    foreach(i, line;bog)
        foreach(j, letter;line)
            if(start.letters[bog[i][j] - 97] != null)
                words ~= trieSearch(bog, i, j, "", block, start.letters[bog[i][j] - 97]);

    string[] maxwords = [""];
    foreach(word;words)
        if(word.length > maxwords[0].length)
            maxwords = [word];
        else if(word.length == maxwords[0].length)
            maxwords ~= word;

    search.peek.msecs.writeln("msecs search time");
    sw.peek.msecs.writeln("msecs total time");

    maxwords.sort.uniq.writeln;
    maxwords[0].length.writeln;
}