Project Euler 161

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

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

        private function solve(w : uint, h : uint) : Array
        {
        		var base : Array = new Array(w);
        		for(var i : uint = 0;i < w;i++)base[i] = 0;
        		_cache = {};
        		
			_lim = h * w / 3;
        		return rec(base, h, 0);
        }
        
        private var _lim : Number;
        
        // 長方形のなかを、垂直でみたときに間があかないように左下から埋めて行く方針
        private function rec(a : Array, h : uint, ct : uint) : Array
        {
        		if(ct == _lim)return [1, 0];
        		
        		var code : Number = 0;
        		for(var i : uint = 0;i < a.length;i++){
        			code = code * (h + 1) + a[i];
        		}
        		if(_cache[code])return _cache[code];
        		
        		var min : uint = uint.MAX_VALUE;
        		var mi : uint = uint.MAX_VALUE;
        		for(i = 0;i < a.length;i++){
        			if(a[i] < min){
        				min = a[i];
        				mi = i;
        			}
        		}
        		
        		var sum : Array = [0, 0];
        		
        		// タテ3
        		if(min + 3 <= h){
        			a[mi] += 3;
        			sum = N2.add(sum, rec(a, h, ct + 1));
//        			sum += rec(a, h, ct + 1);
        			a[mi] -= 3;
        		}
        		
        		// ヨコ3
        		if(mi+2 < a.length && 
        			a[mi+1] == min && a[mi+2] == min &&
        			min + 1 <= h){
        			a[mi]++; a[mi+1]++; a[mi+2]++;
        			sum = N2.add(sum, rec(a, h, ct + 1));
//        			sum += rec(a, h, ct + 1);
        			a[mi]--; a[mi+1]--; a[mi+2]--;
    			}
    			
    			// □□
    			// □
    			if(mi+1 < a.length &&
    				a[mi+1] == min + 1 &&
    				min+2 <= h){
    				a[mi] += 2; a[mi+1]++;
        			sum = N2.add(sum, rec(a, h, ct + 1));
//        			sum += rec(a, h, ct + 1);
    				a[mi] -= 2; a[mi+1]--;
    			}
    			
    			// 上のパターンで最初にこれないやつ
    			// 2, 2, 2
        		if(mi+2 < a.length && 
        			a[mi+1] == min && a[mi+2] == min &&
        			min + 2 <= h){
        			a[mi]+=2; a[mi+1]+=2; a[mi+2]+=2;
        			sum = N2.add(sum, rec(a, h, ct + 2));
//        			sum += rec(a, h, ct + 2);
        			a[mi]-=2; a[mi+1]-=2; a[mi+2]-=2;
    			}
    			
    			// 2, 2, 1, 1
        		if(mi+3 < a.length && 
        			a[mi+1] == min && a[mi+2] == min && a[mi+3] == min &&
        			min + 2 <= h){
        			a[mi]+=2; a[mi+1]+=2; a[mi+2]++; a[mi+3]++;
        			sum = N2.add(sum, rec(a, h, ct + 2));
//        			sum += rec(a, h, ct + 2);
        			a[mi]-=2; a[mi+1]-=2; a[mi+2]--; a[mi+3]--;
    			}
    			
    				
    			// □
    			// □□
    			if(mi+1 < a.length &&
    				a[mi+1] == min &&
    				min+2 <= h){
    				a[mi] += 2; a[mi+1]++;
        			sum = N2.add(sum, rec(a, h, ct + 1));
//        			sum += rec(a, h, ct + 1);
    				a[mi] -= 2; a[mi+1]--;
    			}
    				
    			//  □
    			// □□
    			if(mi+1 < a.length &&
    				a[mi+1] == min &&
    				min+2 <= h){
    				a[mi]++; a[mi+1] += 2;
        			sum = N2.add(sum, rec(a, h, ct + 1));
//        			sum += rec(a, h, ct + 1);
    				a[mi]--; a[mi+1] -= 2;
    			}
    				
    			// □□
    			//  □
    			if(mi >= 1 &&
    				a[mi-1] == min + 1 &&
    				min+2 <= h){
    				a[mi] += 2; a[mi-1]++;
        			sum = N2.add(sum, rec(a, h, ct + 1));
//        			sum += rec(a, h, ct + 1);
    				a[mi] -= 2; a[mi-1]--;
    			}
        		
        		_ct++;
//        		if(sum > 0)tr(a, sum);
        		_cache[code] = sum;
        		return sum;
        }
        
        private var _ct : uint = 0;

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

class N2{
	public static const N : Number = 1E15;	
	public static function add(a : Array, b : Array) : Array
	{
		var r0 : Number = a[0] + b[0];
		var rp : int = Math.floor(r0 / N);
		r0 -= rp * N;
		var r1 : Number = a[1] + b[1] + rp;
		return [r0, r1];
	}
	
	public static function sub(a : Array, b : Array) : Array
	{
		var r0 : Number = a[0] - b[0];
		var rp : int = Math.floor(r0 / N);
		r0 -= rp * N;
		var r1 : Number = a[1] - b[1] + rp;
		return [r0, r1];
	}
	
	public static function inc(a : Array, b : Number) : Array
	{
		var r0 : Number = a[0] + b;
		var rp : int = Math.floor(r0 / N);
		r0 -= rp * N;
		var r1 : Number = a[1] + rp;
		
		a[0] = r0;
		a[1] = r1;
		return a;
	}
}