Project Euler 247

/**
 * Copyright uwi ( http://wonderfl.net/user/uwi )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/2F21
 */

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    import flash.events.*;
    // @see http://projecteuler.net/index.php?section=problems&id=247
    public class Euler247 extends Sprite {
        private var _tf : TextField;
  
        public function Euler247() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            _s = getTimer();
//            solve(1, 1);
            solve(3, 3); 
        }
        
        private var _s : int;

        /*
        private function solve(L : uint, D : uint) : Number
        {
        		var list : Array = [];
        		list.push({x:1, y:0, e:lenEdge(1, 0), left:0, down:0});
        		
        		var nUnder : uint = 1;
        		for(var i : uint = 0;nUnder > 0 && i < 50000;i++){
        			var o : * = list.pop(); 
        			if(o.left <= L && o.down <= D)nUnder--;
        			
        			insert(list, {x:o.x+o.e, y:o.y, e:lenEdge(o.x+o.e, o.y), left:o.left+1, down:o.down});
        			insert(list, {x:o.x, y:o.y+o.e, e:lenEdge(o.x, o.y+o.e), left:o.left, down:o.down+1});
        			if(o.left+1 <= L && o.down <= D)nUnder++;
        			if(o.left <= L && o.down+1 <= D)nUnder++;
        		}
        		tr(nUnder);
        		return i;
        }
        */
        
        private var _list : Array;
        private var _nUnder : uint;
        private var _i : uint;
        private var _L : uint;
        private var _D : uint;
        
        // 左下隅の座標が(a,b)のときの辺の長さは
        // (-(a+b)+√((a-b)^2+4))/2で表される。これの大きい順に見ていけばよい。
        // 2分探索→追加の繰り返しだが、これだけでは時間がかかりすぎる。
        // 
        // (a,b)=(3,3)となる最後のノードの番号を求めればいいので、
        // それ以降のノードは別に要らない。よって
        // (a,b)=(3,3)のなかでの辺の長さの最小値を求めておいて、
        // この最小値を下回った値が出てきたらリストに追加しないようにすると
        // 異常に速くなる。
        private function solve(L : uint, D : uint) : void
        {
        		_list = [];
        		_list.push({x:1, y:0, e:lenEdge(1, 0), left:0, down:0});
        		
        		_nUnder = 1;
        		_i = 0;
        		_L = L;
        		_D = D;
//        		tr(nUnder);
//        		return i;
			// (a,b)<=(L,D)での辺の長さの最小値を求める
        		for(;_list.length > 0;_i++){
        			var o : * = _list.pop(); 
        			if(o.left+1 <= _L && o.down <= _D){
	        			insert(_list, {x:o.x+o.e, y:o.y, e:lenEdge(o.x+o.e, o.y), left:o.left+1, down:o.down});
        			}
        			if(o.left <= _L && o.down+1 <= _D){
	        			insert(_list, {x:o.x, y:o.y+o.e, e:lenEdge(o.x, o.y+o.e), left:o.left, down:o.down+1});
        			}
        		}
        		_mine = o.e;
        		tr(_mine);
        		
        		_list = [];
        		_list.push({x:1, y:0, e:lenEdge(1, 0), left:0, down:0});
        		_nUnder = 1;
        		_i = 0;
        		
			addEventListener(Event.ENTER_FRAME, onEnterFrame);
	    }
        
        private var _mine : Number;
        
        private function onEnterFrame(e : Event) : void
        {
        		var targ : uint = _i + 50000;
        		for(;_nUnder > 0 && _i < targ;_i++){
        			var o : * = _list.pop(); 
        			if(o.left <= _L && o.down <= _D)_nUnder--;
        			
        			var le : Number;
        			le = lenEdge(o.x + o.e, o.y);
        			if(le >= _mine){
	        			insert(_list, {x:o.x+o.e, y:o.y, e:le, left:o.left+1, down:o.down});
//	        			insert(_list, {x:o.x+o.e, y:o.y, e:lenEdge(o.x+o.e, o.y), left:o.left+1, down:o.down});
	        			if(o.left+1 <= _L && o.down <= _D)_nUnder++;
        			}
        			le = lenEdge(o.x, o.y + o.e);
        			if(le >= _mine){
	        			insert(_list, {x:o.x, y:o.y+o.e, e:le, left:o.left, down:o.down+1});
//	        			insert(_list, {x:o.x, y:o.y+o.e, e:lenEdge(o.x, o.y+o.e), left:o.left, down:o.down+1});
	        			if(o.left <= _L && o.down+1 <= _D)_nUnder++;
        			}
        		}
        		tr(_i, _nUnder, (getTimer() - _s) + "ms");
        		if(_nUnder == 0){
        			removeEventListener(Event.ENTER_FRAME, onEnterFrame);
        		}
        }
        
        private function insert(a : Array, o : *) : void
        {
        		if(a.length == 0){
        			a.push(o);
        			return;
        		}
        		if(o.e < a[0].e){
        			a.splice(0, 0, o);
        			return;
        		}
        		/*
        		if(o.e > a[a.length - 1].e){
        			a.push(o);
        			return;
        		}
        		*/
        	
        		var start : uint = 0;
        		var end : uint = a.length;
        		while(end - start > 1){ 
        			var mid : uint = (start + end) >> 1;
        			if(o.e > a[mid].e){
        				start = mid;
        			}else{
        				end = mid;
        			}
        		}
//        		tr(a[start].e, o.e, start, a.length);
        		a.splice(start+1, 0, o);
        }
        
        private function lenEdge(a : Number, b : Number) : Number
        {
        		return (-(a+b)+Math.sqrt((a-b)*(a-b)+4))/2;
        }

        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
            _tf.scrollV = _tf.maxScrollV;
        }
    }
}