data.js

var Data = Data || {}; Data.files = [{"content":"/**\n * 0-1 knapscak problem.\n * Given weights and values of n items,\n * put these items in a knapsack of\n * capacity W to get the maximum total\n * value in the knapsack.\n **/\nvar items = [\n  {w: 2, v: 10},\n  {w: 24, v: 1},\n  {w: 4, v: 3},\n  {w: 1, v: 20},\n  {w: 6, v: 1},\n  {w: 10, v: 10},\n  {w: 12, v: 11},\n  {w: 18, v: 77},\n  {w: 28, v: 33},\n  {w: 32, v: 43},\n  {w: 42, v: 52},\n  {w: 3, v: 2},\n];\n\nmemofunction f(k, w) {\n  if (k === items.length) return 0;\n  if (w === 0) return 0;\n  var ans = f(k + 1, w);\n  if (w >= items[k].w)\n    ans = Math.max(ans, f(k + 1, w - items[k].w) + items[k].v);\n  return ans;\n}\n\nf(0, 50);\n","title":"0-1-knapsack.js"},{"content":"/**\n * Calculate the combination number C(n, m), (pick m elements from n)\n **/\n\nmemofunction c(n, m) {\n  if (n <  0) return 0;\n  if (m === 0) return 1;\n  if (m < 0) return 0;\n  if (n === m) return 1;\n  if (n < m) return 0;\n  return c(n-1, m-1) + c(n-1, m);\n}\n\nc(40, 18);\n","title":"CombinationCalculator.js"},{"content":"/**\n * Find the minimum step to edit word2 into word1.\n * Action of editing could be\n * 1. Insert a character\n * 2. Delete a character\n * 3. Replace a character\n **/\n\nvar word1 = \" *  if (i < n && j < m) result = Math.min(result, 1)\";\nvar word2 = \"  if (i < n && j < m && word1[i] === word2[j]) result = 1;\";\nvar n = word1.length;\nvar m = word2.length;\nmemofunction f(i, j) {\n  if (i === n && m === j) return 0;\n  var result = 1000000; // a very large number\n  if (j < m) result = Math.min(result, f(i, j+1) + 1);\n  if (i < n) result = Math.min(result, f(i+1, j) + 1);\n  if (i < n && j < m) result = Math.min(result, f(i+1, j+1) + 1);\n  if (i < n && j < m && word1[i] === word2[j]) result = Math.min(result, f(i+1, j+1));\n  return result;\n}\n\nf(0, 0);\n","title":"EditDistance.js"},{"content":"var n = 10, m = 20;\n\nmemofunction f(i, j) {\n  if (i === n) return 1;\n  if (j === m) return 1;\n  return f(i+1, j) + f(i, j+1);\n}\n\nf(0, 0);\n","title":"counting.js"},{"content":"memofunction fib(n) {\n    if (n === 0)\n        return 0;\n    if (n === 1)\n        return 1;\n    return fib(n-1) + fib(n-2);\n}\n\nfib(20);","title":"fib.js"},{"content":"/**\n * Given a list of positive integer, find a formulation that has maximum result, with + and *.\n * Example:\n * with list 3 1 3, the maximum result is 3*1*3\n * with list 1 3 1, the maximum result is 1+3+1\n **/\n\nvar a = [1, 3, 4, 8, 8, 1, 1, 3, 9, 1, 2];\n\nmemofunction s(i, j) {\n  if (j < i) return 0;\n  if (j === i) return a[i];\n  return s(i, j-1) * a[j];\n}\n\nmemofunction f(i, j) {\n  if (i === a.length && j === i) return 0;\n  if (j >= a.length) return -1000000;\n  return Math.max(f(j+1, j+1) + s(i, j), f(i, j+1));\n}\n\n\nf(0, 0);\n","title":"maximumResult.js"},{"content":"/**\n * Find the longest moving down strike on a 2D map.\n **/\nvar maxr = 5;\nvar maxc = 5;\nvar height = [\n    [1, 2, 3, 4, 5],\n    [16, 17, 18, 19, 6],\n    [15, 24, 25, 20, 7],\n    [14, 23, 22, 21, 8],\n    [13, 12, 11, 10, 9]\n];\nvar d = [\n    {r: 1, c: 0},\n    {r: -1, c: 0},\n    {r: 0, c: 1},\n    {r: 0, c: -1}\n];\n\nmemofunction l(row, col) {\n    var answer = 1;\n    var currHeight = height[row][col];\n    for (var i = 0; i < 4; i++) {\n        var nr = d[i].r + row;\n        var nc = d[i].c + col;\n        if (nr < 0 || nc < 0 || nr >= maxr || nc >= maxc) {\n            continue;\n        }\n        if (height[nr][nc] < currHeight) {\n            answer = answer >= l(nr, nc) + 1 ? answer : l(nr, nc) + 1;\n        }\n    }\n    return answer;\n}\n\nl(2, 2);\n","title":"skiing.js"}];