From one noob to another: Not much of a difference, but levenshteinDistance seems to be a good fit here. About as fast as your solution, slightly lower memory usage. byCodeUnit/byChar might shave off a few more ms.

For small scripts like these I'm usually not even bothering with const correctness and selective imports. There's also import std; but that might lead to ambiguous imports.

---

import std.algorithm, std.array, std.conv, std.datetime.stopwatch,
       std.functional, std.random, std.range, std.stdio, std.uni;

enum WORDFILE = "/usr/share/hunspell/en_GB.dic";
enum WORDSIZE = 4;
enum STEPS = WORDSIZE;

// could be verified at compile-time
static assert(WORDSIZE % 2 == 0, "WORDSIZE should be even");

alias WordList = string[];
alias WordSet = bool[string];

void main() {
    auto sw = StopWatch(AutoStart.yes);
    auto words = getWords(WORDFILE, WORDSIZE);
    // would be slicker with proper destructuring support
    auto res = generate!(() => genLadder(words.dup, STEPS))
        .enumerate(1)
        .find!(a => !a[1].empty)
        .front;
    writeln("tries: ", res[0]);
    res[1].each!writeln;
    writeln(sw.peek); // or sw.peek.total!"msecs"
}

WordSet getWords(string filename, uint wordsize) {
    return File(filename).byLine
        .map!(line => line.until!(not!isAlpha))
        .filter!(word => word.count == wordsize)
        .map!(word => word.to!string.toUpper)
        .assocArray(true.repeat);
}

WordList genLadder(WordSet words, uint steps) {
    WordList ladder;

    string update(WordList comps) {
        ladder ~= comps.choice;
        words.remove(ladder.back);
        return ladder.back;
    }
    WordList compWords(string prev) {
        return words.byKey.filter!(word => levenshteinDistance(word, prev) == 
1).array;
    }

    auto prev = update(words.byKey.array);
    foreach (comps; generate!(() => compWords(prev)).take(steps + 1)) {
        if (comps.empty) return comps;
        prev = update(comps);
    }

    if (levenshteinDistance(ladder.front, ladder.back) < WORDSIZE)
        return [];
    return ladder;
}

Reply via email to