Project Euler 215

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

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

        private function solve(M : int, N : int) : Number
        {
            var a : Array = rec(M, 0);
            
            var canrides : Array = [];
            var i : int, j : int;
            for(j = 0;j < a.length;j++){
                var canride : Array = [];
                for(i = 0;i < a.length;i++){
                    if(i == j)continue;
                    if((a[j] & a[i]) == 0){
                        canride.push(i);
                    }
                }
                canrides.push(canride);
            }
            
            _cache2 = new Array(N);
            for(i = 0;i < N;i++){
                _cache2[i] = new Array(a.length);
            }
            
            var sum : Number = 0;
            for(i = 0;i < a.length;i++){
                sum += rec2(N, 1, i, canrides);
            }
            return sum;
            
            /*
            var canrides : Array = [];
            var filter : Array = new Array(M);
            var i : int, j : int;
            for(j = 0;j < a.length;j++){
                var aa : Array = a[j];
                for(i = 0;i < M;i++)filter[i] = 0;
                for(i = 0;i < aa.length;i++){
                    filter[aa[i]] = 1;
                }
                
                var canride : Array = [];
                for(i = 0;i < a.length;i++){
                    if(i == j)continue;
                    var f : Boolean = true;
                    for each(var v : int in a[i]){
                        if(filter[v] == 1){
                            f = false;
                            break;
                        }
                    }
                    if(f){
                        canride.push(i);
                    }
                }
                canrides.push(canride);
            }
            */
//            t(canrides);
            return 0;
        }
        
        private function rec2(N : int, pos : int, prev : int, canrides : Array) : Number
        {
            if(pos == N)return 1;
            if(_cache2[pos][prev])return _cache2[pos][prev];
            var ret : Number = 0;
            for each(var v : int in canrides[prev]){
                ret += rec2(N, pos + 1, v, canrides);
            }
            _cache2[pos][prev] = ret;
            return ret;
        }
        
        private function rec(M : int, pos : int) : Array
        {
            if(pos > M)return [];
            if(pos == M)return [0];
            if(_cache[pos])return _cache[pos];
            
            var ret : Array = [];
            var cut : uint;
            if(pos == 0){
                ret = rec(M, pos + 2).concat(rec(M, pos + 3));
            }else{
                var added : uint = 1 << (pos - 1);
                for each(cut in rec(M, pos + 2)){
                    ret.push(cut | added);
                }
                for each(cut in rec(M, pos + 3)){
                    ret.push(cut | added);
                }
                _cache[pos] = ret;
            }
            return ret;
        }
        
        /*
        private function rec(M : int, pos : int) : Array
        {
            if(pos > M)return [];
            if(pos == M)return [[]];
            if(_cache[pos])return _cache[pos];
            
            var ret : Array = [];
            var cut : Array;
            var added : Array = [pos];
            if(pos == 0){
                ret = rec(M, pos + 2).concat(rec(M, pos + 3));
            }else{
                for each(cut in rec(M, pos + 2)){
                    ret.push(cut.concat(added));
                }
                for each(cut in rec(M, pos + 3)){
                    ret.push(cut.concat(added));
                }
                _cache[pos] = ret;
            }
            return ret;
        }
        */

/*
        private function rec(M : int, pos : int) : Number
        {
            if(pos > M)return 0;
            if(pos == M)return 1;
            if(_cache[pos])return _cache[pos];
            
            var ret : Number = rec(M, pos + 2) + rec(M, pos + 3);
            _cache[pos] = ret;
            return ret;
        }
*/

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