Aha, Evaluation Order Matters!

As a professional C++ developer, most people won’t trouble themselves writing something stupid like f(++i, i, i++). This is because the order of evaluation of arguments in a function call is unspecified. Although I am aware of this rule, I’m trapped today, when writing a recursion algorithm.

The problem stems from leetcode #120. You’re given a triangle of numbers. Find a path from top to bottom so that the sum of the numbers on this path is minimal.

E.g., given the following triangle:

[
      [2],
     [3, 4],
    [6, 5, 7],
   [4, 1, 8, 3]
] 

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Apparently, the way to get this right is dynamic programming, because there are subproblems(subtriangles) that are calculated over and over again.

So the first try is to use a top-down approach with memo. Here is the code. “min_aux” is straight-forward, for each node that hasn’t been calculated, it recursively checks the only two branches and picks the smaller one.

int min_aux(vector<vector<int> > &triangle,
            vector<vector<int> > &lookup,
            int row,
            int col)
{
   if (lookup[row][col] != INT_MIN)
   {
      return lookup[row][col];
   }

   int c = 0;
   if (row == triangle.size() - 1)
   {
      c = triangle[row][col];
   }
   else
   {
      c = min(min_aux(triangle, lookup, row + 1, col),
              min_aux(triangle, lookup, row + 1, col + 1))
              + triangle[row][col];
   }

   lookup[row][col] = c;
   return c;
}

// this is the interface required by the online judge
int minimumTotal(vector<vector<int> > &triangle)
{
   vector<vector<int> > lookup = triangle;
   for (size_t i = 0; i < lookup.size(); ++i)
   {
      for (size_t j = 0; j < lookup[i].size(); ++j)
      {
         lookup[i][j] = INT_MIN;
      }
   }
   return min_aux(triangle, lookup, 0, 0);
}

It actually passed the judge, with a run time of 17ms. As seen, there’s still room to improve.

As we look at “lookup”, it is as large as the input. But if we can arrange our recursion path to always go left-down first, we only need one slot each row. Why? Let’s say we allocate and save two slots per row, which are LEFT, RIGHT respectively. If LEFT hasn’t been revisited, there is no way RIGHT is visited. Otherwise, it’d break our rule that left-down branch is picked prior to right-down branch; Let’s look at it the other way. If RIGHT is revisited, do we need to retain the value of LEFT? No, the same argument applies. So this means that we can have a linear lookup table of size #n, the numbers of rows of the triangle. Good!

Here is the code:

int min_aux(vector<vector<int> > &triangle,
            vector<int> &lookup,
            int row,
            int col,
            bool left)
{
   int c = 0;
   // 2nd visit, must be left branch. Clear it.
   if (lookup[row] != INT_MIN)
   {
      c = lookup[row];
      lookup[row] = INT_MIN;
      return c;
   }

   if (row == triangle.size() - 1)
   {
      c = triangle[row][col];
   }
   else
   {
      c = min(min_aux(triangle, lookup, row + 1, col, true),
              min_aux(triangle, lookup, row + 1, col + 1, false))
              + triangle[row][col];
   }

   // if on parent's right branch, save it for later visit
   if (!left)
   {
      lookup[row] = c;
   }
   return c;
}

int minimumTotal(vector<vector<int> > &triangle)
{
   vector<int> lookup;
   lookup.resize(triangle.size());
   std::fill(lookup.begin(), lookup.end(), INT_MIN);
   return min_aux(triangle, lookup, 0, 0, true);
}

We add a boolean variable to the recursion to tell the callee whether it’s in the left branch of its parent, or the right branch. We notice the fact that a node will be accessed at most twice, one from its parent, the other from its left-parent as its right child. We save the value on first visit from its left-parent, and clear the value on second visit from its parent.

I was so happy to submit it to the online judge, only to find out that it failed.

I reviewed the code again and nothing seemed to go wrong. The attachment of a debugger finally revealed the bug. The algorithm holds only if the left branch recursion happens before the right branch. The “min” function call takes two arguments which are both recursive function calls, and the order of which happens first is unspecified. Unfortunately, the right one goes first in this case!

The fix is easy. Instead of wrapping two calls together, we separate them. And normally non-inlined functions act as natural barriers so their relative order is reserved as defined in program order.

int l = minimum_aux(triangle, lookup, row + 1, col, true);
int r = minimum_aux(triangle, lookup, row + 1, col + 1, false);
c = min(l, r) + + triangle[row][col];

With this approach, the run time is reduced to 11ms.

A Little More

Don’t confuse the evaluation order with calling convention. Calling convention specifies in which order parameters are passed to a function, left-to-right, or right-to-left, among several other things. But it doesn’t define anything about evaluation order. Arguments can still be evaluated in any order.