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;

// 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))
        .find!(a => !a[1].empty)
    writeln("tries: ", res[0]);
    writeln(sw.peek); // or!"msecs"

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

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

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

    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