Project Euler 189

@see http://projecteuler.net/index.php?section=problems&id=189

forked:0
favorite:0
lines:91
license : MIT License
modified : 2010-03-18 22:08:11

Embed: Tweet

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

// 一番上の三角形からはじめて、下へ、左右へ、の繰り返しDP.
        // 色付けを4進数で表わしてカウントしていく。
        private function solve() : Number
        {
        		var c : Array = new Array(1 << (1 * 2));
        		var i : uint;
        		c[0] = 1; c[1] = 1; c[2] = 1; c[3] = 0;
        		for(i = 1;i <= 7;i++){
	        		c = stepD(c, i);
	        		c = stepLR(c, i+1);
        		}
        		
        		var sum : Number = 0;
        		for each(var v : Number in c){
        			sum += v;
        		}
        		return sum;
        }
        
        private function stepD(c : Array, n : uint) : Array
        {
        		var d : Array = new Array(1 << (n * 2));
        		var i : uint, j : uint, k : uint;
        		for(i = 0;i < d.length;i++)d[i] = 0;
        		
        		for(i = 0;i < c.length;i++){
        			if(c[i] > 0){
        				var seeds : Array = [0];
        				for(j = 0;j < n;j++){
        					var newseeds : Array = [];
        					var u : uint = (i >> (j * 2)) & 3;
        					for each(var seed : uint in seeds){
        						for(k = 0;k <= 2;k++){
        							if(u == k)continue;
        							newseeds.push(seed | (k << (j * 2)));
        						}
        					}
        					seeds = newseeds;
        				}
        				for each(seed in seeds){
        					d[seed] += c[i];
        				}
        			}
        		}
        		return d;
        }
        
        private function stepLR(c : Array, n : uint) : Array
        {
        		var d : Array = new Array(1 << (n * 2));
        		var i : uint, j : uint, k : uint;
        		for(i = 0;i < d.length;i++)d[i] = 0;
        		
        		for(i = 0;i < c.length;i++){
        			if(c[i] > 0){
        				var seeds : Array = [0];
        				for(j = 0;j < n;j++){
        					var newseeds : Array = [];
        					var l : uint = j >= 1 ? (i >> ((j - 1) * 2)) & 3 : 999;
        					var r : uint = j < n - 1 ? (i >> (j * 2)) & 3 : 999;
        					for each(var seed : uint in seeds){
        						for(k = 0;k <= 2;k++){
        							if(k == l || k == r)continue;
        							newseeds.push(seed | (k << (j * 2)));
        						}
        					}
        					seeds = newseeds;
        				}
        				for each(seed in seeds){
        					d[seed] += c[i];
        				}
        			}
        		}
        		return d;
        }

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

Code Fullscreen

Preview Fullscreen