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