-
-
Save mladen/15eb8b1954b2162348da to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Build a tree using a compacted object with no pointer for the left/right children | |
function buildTree(A) { | |
// Shuffle the array. so we gain a more balance search tree | |
A.sort(function() { return parseInt(Math.random()*3) - 1; }); | |
var tree = {'0': A[0]}, current = 1; | |
var inserted, node, treeSize = 1; | |
// This will take O(N * log N) if we have a balanced tree | |
// the worst case cost will be O(N^2) | |
for (var i = 1; i < A.length; i++) { | |
node = A[i]; | |
inserted = false; | |
current = 1; | |
while (!inserted) { | |
if ( treeSize <= current ) { | |
treeSize += current - treeSize; | |
} | |
if (tree[current - 1] === undefined) { | |
tree[current - 1] = node; | |
inserted = true; | |
} else if (tree[current - 1] < node) { | |
// go to the right | |
current = current * 2 + 1; | |
} else { | |
current = current * 2; | |
} | |
} | |
} | |
tree.length = treeSize; | |
return tree; | |
} | |
// Levenshtein distance in O(2^n) | |
function strDistance(str1, str2, i, j) { | |
if (i === 0 || j === 0) { | |
return Math.max(i, j); | |
} | |
var distance = (str1.charAt(i) == str2.charAt(j)) ? 0 : 1; | |
return Math.min( | |
strDistance(str1, str2, i - 1, j) + 1 | |
, strDistance(str1, str2, i, j - 1) + 1 | |
, strDistance(str1, str2, i - 1, j - 1) + distance | |
); | |
} | |
// Levenshtein distance in O(n^2) | |
function strDistance(str1, str2, len1, len2) { | |
var distance, | |
memo = new Array(len1 + 1); | |
for (var i = 0; i <= len1; i++) { | |
memo[i] = new Array(len2 + 2); | |
memo[i][0] = i; | |
} | |
for (var i = 0; i <= len2; i++) { | |
memo[0][i] = i; | |
} | |
for (var i = 1; i <= len1; i++) { | |
for (var j = 1; j <= len2; j++) { | |
distance = (str1.charAt(i) == str2.charAt(j)) ? 0 : 1; | |
memo[i][j] = Math.min( | |
memo[i - 1][j] + 1 | |
, memo[i][j - 1] + 1 | |
, memo[i - 1][j - 1] + distance | |
); | |
} | |
} | |
return memo[len1][len2]; | |
} | |
// Get nodes relative to a given target if their distance equal 'distance' | |
function getNodesWithDistance(flatTree, distances, index, distance, visited) { | |
if (index < 0 || index > flatTree.length || visited[index] === true) { | |
return []; | |
} | |
if (distance === 0) { | |
return (flatTree[index - 1] === undefined) ? [] : [flatTree[index - 1]]; | |
} | |
visited[index] = true; | |
var result = []; | |
result = result.concat( | |
getNodesWithDistance(flatTree, distances, index * 2, distance - 1, visited) | |
, getNodesWithDistance(flatTree, distances, index * 2 + 1, distance - 1, visited) | |
, getNodesWithDistance(flatTree, distances, parseInt(index / 2), distance - 1, visited) | |
); | |
return result; | |
} | |
// Get all elements which have a distance of `D` (distance) from node `N` (node) | |
function treeLevel(flatTree, node, distance) { | |
var distances = {}; | |
var treeSize = flatTree.length; | |
var currentIndex = 0; | |
var queue = [1]; | |
// Place a sentinel | |
distances[-1] = -1; | |
while (queue.length > 0 && currentIndex < treeSize) { | |
// queue.shift() is slow! O(N) uuuuh! | |
// Instead implement an amortized dequeue operation. | |
currentIndex = queue.shift(); | |
// Get the distance of the parent and add 1 | |
distances[currentIndex - 1] = distances[parseInt(currentIndex / 2) - 1] + 1; | |
queue.push(currentIndex * 2); | |
queue.push(currentIndex * 2 + 1); | |
} | |
currentIndex = 1; | |
while (currentIndex <= treeSize) { | |
if (flatTree[currentIndex - 1] == node) { | |
return getNodesWithDistance(flatTree, distances, currentIndex, distance, {}); | |
} else if (flatTree[currentIndex - 1] > node) { | |
currentIndex = currentIndex * 2; | |
} else { | |
currentIndex = currentIndex * 2 + 1; | |
} | |
} | |
return null; | |
} | |
// Integer partition problem in O(2^n) uhh. can be reduced to polynomial time using DP | |
function intPartition(target, maxValue, append) { | |
if (target == 0) { | |
return [append]; | |
} else { | |
var parts, result = []; | |
if (maxValue > 1) { | |
parts = intPartition(target, maxValue-1, append.slice(0)); | |
for (var i = 0; i < parts.length; i++) { | |
result.push(parts[i]); | |
} | |
} | |
if (target >= maxValue) { | |
parts = intPartition(target - maxValue, maxValue, append.concat([maxValue])); | |
for (var i = 0; i < parts.length; i++) { | |
result.push(parts[i]); | |
} | |
} | |
return result; | |
} | |
} | |
// Set partition problem | |
// Returns true if A can be partitioned into two subsets such that the sum of the elements | |
// of both half is the same | |
// @param {Bool} recursive if you want a O(2^n) cost, false if you are smart and want O(n^2) | |
function partition(A, recursive) { | |
var findSubset; | |
var POS_STAY = 0; | |
var POS_UP = 1; | |
var POS_UP_LEFT = 2; | |
if (recursive === true) { | |
// O(2^n) Ouhh! | |
findSubset = function(A, n, sum) { | |
if (sum == 0) { | |
return true; | |
} | |
if (n == 0 && sum != 0) { | |
return false; | |
} | |
if (A[n-1] > sum) { | |
return findSubset(A, n - 1, sum); | |
} | |
return findSubset(A, n - 1, sum) || findSubset(A, n - 1, sum - A[n - 1]); | |
}; | |
} else { | |
// Dynamic programming | |
findSubset = function(A, n, sum) { | |
var memo = new Array(n + 1); | |
for (var i = 0; i <= n; i++) { | |
memo[i] = new Array(sum + 1); | |
memo[i][0] = {sol: true, pos: POS_STAY}; | |
} | |
for (var i = 1; i <= sum; i++) { | |
memo[0][i] = {sol: false, pos: POS_STAY}; | |
} | |
for (var i = 1; i <= n; i++) { | |
for (var j = 1; j <= sum; j++) { | |
if (A[i-1] > j) { | |
memo[i][j] = {sol: memo[i-1][j].sol, pos: POS_UP}; | |
} else { | |
if (memo[i-1][j].sol) { | |
memo[i][j] = {sol: true, pos: POS_UP}; | |
} else if (memo[i-1][j-A[i-1]].sol) { | |
memo[i][j] = {sol: true, pos: POS_UP_LEFT}; | |
} else { | |
memo[i][j] = {sol: false, pos: POS_STAY}; | |
} | |
} | |
} | |
} | |
// If we have a solution | |
if (memo[n][sum].sol) { | |
var setA = []; | |
var setB = []; | |
var j = sum; | |
var i = n; | |
while (i > 0 && j>=0) { | |
if (memo[i][j].pos == POS_UP_LEFT) { | |
// This is a solution for setA | |
setA.push(A[i-1]); | |
i = i - 1; | |
j = j - A[i]; | |
} else if (memo[i][j].pos == POS_UP) { | |
i = i - 1; | |
setB.push(A[i]); | |
} else { | |
i = i - 1; | |
setB.push(A[i]); | |
} | |
} | |
while (i > 0) { | |
i--; | |
setB.push(A[i]); | |
} | |
return [setA, setB]; | |
} else { | |
return []; | |
} | |
}; | |
} | |
var sum = 0; | |
for (var i = 0; i < A.length; i++) { | |
sum += A[i]; | |
} | |
if (sum % 2 != 0) { | |
return []; | |
} | |
return findSubset(A, A.length, sum / 2); | |
} | |
// Object mixin | |
var extend = function(obj) { | |
var args = Array.prototype.slice.call(arguments, 1); | |
for (var i = 0, len = args.length; i < len; i++) { | |
for (var prop in args[i]) { | |
obj[prop] = args[i][prop]; | |
} | |
} | |
};s | |
// Extend an Object | |
Model.extend = function(proto) { | |
var parent = this; | |
var child = function() { return parent.apply(this, arguments); }; | |
// static | |
extend(child, parent); | |
var Dummy = function() { this.constructor = child; }; | |
Dummy.prototype = parent.prototype; | |
child.prototype = new Dummy(); | |
extend(child.prototype, proto); | |
child.__super__ = parent.prototype; | |
return child; | |
}; | |
// Test | |
var User = Model.extend({ | |
init: function(username, password) { | |
this.props.username = username; | |
this.props.password = password; | |
} | |
}); | |
// Subtype of User | |
var AdminUser = User.extend({ | |
init: function(username, password) { | |
this.__super__.init(username, password); | |
} | |
}) | |
// Swap two values in an array A using bit manipulation. | |
// The V8 engine may optimize swap if you store a copy of the value, but it's an interesting hack | |
function swap(A, i, j) { | |
A[i] = A[i] ^ A[j]; | |
A[j] = A[i] ^ A[j]; | |
A[i] = A[i] ^ A[j]; | |
} | |
// Get a random index within [l, r] inclusive | |
function randomIndex(l, r) { | |
return parseInt((r - l + 1) * Math.random()) + l; | |
} | |
// Partition subrutine. | |
// Takes an array A and partition the array such that | |
// A[i] for each i in 0...pivot-1 <= A[pivot] <= A[j] for each j in pivot+1...sizeof(A) | |
// This procedure runs in O(n) | |
function partition(A, l, r) { | |
var pivotIndex = randomIndex(l, r); | |
var pivot = A[pivotIndex]; | |
var q = pivotIndex; | |
for (var i = l + 1; i <= r; i++) { | |
if (A[i] < pivot) { | |
swap(A, i, q); | |
q++; | |
} | |
} | |
return q; | |
} | |
// Quicksort | |
// This is the randomized version which runs in O(n*log n) :) | |
function quicksort(A, l, r) { | |
if (l < r ) { | |
var q = partition(A, l, r); | |
quicksort(A, l, q); | |
quicksort(A, q + 1, r); | |
} | |
} | |
// Gets the nth element in an unsorted array in O(n) time. | |
// for example nth([2,8,9,1,10,25], 0, 5, 1) will return the first element in the array which is 1, in O(n)! | |
// no sorting is required | |
function nth(A, l, r, n) { | |
if (l == r) { | |
return A[l] | |
} else { | |
var q = partition(A, l, r); | |
var k = q - l + 1; | |
if (k == n) { | |
return A[q]; | |
} else if (n < k) { | |
return nth(A, l, q - 1, n); | |
} else { | |
return nth(A, q + 1, r, n - k); | |
} | |
} | |
} | |
// Get the hight of a given tree or subtree. | |
function treeHeight(tree) { | |
if (tree == null) { | |
return 0; | |
} | |
return Math.max(treeHeight(tree.left), treeHeight(tree.right)) + 1; | |
} | |
// Get the Lowest common ancestor of two nodes in a tree | |
function lca(root, a, b) { | |
if (root == null) { | |
return null; | |
} | |
if (a > root.value && b > root.value) { | |
return lca(root.right, a, b); | |
} else if (a < root.value && b < root.value) { | |
return lca(root.left, a, b); | |
} else { | |
return root; | |
} | |
} | |
// 3SUM problem for a sorted list | |
// Return a triple where A[i] + A[j] = A[t] where {i, j , t} >= 0 && <= sizeof(list) -1 | |
// Runtime: O(n^2), memory: O(1) | |
function sums(list) { | |
var solutions = []; | |
for (var i = list.length-1; i >= 2; i--) { | |
var c = list[i]; | |
var r = i - 1; | |
var l = 0; | |
while (l < r) { | |
var a = list[l]; | |
var b = list[r]; | |
var sum = a + b; | |
if (sum == c) { | |
solutions.push([a, b, c]); | |
l = l + 1; | |
r = r - 1; | |
} else if (sum < c) { | |
l = l + 1; | |
} else { | |
r = r - 1; | |
} | |
} | |
} | |
return solutions; | |
} | |
// 3SUM problem for an unsorted list | |
// Runtime: O(n^2) , memory: O(n) | |
function sums2(list) { | |
var solutions = []; | |
for (var i = 0; i < list.length; i++) { | |
var c = list[i]; | |
var memo = {}; | |
for (var j = 0; j < list.length; j++) { | |
if (j != i) { | |
if (memo[c - list[j]]) { | |
solutions.push([list[j], c - list[j], c]); | |
} | |
memo[list[j]] = true; | |
} | |
} | |
} | |
return solutions; | |
} | |
// Take a sorted list and | |
// return an array of 2-tuples where A[i] + A[j] = target | |
// Runtime: o(n) | |
function eqTarget(list, target) { | |
var solutions = []; | |
var l = 0; | |
var r = list.length - 1; | |
var sum; | |
while (l < r) { | |
sum = list[l] + list[r]; | |
if (sum == target) { | |
solutions.push([list[l], list[r]]); | |
l = l + 1; | |
r = r - 1; | |
} else if (sum < target) { | |
l = l + 1; | |
} else { | |
r = r - 1; | |
} | |
} | |
return solutions; | |
} | |
// Takes an unsorted list and | |
// return an array of 2-tuples where A[i] + A[j] = target | |
// Runtime: o(n) | |
function eqTarget2(list, target) { | |
var solutions = []; | |
var memo = {}; | |
for (var i = 0; i < list.length; i++) { | |
if (memo[target - list[i]]) { | |
solutions.push([list[i], target - list[i]]); | |
} | |
memo[list[i]] = true; | |
} | |
return solutions; | |
} | |
// Find a value in a sorted list using a binary search | |
// Runtime: O(log n) | |
function find(list, value) { | |
var l = 0; | |
var r = list.length; | |
var mid; | |
while (l <= r) { | |
mid = Math.floor(( l + r ) / 2); | |
if (list[mid] < value) { | |
l = mid + 1; | |
} else if (list[mid] > value) { | |
r = mid - 1; | |
} else { | |
return mid; | |
} | |
} | |
return -1; | |
} | |
// Return the max crossing sum in a list where l <= m <= r | |
function maxCrossing(list, l, m, r) { | |
var leftMax = -Infinity; | |
var leftSum = 0; | |
var leftIndex; | |
for (var i = m; i >= l; i--) { | |
leftSum += list[i]; | |
if (leftSum > leftMax) { | |
leftMax = leftSum; | |
leftIndex = i; | |
} | |
} | |
var rightMax = -Infinity; | |
var rightSum = 0; | |
var rightIndex; | |
for (var i = m + 1; i <= r; i++) { | |
rightSum += list[i]; | |
if (rightSum > rightMax) { | |
rightMax = rightSum; | |
rightIndex = i; | |
} | |
} | |
return { | |
sum: leftMax + rightMax, | |
left: leftIndex, | |
right: rightIndex | |
} | |
} | |
// Returns the maximum crossing subarray in an array | |
// runtime O(n*log n) | |
function maxSubarray(list, l, r) { | |
if (l == r) { | |
return {left: l, right: r, sum: list[l]}; | |
} else { | |
var mid = Math.floor((l + r ) / 2); | |
var left = maxSubarray(list, l, mid); | |
var right = maxSubarray(list, mid + 1, r); | |
var crossing = maxCrossing(list, l, mid, r); | |
if (left.sum >= crossing.sum && left.sum >= right.sum) { | |
return {left: left.left, right: left.right, sum: left.sum}; | |
} else if (right.sum >= crossing.sum && right.sum >= left.sum) { | |
return {left: right.left, right: right.right, sum: right.sum}; | |
} else { | |
return {left: crossing.left, right: crossing.right, sum: crossing.sum}; | |
} | |
} | |
} | |
// Sorts an array using bubble sort | |
// runtime: O(n^2) | |
function bubbleSort(A) { | |
var wasSwaped = false; | |
do { | |
wasSwaped = false; | |
for (var j = 1; j < A.length; j++) { | |
if (A[j - 1] > A[j]) { | |
swap(A, j - 1, j); | |
wasSwaped = true; | |
} | |
} | |
} while (wasSwaped); | |
return A; | |
} | |
// Sorts an array using selection sort | |
// runtime: O(n^2) | |
function selectionSort(A) { | |
for (var i = 0; i < A.length; i++) { | |
var k = i; | |
var min = A[i]; | |
for (var j = i + 1; j < A.length; j++) { | |
if ([j] < min) { | |
min = A[j]; | |
k = j; | |
} | |
} | |
if (k != i) { | |
swap(A, i, k); | |
} | |
} | |
return A; | |
} | |
// Sorts an array using insertion sort | |
// runtime: O(n^2) | |
function insertionSort(A) { | |
for (var i = 0; i < A.length; i++) { | |
var j = i; | |
while (j > 0 && A[j - 1] > A[j]) { | |
swap(A, j - 1, j); | |
j--; | |
} | |
} | |
return A; | |
} | |
// Merge two sorted arrays into one array | |
// runtime: O(n) | |
function merge(A, B) { | |
var list = []; | |
var j = 0; | |
var i = 0; | |
while (i < A.length && j < B.length) { | |
if (A[i] < B[j]) { | |
list.push(A[i]); | |
i++; | |
} else { | |
list.push(B[j]); | |
j++; | |
} | |
} | |
while (i < A.length) { | |
list.push(A[i]); | |
i++; | |
} | |
while (j < B.length) { | |
list.push(B[j]); | |
j++; | |
} | |
return list; | |
} | |
// Sort an array using merge sort | |
// runtime: O(n*log n). memory: O(n) | |
function mergeSort(list, l, r) { | |
if (l == r) { | |
return [list[l]]; | |
} | |
var mid = Math.floor( (l + r) / 2); | |
var left = mergeSort(list, l, mid); | |
var right = mergeSort(list, mid + 1, r); | |
return merge(left, right); | |
} | |
// Return the power set of a set. | |
// That is, all the possible subsets within a set | |
// runtime: O(2^n) | |
function powerSet(set) { | |
if (set.length == 0) { | |
return []; | |
} | |
if (set.length == 1) { | |
return [[set[0]]]; | |
} | |
var result = [ [set[0]] ]; | |
var subset = powerSet(set.slice(1)); | |
for (var i = 0; i < subset.length; i++) { | |
result.push(subset[i]); | |
result.push([set[0]].concat(subset[i])); | |
} | |
return result; | |
} | |
// Return a list with all the permutations of a given string | |
// Runtime: O(n!) | |
function permutation(str) { | |
if (str === '') { | |
return []; | |
} else if (str.length == 1) { | |
return [str]; | |
} else { | |
var solutions = []; | |
for (var i = 0; i < str.length; i++) { | |
var character = str.charAt(i); | |
var permutes = permutation(str.substr(0, i) + str.substr(i + 1)); | |
for (var j = 0; j < permutes.length; j++) { | |
solutions.push(character + permutes[j]); | |
} | |
} | |
return solutions; | |
} | |
} | |
// Return a list with all the permutations of a given array | |
// Runtime: O(n!) | |
function permutation2(arry) { | |
if (arry.length === 0) { | |
return []; | |
} else if (arry.length == 1) { | |
return [[arry[0]]]; | |
} else { | |
var solutions = []; | |
for (var i = 0; i < arry.length; i++) { | |
var character = arry[i]; | |
var permutes = permutation2(arry.slice(0, i).concat(arry.slice(i + 1))); | |
for (var j = 0; j < permutes.length; j++) { | |
solutions.push([character].concat(permutes[j])); | |
} | |
} | |
return solutions; | |
} | |
} | |
// Return the first `num` binary numbers | |
function binary(num) { | |
if (num <= 1) { | |
return ['0', '1']; | |
} | |
var b = binary(num - 1); | |
var result = []; | |
for (var i = 0; i < b.length; i++) { | |
result.push(b[i] + '0'); | |
result.push(b[i] + '1'); | |
} | |
return result; | |
} | |
// Longest common subsquence problem | |
// Return the string that contains the most elements in common | |
// runtime: O(n^2) | |
function lcs(str1, str2) { | |
var len1 = str1.length; | |
var len2 = str2.length; | |
var table = new Array(len1+1); | |
var POSITION = {LEFT: 1, UP: 2, LEFTUP: 3, NONE: 0}; | |
for (var i = 0; i <= len1; i++) { | |
table[i] = new Array(len2+1); | |
table[i][0] = {len: 0, dest: POSITION.NONE}; | |
} | |
for (var j = 0; j <= len2; j++) { | |
table[0][j] = {len: 0, dest: POSITION.NONE}; | |
} | |
for (var i = 1; i <= len1; i++) { | |
for (var j = 1; j <= len2; j++) { | |
if (str1.charAt(i-1) == str2.charAt(j-1)) { | |
table[i][j] = {len: table[i-1][j-1].len + 1, dest: POSITION.LEFTUP}; | |
} else { | |
if (table[i-1][j].len > table[i][j-1].len) { | |
table[i][j] = {len: table[i-1][j].len, dest: POSITION.LEFT}; | |
} else { | |
table[i][j] = {len: table[i][j-1].len, dest: POSITION.UP}; | |
} | |
} | |
} | |
} | |
var i = len1; | |
var j = len2; | |
var str = ''; | |
while (i > 0 && j > 0) { | |
if (table[i][j].dest == POSITION.LEFT) { | |
i--; | |
} else if (table[i][j].dest == POSITION.UP) { | |
j--; | |
} else if (table[i][j].dest == POSITION.LEFTUP) { | |
str = str1.charAt(i-1) + str; | |
i--; | |
j--; | |
} else { | |
break; | |
} | |
} | |
return str; | |
} | |
// Diff algorithm | |
// Return the difference character by character between two strings using lcs | |
// runtime: O(n^2) | |
function diff(str1, str2) { | |
var sub = lcs(str1, str2); | |
var len1 = str1.length; | |
var len2 = str2.length; | |
var changes = ''; | |
var i = 0, j = 0, s = 0; | |
while (i < len1 && j < len2 && s < sub.length) { | |
if (str1.charAt(i) == sub.charAt(s)) { | |
if (str2.charAt(j) == sub.charAt(s)) { | |
changes += '*' + str1.charAt(i); | |
i++; | |
s++; | |
j++; | |
} else { | |
changes += '+' + str2.charAt(j); | |
j++; | |
} | |
} else { | |
changes += '-' + str1.charAt(i); | |
i++; | |
} | |
} | |
while (i < len1) { | |
changes += '-' + str1.charAt(i); | |
i++; | |
} | |
while (j < len2) { | |
changes += '+' + str2.charAt(j); | |
j++; | |
} | |
return changes; | |
} | |
// Subset sum problem | |
// Return a subset of `a` such that if you sum all the elements within that subset | |
// they will equal a target number `q` | |
// Recurrence: | |
// i : means include the ith element in A | |
// target: the current target value | |
// P(i, target) -> true if i = 0 && target = 0 (don't include any element) | |
// -> false if i = 0 && target!=0 | |
// -> (target >= A[i - 1] && P(i - 1, target - A[i - 1])) || P(i - 1, target) otherwise | |
// | |
// * The exponential function: | |
// function getSubset(A, i, target) { | |
// if (i === 0) { | |
// return (target === 0); | |
// } else { | |
// return (target >= A[i-1] && getSubset(A, i - 1, target - A[i-1])) || getSubset(A, i-1, target); | |
// } | |
// } | |
// Example: getSubset([1,2,3,4,5], 5, 7) -> true because 5+2 or 3+4 or 1+2+4 is 7 | |
// | |
// | |
// DP Solution Runtime: O(n^2) | |
function getSubset(A, q) { | |
var listSize = A.length; | |
var memo = new Array(listSize + 1); | |
var solutions = []; | |
for (var i = 0; i <= listSize; i++) { | |
memo[i] = new Array(q + 1); | |
} | |
for (var i = 1; i <= q; i++) { | |
memo[0][i] = {belong: false, exists: false}; | |
} | |
memo[0][0] = {belong: false, exists: true}; | |
for (var i = 1; i <= listSize; i++) { | |
for (var j = 0; j <= q; j++) { | |
memo[i][j] = {belong: false, exists: false}; | |
if (j >= A[i-1] && memo[i-1][j-A[i-1]].exists) { | |
memo[i][j].exists = true; | |
memo[i][j].belong = true; | |
solutions.push(A[i - 1]); | |
} else if (memo[i - 1][j].exists) { | |
memo[i][j].exists = true; | |
} | |
} | |
} | |
return memo[listSize][q].exists; | |
} | |
// Rod cutting problem in O(2^n) | |
// Giving a list `A` where A[i] represents the cost of a rod of length i | |
// Return the maximum cost you can get from a rod of size n if you cut | |
// it in smaller pieces | |
function cutRod(A, n) { | |
if (t === 0) { | |
return 0; | |
} | |
var max = -Infinity; | |
for (var i = 1; i <= n; i++) { | |
max = Math.max(max, A[i] + cutRod(A, n - i)); | |
} | |
return max; | |
} | |
// Rod cutting problem in O(n^2) using DP | |
// Example: cutRodDP([0,1,5,8,9,10,17,17,20,24,30],9) -> { maxCost: 25, parts: [ 3, 6 ] } | |
function cutRodDP(A, n) { | |
var memo = new Array(n + 1); | |
var parts = new Array(n + 1); | |
memo[0] = 0; | |
for (var i = 1; i <= n; i++) { | |
maxCost = - Infinity; | |
for (var j = 1; j <= i; j++) { | |
costIncludingJ = A[j] + memo[i - j]; | |
if (costIncludingJ > maxCost) { | |
maxCost = costIncludingJ; | |
parts[i] = j; | |
} | |
}; | |
memo[i] = maxCost; | |
} | |
var solutions = []; | |
var i = n; | |
while (i > 0) { | |
solutions.push(parts[i]); | |
i = i - parts[i]; | |
} | |
return {maxCost: memo[n], parts: solutions}; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment