wordladder - code improvement

mark mark at qtrac.eu
Thu Jan 30 13:05:29 UTC 2020


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
enum STEPS = WORDSIZE;

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) {
	write('.');
	ladder = generate(words, STEPS);
	if (ladder.length != 0)
	    break;
	++count;
     }
     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 => word.to!string.toUpper)
	.assocArray(0.repeat);
}

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;
     words.remove(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;
}


More information about the Digitalmars-d-learn mailing list