Below is a program that produces a wordladder.

The algorithm is probably suboptimal, but I don't care since I've implemented the same one in Python, Rust, Go, Java, and Nim, so I find it useful for language comparison purposes.

What I'd like some feedback on is how to improve the code (keeping the algorithm the same) to make it into more idiomatic D and to take the most advantage of D's features (while keeping it as understandable as possible).

For example, in the last function, compatibleWords(), I can't help thinking that I could avoid the foreach loop.

Also I'm still not really clear on the appropriateness of const/immutable/in in function arguments. The docs seem to discourage in, and other things I've read seem to favour const. Similarly, the appropriateness of const/immutable inside functions.

// wordladder.d
import core.time: MonoTime;
import std.algorithm: any, count, filter, map, sum, until;
import std.array: array, join;
import std.conv: dtext, to;
import std.functional: not;
import std.range: assocArray, repeat, zip;
import std.random: choice;
import std.stdio: File, write, writeln;
import std.uni: isAlpha, toUpper;

enum WORDFILE = "/usr/share/hunspell/en_GB.dic";
enum WORDSIZE = 4; // Should be even

alias WordList = string[];
alias WordSet = int[string]; // key = word; value = 0

void main() {
    immutable start = MonoTime.currTime;
    auto words = getWords(WORDFILE, WORDSIZE);
    int count = 1;
    WordList ladder;
    write("Try ");
    while (true) {
        ladder = generate(words, STEPS);
        if (ladder.length != 0)
    writeln(' ', count);
    writeln(join(ladder, '\n'));
    writeln(MonoTime.currTime - start);

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

WordList generate(WordSet allWords, const int steps) {
    WordList ladder;
    auto words = allWords.dup;
    auto compatibles = allWords.dup;
    auto prev = update(ladder, words, compatibles);
    for (int i = 0; i <= steps; ++i) {
        compatibles = compatibleWords(prev, words);
        if (compatibles.length == 0)
            return [];
        prev = update(ladder, words, compatibles);
    immutable first = dtext(ladder[0]);
    immutable last = dtext(ladder[$ - 1]);
    if (any!(t => t[0] == t[1])(zip(first, last)))
        return []; // Don't accept any vertical letters in common
    return ladder;

string update(ref WordList ladder, ref WordSet words,
              const WordSet compatibles) {
    immutable word = compatibles.byKey.array.choice;
    ladder ~= word;
    return word;

// Add words that are 1 letter different to prev
WordSet compatibleWords(const string prev, const WordSet words) {
    WordSet compatibles;
    immutable prevChars = dtext(prev);
    immutable size = prevChars.length - 1;
    foreach (word; words.byKey)
        if (sum(map!(t => int(t[0] == t[1]))
                     (zip(prevChars, dtext(word)))) == size)
            compatibles[word] = 0;
    return compatibles;

Reply via email to