digitalmars.D.learn - Why does indexing a string inside of a recursive call yield a
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?
May 10 2020
On 10.05.20 12:02, Adnan wrote: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?You're going from this (simplified): delt = a == b ? 0 : 1 result = x + delt to this: result = x + a == b ? 0 : 1 But that new one isn't equivalent to the old one. The new one actually means: result = (x + a == b) ? 0 : 1 You need parentheses around the ternary expression: result = x + (a == b ? 0 : 1)
May 10 2020
On Sunday, 10 May 2020 at 10:02:18 UTC, Adnan wrote: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?Wrap the ternary condition into parenthesis. editDistance(a[0 .. $ - 1], b[0 .. $ - 1]) + (a[$ - 1]== b[$ - 1] ? 0 : 1)
May 10 2020