www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Why does indexing a string inside of a recursive call yield a

reply Adnan <relay.public.adnan outlook.com> writes:
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
next sibling parent ag0aep6g <anonymous example.com> writes:
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
prev sibling parent bauss <jj_1337 live.dk> writes:
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