15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* The Great Computer Language Shootout 25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) http://shootout.alioth.debian.org/ 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) contributed by Isaac Gouy */ 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function TreeNode(left,right,item){ 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.left = left; 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.right = right; 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.item = item; 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)TreeNode.prototype.itemCheck = function(){ 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.left==null) return this.item; 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else return this.item + this.left.itemCheck() - this.right.itemCheck(); 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function bottomUpTree(item,depth){ 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (depth>0){ 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return new TreeNode( 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) bottomUpTree(2*item-1, depth-1) 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ,bottomUpTree(2*item, depth-1) 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ,item 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ); 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else { 255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return new TreeNode(null,null,item); 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)var ret; 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)for ( var n = 4; n <= 7; n += 1 ) { 325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var minDepth = 4; 335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var maxDepth = Math.max(minDepth + 2, n); 345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var stretchDepth = maxDepth + 1; 355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var check = bottomUpTree(0,stretchDepth).itemCheck(); 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var longLivedTree = bottomUpTree(0,maxDepth); 395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var depth=minDepth; depth<=maxDepth; depth+=2){ 405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var iterations = 1 << (maxDepth - depth + minDepth); 415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) check = 0; 435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i=1; i<=iterations; i++){ 445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) check += bottomUpTree(i,depth).itemCheck(); 455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) check += bottomUpTree(-i,depth).itemCheck(); 465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ret = longLivedTree.itemCheck(); 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 51