flash on 2009-11-15

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

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();
            tr(solve(200000));
            var g : int = getTimer();
            tr((g - s) + " ms");
        }
        
        private var _base : Array;
        private var _5k : Array;
        private var _sat : Array;

        private function solve(N : int) : Number
        {
            _base = [0];
            _5k = [1];
            for(var m : int = 5;m < N;m *= 5){
                _base.push(N % m);
                _5k.push(m);
                tr(N % m, m);
            }
            
            var ret : Number = 0;
            var M : int = _base.length - 1;
            var i : int, j : int, k : int;
            for(i = Math.pow(3, M)-1;i >= 0;i--){
                var sum : int = 0;
                for(j = i;j > 0;j /= 3)sum += j % 3;
                if(sum >= 12){
                    _sat = [];
                    for(k = 0, j = i;k < M;k++, j /= 3)_sat.push(j % 3);
                    
                    var res : int = 0;
                    var mul : Number = 1;
                    for(j = 0, k = 5;j < M;j++, k *= 5){
                        var v : int = _base[j + 1] + _sat[j] * k;
                        var ind : int = (v - res) * 5 / k;
                        if(ind < 0 || ind >= 13){
                            mul = 0;
                            break;
                        }
//                        tr(v, ind);
                        mul *= NUM[ind];
                        res = v;
                    }
                    tr(_sat, mul);
                    ret += mul;
//                    ret += rec(1, 0, 0, 0);
                }
            }
            
            return ret;
        }
        
        private const NUM : Array = [1, 3, 6, 10, 15, 18, 19, 18, 15, 10, 6, 3, 1];
        
        private function rec(pos : int, a : int, b : int, c : int) : Number
        {
            /*
            if(pos == 8){
                return left <= 0 ? 1 : 0;
            }
            */
            
            var i : int = _sat[pos - 1];
                var l : int = _base[pos] + _5k[pos] * i - (a + b + c);
                if(l < 0)return 0;
                
                l /= _5k[pos - 1];
                if(pos == 7){
                    return NUM[l];
                }
                
                var ret : Number = 0;
                var aa : int, bb : int;
                for(aa = 0;aa <= 4;aa++){
                    for(bb = 0;bb <= 4;bb++){
                        var cc : int = l - aa - bb;
                        if(cc < 0 || cc > 4)continue;
                        ret += rec(pos + 1,
                            a + aa * _5k[pos - 1],
                            b + bb * _5k[pos - 1],
                            c + cc * _5k[pos - 1]
                            );
                    }
                }
            return ret;
        }

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