Project Euler 170

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

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=170
    public class Euler170 extends Sprite {
        private var _tf : TextField;
  
        public function Euler170() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            tr(solve());
            var g : int = getTimer();
            tr((g - s) + " ms");
        }

        // concatenated productの最上位の数字cを決めて、そこから、
        // ab = cとなるa,bを探す。そのあとa,b以外のinputと、
        // c以外のoutputを埋める組み合わせをみつける。
        // productの最大値を見つければよいため、
        // cの最上位の数字は9となるようにする。(98としてもよい)
        private function solve() : Number
        {
            var i : uint, j : uint, k : uint;
            for(i = 1023;i >= 1;i--){
                var a : Vector.<uint> = new Vector.<uint>();
                for(j = 0, k = i;j < 10;j++, k>>=1){
                    if(k & 1)a.push(j);
                }
                if(a.length >= 8)continue;
                for(;a != null; a = nextPermutation(a)){
                    if(a[0] != 9)continue;
//                    if(a.length > 1 && a[1] != 8)continue;
                    calcOrg(a);
                }
            }
            
            tr(_ct);
            return Number(_gopt);
        }
        
        private var _ct : uint = 0;
        private var _gopt : String = "";
        
        private function calcOrg(a : Vector.<uint>) : void
        {
            var ai : Number = 0;
            var code : uint = 0;
            for each(var e : uint in a){
                ai = ai * 10 + e; 
                code |= 1 << e;                
            }
            if(_gopt.substr(0, ai.toString().length) > ai.toString())return;
            
            for(var i : uint = 2;i * i < ai;i++){
                if(ai % i == 0){
                    var du : uint = isDup(i, ai / i);
                    if(du == 0)continue;
                    
                    var li : String;
                    li = ai + lookup(i, du, code);
                    if(li.length == 10){
                        tr(ai, i, li);
                        if(li > _gopt)_gopt = li;
                        _ct++;                        
                    }
                    li = ai + lookup(ai / i, du, code);
                    if(li.length == 10){
                        tr(ai, ai / i, li);
                        if(li > _gopt)_gopt = li;
                        _ct++;                        
                    }
                }
            }

        }
        
        private function isDup(...args : Array) : uint
        {
            var c : uint = 0;
            for each(var a : uint in args){
                while(a > 0){
                    if(c & (1 << (a % 10)))return 0;
                    c |= 1 << (a % 10);
                    a /= 10;
                }
            }
            return c;
        }
        
        private function lookup(base : uint, src : uint, dst : uint) : String
       {
            var ob : Object = {};
            
            var gct : uint = 0;
            var i : int, j : int, k : int;
            var ord : Array = [];
            for(k = 1;k < 1024;k++){
                if(src & k)continue;
                var a : Vector.<uint> = new Vector.<uint>();
                for(i = 0, j = k;i < 10;i++, j>>=1){
                    if((j & 1) == 1){
                        a.push(i);
                    } 
                }
                outera:
                for(;a != null; a = nextPermutation(a)){
                    if(a[0] == 0)continue;
                    var aa : uint = dec(a);
                    var count : uint = dst;
                    for(var r : Number = base * aa;r > 0;r = Math.floor(r / 10)){
                        var c : uint = 1 << (r % 10);
                        if(count & c)continue outera;
                        count |= c;
                    }
                    ord.push({mul : base * aa, src : k, dst : count ^ dst});
                    gct++;
                }
            }
//            tr(base, gct);
            
            ord.push({mul : 0, src : 1, dst : 1});
            ord.sortOn("mul", Array.DESCENDING);
            opt = "";
            rec(ord, src, dst, "", 0);
            return opt;
        }
        
        private var opt : String = "";
        
        // src, dstどちらも1023にする
        private function rec(ord : Array, src : uint, dst : uint, prev : String, depth : uint) : void
        {
            for(var i : uint = 0;i < ord.length;i++){
                if(src & ord[i].src)continue;
                if(dst & ord[i].dst)continue;
                var nsrc : uint = src | ord[i].src;
                var ndst : uint = dst | ord[i].dst;
                var cur : String = prev + ord[i].mul;
                if(nsrc != 1023 && ndst != 1023 && cur >= opt.substr(0, cur.length)){
                    rec(ord, nsrc, ndst, cur, depth + 1);
                }
                if(nsrc == 1023 && ndst == 1023){
                    if(cur > opt){
                        opt = cur;
                    }
                }
            }
        }
        
        private function dec(v : Vector.<uint>) : uint
        {
            var ret : uint = 0;
            for each(var u : int in v){
                ret = ret * 10 + u;
            }
            return ret;
        }

        private function nextPermutation(src : Vector.<uint>) : Vector.<uint>
        {
            for(var i : int = src.length - 2;i >= 0 && src[i] > src[i + 1];i--);
            if(i == -1)return null;
            for(var j : uint = i + 1;j < src.length && src[i] < src[j];j++);
            var d : uint;
            d = src[i]; src[i] = src[j - 1]; src[j - 1] = d;
            for(var p : uint = i + 1, q : uint = src.length - 1;p < q;p++, q--){
                d = src[p]; src[p] = src[q]; src[q] = d;
            }
            return src;
        }
        
            private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
            _tf.scrollV = _tf.maxScrollV;
        }
    }
}