July 11, 2018 Problem Of The Week – “MovingCandies”

This week, we’re going to take a look at a problem that featured in SRM 706, Division 1, Level 1 – “MovingCandies”, authored by Errichto
The summary of the problem statement is – Given a grid of characters, each element being either a ‘.’ or a ‘#’, where ‘.’ denotes an empty cell and ‘#’ denotes a candy, find the minimum number of moves to be made, for a path of candies to exist from the top-left corner to the bottom-right corner. If there is no possible route, return -1.
Now, a recursive solution is fairly intuitive, wherein the parameters would be { number_of_candies_available, current_row, current_col } and the function would return the minimum number of moves made to reach the current_row and current_col position.
After the formulation of this recursive state, the recurrence relation can be easily derived by realizing that any {row, column} co-ordinate can be reached by only its 4 adjacent neighbors that share an edge with it — therefore by factoring in which of the neighbors have candies and which don’t, a recurrence relation can be generated.
In addition, the important point to note here is that there are multiple ways of reaching the same recursive state.

Thus, this leads us to the conclusion that dynamic programming is a viable choice, as we face the issue of repeated subproblems.
So the question then reduces to identifying the correct recurrence relation, and then memoizing the values by either tabulation or a top-down function call. After tabulating, the answer is the value stored at the coordinate at the last row and last column.
The fastest implementation was in C++ by LLI_E_P_JI_O_K taking him 5 minutes and 17 seconds to implement, however the fastest implementer in Java, Petr had a solution worth checking out because apart from following the same algorithm described above, it leveraged the fact that while all function calls have 3 parameters, 1 of them (number_of_candies_available) only revisit the previous state, while the other two (current_row and current_column) revisit 4 states.
Because of this, he changed the space complexity of his code by not memoizing the answers in a 3D array, but in two 2D arrays, keeping track of the 2D array with k number of available candies, while calculating the 2D array with (k+1) number of available candies.
The C++ implementation of the fastest solution is enclosed below –

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int const MAX_N = 32;
int const INT_INF = 1000000000;
int const DX[4] = {-1,1,0,0};
int const DY[4] = {0,0,-1,1};
int dp[MAX_N*MAX_N+MAX_N*2+50][MAX_N][MAX_N];
class MovingCandies {
  public:
    int minMoved(vector <string> t) {
      int n = (int) t.size();
      int m = (int) t[0].size();
      int min_ans = INT_INF, cnt = 0;
      for (int i=0; i<n; i++)
        for (int j=0; j<m; j++) {
          cnt += t[i][j] == '#';
          dp[0][i][j] = INT_INF;
        }
      dp[0][0][0] = (t[0][0] != '#');
      for (int mv=0; mv<n*m+n+m+10; mv++) {
        for (int i=0; i<n; i++)
          for (int j=0; j<m; j++)
            dp[mv+1][i][j] = INT_INF;
        for (int i=0; i<n; i++)
          for (int j=0; j<m; j++) {
            int QQ = dp[mv][i][j];
            if (QQ < INT_INF)
              for (int k=0; k<4; k++) {
                int x = i + DX[k];
                int y = j + DY[k];
                if (x >= 0 && x < n && y >= 0 && y < m)
                  dp[mv+1][x][y] = min(dp[mv+1][x][y], QQ + (t[x][y] != '#'));
              }
          }
      }
      for (int mv=0; mv<cnt; mv++) {
        int QQ = dp[mv][n-1][m-1];
        if (QQ < INT_INF)
          min_ans = min(min_ans, QQ);
      }
      if (min_ans > INT_INF/2)
        min_ans = -1;
      return min_ans;
    }
};