flash on 2010-4-13

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

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    
    // @see http://www.itmedia.co.jp/enterprise/articles/1002/06/news001.html
    // 3人の宣教師と、3人の先住民が川岸にいる。
    // 2人まで乗れるボートがあり、ボートをこげるのはある先住民1人と宣教師1人だけである。
    // どちらかの岸で先住民が宣教師より多くなってしまうと、
    // 先住民が宣教師を襲ってしまう。
    // 無事全員で渡り切るにはどうすればよいかを出力しなさい。
    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());
            var g : int = getTimer();
            tr((g - s) + " ms");
        }

        private function solve() : Array
        {
        		_cache = new Array(4 * 4 * 2 * 2 * 2);
//        		for(var i : uint = 0;i < _cache.length;i++)_cache[i] = 0;
        		_passed = new Array(4 * 4 * 2 * 2 * 2);
        		
        		var ret : Array = rec(0, 0, 0, 0, 0);
        		ret.reverse();
        		return ret;
        }
        
        private var _cache : Array;
        private var _passed : Array;
        
        // a:宣教師(s), b:先住民(n)
        // c:ある宣教師(S), d:ある先住民(N)
        // dir:0,1
        private function rec(a : uint, b : uint, c : uint, d : uint, dir : uint) : Array
        {
        		if(a < 0 || a > 3 || b < 0 || b > 3)return null;
        		if(a == 3 && b == 3)return [];
        		if(a > 0 && a < b)return null;
        		if(3-a > 0 && 3-a < 3-b)return null;
        		
        		var code : uint = (((a * 4 + b) * 2 + c) * 2 + d) * 2 + dir;
        		if(_passed[code])return null;
        		if(_cache[code]){
        			return _cache[code] == 1 ? null : _cache[code];
        		}
        		_passed[code] = 1;
        		
        		var ret : Array = null;
        		var val : Array;
        		if(dir == 0){
        			if(c == 0){
        				ret = add(ret, rec(a+2, b, 1, d, 1), "Ss->");
        				ret = add(ret, rec(a+1, b+1, 1, d, 1), "Sn->");
        				ret = add(ret, rec(a+1, b, 1, d, 1), "S->");
        			}
        			if(d == 0){
        				ret = add(ret, rec(a+1, b+1, c, 1, 1), "Ns->");
        				ret = add(ret, rec(a, b+2, c, 1, 1), "Nn->");
        				ret = add(ret, rec(a, b+1, c, 1, 1), "N->");
        			}
        			if(c == 0 && d == 0){
        				ret = add(ret, rec(a+1, b+1, 1, 1, 1), "SN->");
        			}
        		}else{
        			if(c == 1){
        				ret = add(ret, rec(a-2, b, 0, d, 0), "Ss<-");
        				ret = add(ret, rec(a-1, b-1, 0, d, 0), "Sn<-");
        				ret = add(ret, rec(a-1, b, 0, d, 0), "S<-");
        			}
        			if(d == 1){
        				ret = add(ret, rec(a-1, b-1, c, 0, 0), "Ns<-");
        				ret = add(ret, rec(a, b-2, c, 0, 0), "Nn<-");
        				ret = add(ret, rec(a, b-1, c, 0, 0), "N<-");
        			}
        			if(c == 1 && d == 1){
        				ret = add(ret, rec(a-1, b-1, 0, 0, 0), "SN<-");
        			}
        		}
        		_passed[code] = 0;
        		_cache[code] = ret ? ret : 1;
        		
        		return ret;
        }
        
        private function add(ret : Array, val : Array, str : String) : Array
        {
        		if(val != null && (ret == null || ret.length > val.length + 1)){
        			val.push(str);
        			return val;
        		}
        		return ret;
        }

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