Unique Paths

JavaScript performance comparison

Test case created by Adrian

Preparation code


      
      <script>
Benchmark.prototype.setup = function() {
  function paths(r, c) {
      // Since we are already in the first row and first column
      // there is one movement we wont be doing
      r--;
      c--;
  
      var total = r + c;
      var tFactorial = 1;
      var rFactorial;
      var cFactorial;
      for (var i = 1; i <= total; i++) {
          tFactorial *= i;
          if (i === r) {
              rFactorial = tFactorial;
          }
  
          if (i === c) {
              cFactorial = tFactorial;
          }
      }
  
      return tFactorial / (rFactorial * cFactorial);
  }
  
  function paths2(r, c) {
      // Make rows and columns 0 based
      r--;
      c--;
  
      function doIt(x, y) {
          // We are in a extreme column or in a
          // extreme row. There is one one more
          // way to get to the end
          if (x === c || y === r) {
              return 1;
          }
  
          // We are not in a extreme, so add the
          // paths for both right and left
          return doIt(x + 1, y) + doIt(x, y + 1);
      }
  
      return doIt(0, 0);
  }
  
  function paths3(r, c) {
      // Make rows and columns 0 based
      r--;
      c--;
      var cache = {};
  
      function doIt(x, y) {
          // We are in a extreme column or in a
          // extreme row. There is one one more
          // way to get to the end
          if (x === c || y === r) {
              return 1;
          }
  
          // We are not in a extreme, so add the
          // paths for both right and left
          if (!cache[(x + 1) + ',' + y]) {
              cache[(x + 1) + ',' + y] = doIt(x + 1, y);
          }
          if (!cache[x + ',' + (y + 1)]) {
              cache[x + ',' + (y + 1)] = doIt(x, y + 1);
          }
  
          return cache[(x + 1) + ',' + y] + cache[x + ',' + (y + 1)];
      }
  
      return doIt(0, 0);
  }
  
  function paths4(r, c) {
      function doIt(x, y) {
          // We are in the top or in the left
          if (x === 0 || y === 0) {
              return 1;
          }
  
          return doIt(x - 1, y) + doIt(x, y - 1);
      }
  
      // Make rows and columns 0 based
      return doIt(r -1, c - 1);
  }
  
  function paths5(r, c) {
      var cache = {};
  
      function doIt(x, y) {
          // We are in the top or in the left
          if (x === 0 || y === 0) {
              return 1;
          }
  
          // Don't calculate values that have already
          // been calculated
          if (!cache[(x - 1) + '-' + y]) {
              cache[(x - 1) + '-' + y] = doIt(x - 1, y);
          }
          if (!cache[x + '-' + (y - 1)]) {
              cache[x + '-' + (y - 1)] = doIt(x, y - 1);
          }
  
          return cache[(x - 1) + '-' + y] + cache[x + '-' + (y - 1)];
      }
  
      // Make rows and columns 0 based
      return doIt(r -1, c - 1);
  }
  
  function paths6(r, c, m, n) {
    if (r == m && c == n) {
      return 1;
    }
    if (r > m || c > n) {
      return 0;
    }
  
    return paths6(r+1, c, m, n) + paths6(r, c+1, m, n);
  }
  
  function paths7(r, c) {
    var mat = []
  
    function backtrack(r, c, m, n) {
      if (r == m && c == n) {
        return 1;
      }
      if (r > m || c > n) {
        return 0;
      }
  
      if (!mat[r+1]) {
        mat[r+1] = [];
      }
      if (!mat[r]) {
        mat[r] = [];
      }
  
      if (mat[r+1][c] == undefined) {
        mat[r+1][c] = backtrack(r+1, c, m, n, mat);
      }
      if (mat[r][c+1] == undefined) {
        mat[r][c+1] = backtrack(r, c+1, m, n, mat);
      }
  
      return mat[r+1][c] + mat[r][c+1];
    }
  
    return backtrack(1, 1, r, c);
  }
  
  function paths8(m, n) {
    var mat = [];
    mat[m] = [];
    mat[m][n+1] = 1;
  
    for (r = m; r >= 1; r--) {
      if (!mat[r]) {
        mat[r] = [];
      }
      if (!mat[r+1]) {
        mat[r+1] = [];
      }
  
      for (c = n; c >= 1; c--) {
        mat[r][c] = (mat[r+1][c] || 0) + (mat[r][c+1] || 0);
      }
    }
  
    return mat[1][1];
  }

};
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in CCBot 2.0.0 / Other 0.0.0
Test Ops/sec
Combinatorics
paths(10, 8);
pending…
Top-bottom
paths2(10, 8);
pending…
Top-bottom memoized
paths3(10, 8);
pending…
Bottom-top
paths4(10, 8);
pending…
Bottom-top memoized
paths5(10, 8);
pending…
Top-bottom leet
paths6(10, 8);
pending…
Top-bottom memoized leet
paths7(10, 8);
pending…
Bottom-top leet
paths8(10, 8);
pending…

You can edit these tests or add even more tests to this page by appending /edit to the URL.

Compare results of other browsers

0 Comments