Re: wordladder - code improvement

2020-01-31 Thread dwdv via Digitalmars-d-learn

On 2020-01-31 09:44, mark via Digitalmars-d-learn wrote:

I can't use the levenshtien distance because although it is a better solution, 
[...]


Nah, it isn't, sorry for the noise, should have slept before sending the message, was thinking of 
hamming distance:


auto a = "abcd";
auto b = "bcda";

auto hammingDistance(string a, string b) {
return zip(a, b).count!(t => t[0] != t[1]);
}

levenshteinDistance(a, b).writeln; // => 2
hammingDistance(a, b).writeln; // => 4


main() [...] doesn't match the behaviour


There's also std.range.tee if you ever need to perform additional side-effects in a range pipeline, 
which restores the original dot printing:


write("Try ");
auto res = generate!(() => genLadder(words.dup, STEPS))
.enumerate(1)
.tee!(_ => write('.'), No.pipeOnPop) // No.pipeOnPop ensures we're not one 
dot short
.find!(a => !a[1].empty)
.front;
writeln(" ", res[0]);


genLadder() [...] is so compact.


Thinking about it, you could even eliminate the prev variable all together when using ladder.back in 
compWords.


Regarding const correctness, this article and thread might contain useful information: 
https://forum.dlang.org/thread/2735451.YHZktzbKJo@lyonel


By the way, keep the documentation improvements coming, much appreciated!



Re: wordladder - code improvement

2020-01-31 Thread mark via Digitalmars-d-learn
I forgot to mention: I know it isn't worth bothering with 
const/immutable for this tiny example. But I want to learn how to 
write large D programs, so I need to get into the right habits 
and know the right things.


Re: wordladder - code improvement

2020-01-31 Thread mark via Digitalmars-d-learn

Thanks for your implementation.

I can't use the levenshtien distance because although it is a 
better solution, I want to keep the implementation as compatible 
with those in the other languages as possible.


Your main() is much shorter than mine, but doesn't match the 
behaviour (and again I want to keep the same as the other 
implementations). Nonetheless, I didn't know about generate!()(), 
so I've learnt from yours.


Nor did I know about the StopWatch which I'm now using, plus I've 
added your static assert, and also copied your idea of making 
update() an inner function (and now only needing one parameter).


I still need to study your genLadder() more carefully to 
understand it because it is so compact.


Re: wordladder - code improvement

2020-01-30 Thread dwdv via Digitalmars-d-learn
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;
}