Project Euler 209

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

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=209
    public class Euler209 extends Sprite {
        private var _tf : TextField;
  
        public function Euler209() {
            _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");
        }
        
        private var _link : Array;

        private function solve() : Number
        {
            // リンク構成
            _link = new Array(64);
            var i : int;
            for(i = 0;i < 64;i++){
                _link[i] = [];
            }
            for(i = 0;i < 64;i++){
                var a : int = (i >> 5) & 1;
                var b : int = (i >> 4) & 1;
                var c : int = (i >> 3) & 1;
                var j : int = ((i & 31) << 1) | (a ^ (b & c));
                _link[i].push(j);
                _link[j].push(i);
            }
            
            // 環を抽出
            var rest : Array = new Array(64);
            var loops : Array = [];
            for(i = 0;i < 64;i++){
                if(rest[i])continue;
                var nex : Array = [i];
                var his : Object = {};
                his[i] = i;
                while(nex.length >= 1){
                    var v : int = nex.pop();
                    if(!rest[v]){
                        rest[v] = 1;
                        for each(var w : int in _link[v]){
                            nex.push(w);
                            his[w] = w;
                        }
                    }
                }
                
                var ct : int = 0;
                for each(var u : int in his){
                    tr(u,_link[u]);
                    ct++;
                }
                tr();
                loops.push(ct);
            }
            
            // 環の組み合わせをかける
            var ret : Number = 1;
            for each(var l : int in loops){
                tr(l);
                ret *= nLoop(l);
            }
            
            return ret;
        }
        
        private var _cache : Array;
        
        private function nLoop(n : int) : Number
        {
            if(n == 1)return 1;
            _cache = new Array((n + 1) * 2 * 2);
            return rec(n - 1, 0, 0) + rec(n - 1, 1, 1);
        }
        
        private function rec(pos : int, start : int, prev : int) : Number
        {
            if(pos == 1){
                return (prev == 1 || start == 1) ? 1 : 2;
            }
            var code : int = (pos << 2) | (start << 1) | prev;
            if(_cache[code])return _cache[code];
            
            var ret : Number = rec(pos - 1, start, 0) + (prev == 0 ? rec(pos - 1, start, 1) : 0);
            _cache[code] = ret;
            return ret;
        }

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