Swap trees.js

swap-tress.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])