In my naive implementation of edit-distance finder, I have to check whether the last characters of two strings match:
ulong editDistance(const string a, const string b) {
if (a.length == 0)
return b.length;
if (b.length == 0)
return a.length;
const auto delt = a[$ - 1] == b[$ - 1] ? 0 : 1;
import std.algorithm : min;
return min(
editDistance(a[0 .. $ - 1], b[0 .. $ - 1]) + delt,
editDistance(a, b[0 .. $ - 1]) + 1,
editDistance(a[0 .. $ - 1], b) + 1
);
}
This yields the expected results but if I replace delt
with its definition it always returns 1 on non-empty strings:
ulong editDistance(const string a, const string b) {
if (a.length == 0)
return b.length;
if (b.length == 0)
return a.length;
//const auto delt = a[$ - 1] == b[$ - 1] ? 0 : 1;
import std.algorithm : min;
return min(
editDistance(a[0 .. $ - 1], b[0 .. $ - 1]) + a[$ - 1] == b[$ - 1] ? 0 : 1, //delt,
editDistance(a, b[0 .. $ - 1]) + 1,
editDistance(a[0 .. $ - 1], b) + 1
);
}
Why does this result change?
The operators have different precedence from what you expect. In const auto delt = a[$ - 1] == b[$ - 1] ? 0 : 1;
there is no ambiguity, but in editDistance(a[0 .. $ - 1], b[0 .. $ - 1]) + a[$ - 1] == b[$ - 1] ? 0 : 1
, there is (seemingly).
Simplifying:
auto tmp = editDistance2(a[0..$-1], b[0..$-1]);
return min(tmp + a[$-1] == b[$-1] ? 0 : 1),
//...
);
The interesting part here is parsed as (tmp + a[$-1]) == b[$-1] ? 0 : 1
, and tmp + a[$-1]
is not equal to b[$-1]
. The solution is to wrap things in parentheses:
editDistance(a[0 .. $ - 1], b[0 .. $ - 1]) + (a[$ - 1] == b[$ - 1] ? 0 : 1)