Skip to content

Instantly share code, notes, and snippets.

@marcin-chwedczuk
Created January 14, 2018 10:05
Show Gist options
  • Save marcin-chwedczuk/e93fd9b48c25ebd2412dc2e0bf6883d7 to your computer and use it in GitHub Desktop.
Save marcin-chwedczuk/e93fd9b48c25ebd2412dc2e0bf6883d7 to your computer and use it in GitHub Desktop.
Swap trees.js
function places(treeHeights) {
var N = treeHeights.length;
var H = 0;
for (var i = 1; i < N - 1; i++) {
H += dH(i);
}
for (var firstTree = 0; firstTree < N; firstTree++) {
var minH = H; // swap firstTree <-> firstTree
var swapWith = firstTree;
for (var secondTree = 0; secondTree < N; secondTree++) {
// swap firstTree <-> secondTree
var afterSwapH = H;
afterSwapH -= dH(firstTree) + dH(secondTree);
swapHeights(firstTree, secondTree);
afterSwapH += dH(firstTree) + dH(secondTree);
swapHeights(firstTree, secondTree);
if (afterSwapH < minH) {
minH = afterSwapH;
swapWith = secondTree;
}
}
console.log('swap tree ' + treeHeights[firstTree] + ' with ' +
treeHeights[swapWith] + ' to achieve H ' + minH + ' vs ' + H);
}
function swapHeights(index1, index2) {
var tmp = treeHeights[index1];
treeHeights[index1] = treeHeights[index2];
treeHeights[index2] = tmp;
}
function dH(index) {
return ((index === 0) || (index === N)) ?
0 :
Math.abs(treeHeights[index-1] - treeHeights[index]) + Math.abs(treeHeights[index] - treeHeights[index+1]);
}
}
// places([1,2,3,4,5])
// places([2,4,3,5,1])
// places([1])
// places([1,7])
places([5,72,3,111,32,85,1])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment