forked from: flash on 2009-8-17

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

// forked from uwi's flash on 2009-8-17
package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=
    public class Euler extends Sprite {
        private var _tf : TextField;
  
        public function Euler() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            t(solve(10));
            var g : int = getTimer();
            t((g - s) + " ms");
        }
        
        private var _caches : Array;
        private var _cachep : Array;
        private var _splits : Array;

        // S := P | SP
        // P := P/S
        private function solve(M : int) : int
        {
            _splits = new Array(19);
            var i : int;
            // 18でも400個弱
            for(i = 0;i <= 18;i++){
                _splits[i] = divide(i, i);
            }
            
            _caches = new Array(M + 1);
            _cachep = new Array(M + 1);
            
            var ret : Object = {};
            var v : Number;
            
            for(i = 1;i <= M;i++){
                for each(v in s(i)){
                    ret[v] = v;
                }
            }
            
            var ct : int = 0;
            for each(v in ret){
//                t(v);
                ct++;
            }
            return ct;
        }
        
        private function divide(n : int, lim : int) : Array
        {
            if(n == 1)return [[1]];
            if(n == 0)return [[]];
            var ret : Array = [];
            for(var i : int = 1;i <= lim && i <= n;i++){
                for each(var val : Array in divide(n - i, i)){
//                    ret.push(val.concat(i));
                    ret.push([i].concat(val));
                }
            }
            return ret;
        }
        
        private function s(n : int) : Object
        {
            if(n <= 1)return {1:1};
            if(_caches[n])return _caches[n];
            
            var ret : Object = {};
            var v : Number;
            
            for each(var sp : Array in _splits[n]){
                var prev : Array = [];
                
                var first : Boolean = true;
                for each(var vs : int in sp){
                    if(first){
                    for each(var rs : Number in p(vs)){
                        prev.push(rs);
                    }
                        first = false;
                        continue;
                    }
                    var cur : Array = [];
                    for each(var rs : Number in p(vs)){
                        for each(var vp : Number in prev){
                            v = rs * vp / (rs + vp);
                            cur.push(v);
                        }
                    }
                    prev = cur;
                }
                
                for each(v in prev)ret[v] = v;
            }
            _caches[n] = ret;
            
            return ret;
        }

        private function p(n : int) : Object
        {
            if(n <= 1)return [1];
            if(_cachep[n])return _cachep[n];
            
            var ret : Object = {};
            var v : Number;
            
            for each(var sp : Array in _splits[n]){
                if(sp[0] == n)continue;
                var prev : Array = [0];
                
                for each(var vs : int in sp){
                    var cur : Array = [];
                    for each(var rs : Number in s(vs)){
                    for each(var vp : Number in prev){
                        v = rs + vp;
                        cur.push(v);
                    }}
                    prev = cur;
                }
                
                for each(v in prev)ret[v] = v;
            }
            _cachep[n] = ret;
            
            return ret;
        }

	private function t(o : *) : void
	{
            _tf.appendText("" + o + "\n");
	}
    }
}