test3_dp.cpp

test3_dp.cpp

#include <bits/stdc++.h>
#include <lab.H>
using namespace std;


float calculateDistance(int x, int y)
{
  return sqrt(x*x + y*y);
}

// translate col in 2D array to X axis coordinate with (0,0) at the center of the array
inline int xtrans(int idx, int delta)
{
  return idx - delta;
}

// translate row in 2D array to Y axis coordinate with (0,0) at the center of the array
inline int ytrans(int idx, int delta)
{
  return delta - idx;
}

/*
 * Algo: Dynamic Programming
 *  - State: dp[k][i][j]
 *    - k: the N-th step
 *    - i, j: the matrix for each step where we fill the expected distance for the step
 *  - State Transition:
 *    - dp[k-1][i][j] = f(dp[k][i][j])
 *  - Initial Values:
 *    - We should first fill the matrix for last step, where the value is simply the sqrt(x^2, y^2)
 *
 *  Note in below code the state is compressed from 3D to 2D
 *
 * Complexity:
 *   - (2N+1)*(2N+1)*N = O(N^3) - where N is the num of steps
 *
 * Notes:
 *   - A naive DFS recursive is extremely slow with O(4^N)
 *   - Memorize for each (x, y, step) could signifanty speed it up, but still a lot slower than the DP solution (cache overhead)
 */
float ExpectedCrabWalk(int numsSteps)
{
  constexpr static int   NumOfDirs = 4;
  // Direction:                               left down, right, up
  constexpr static array<int, NumOfDirs> dx = {0,   1,    0,     -1};
  constexpr static array<int, NumOfDirs> dy = {-1,  0,    1,     0};

  if(numsSteps <= 0) return 0.0f;
  int n = 2 * numsSteps + 1;
  vector<vector<float>> dp(n, vector<float>(n, 0.0f));
  for(int k = numsSteps; k >= 0; --k)
  {
    for(int i = 0; i < n; ++i)
    {
      for(int j = 0; j < n; ++j)
      {
        int x = xtrans(j, numsSteps);
        int y = ytrans(i, numsSteps);

        int coordinateSum = abs(x) + abs(y);

        if(coordinateSum <= k && (coordinateSum % 2) == (k % 2))
        {
          if(k == numsSteps)
          {
            // Initialize the matrix value for last step
            dp[i][j] = calculateDistance(x, y);
          }
          else
          {
            // Calulate based on previous step
            float newDist = 0.0;
            for(int dir = 0; dir < NumOfDirs; ++dir)
            {
              newDist += dp[i+dx[dir]][j+dy[dir]] * 0.2;
            }

            // fall asleep - no need to infer from original dp[i][j] as should have no further moves
            dp[i][j] = newDist + calculateDistance(x, y) * 0.2;
          }
        }
      }
    }
  }
  return dp[numsSteps][numsSteps];
}

int main(int argc, char** argv)
{
  TIMING(ExpectedCrabWalk(1), "cache warming up");
  for(int i = -2 ; i < 100; ++i)
  {
    TIMING(ExpectedCrabWalk(i), i);
  }
}