Project Euler 147

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

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

        // 縦横と斜めの長方形に分けて考える。
        // w*hのとき、縦横の長方形の総数はw(w+1)h(h+1)/4
        // 斜めの場合はがんばって公式を出してもいいが、上限が小さいので
        // がんばって数える。
        // 斜めに座標系をとって、有効なブロックを列挙、その後、
        // 各ブロック*横幅*縦幅の4重ループで長方形を探す。
        // (W,H)単体ならこれで1秒以内で出るが、smallerも含むと時間がかかってしまう。
        //
        // そこで、斜めの長方形をカウントするとき、長方形の最大x,y座標を見て、
        // いくつのsmallerに対して同一位置の長方形が入るかを計算するようにする。
        private function solve(W : int, H : int) : Number
        {
            if(H > W){
                var d : int = W;
                W = H;
                H = d;
            }
            
            var i : int, j : int;
            
            // 縦横の長方形を数える
            var ret : Number = 0;
            for(i = 1;i <= W;i++){
                for(j = 1;j <= H;j++){
                    ret += i * (i + 1) / 2 * j * (j + 1) / 2;
                }
            }
            
            var f : Array = new Array(2 * W * 2 * W);
            
            // W >= H
            // 斜めの座標系をつくる
            for(i = 0;i < 2 * W;i++){
                for(j = 0;j < 2 * W;j++){
                    var x : Number = -0.5 * W + 0.5 * i + 0.5 * j + 0.5;
                    var y : Number = 0.5 * W - 0.5 * i + 0.5 * j;
                    if(x > 0 && x < W && y > 0 && y < H){
                        f[i * 2 * W + j] = 1;
                    }else{
                        f[i * 2 * W + j] = 0;
                    }
                }
            }
            
            // 斜めの長方形を数える。
            var ct : Number = 0;
            var w : int, h : int;
            for(i = 0;i < 2 * W;i++){
                for(j = 0;j < 2 * W;j++){
                    if(f[i * 2 * W + j] == 0)continue;
                    for(w = 0;w < 2 * W - i;w++){
                        for(h = 0;h < 2 * W - j;h++){
                            if(f[(i + w) * 2 * W + (j + h)] == 1 && f[i * 2 * W + j + h] == 1 && f[(i + w) * 2 * W + j] == 1){
                                var y1 : Number = 0.5 * W - 0.5 * i + 0.5 * (j + h);
                                var x2 : Number = -0.5 * W + 0.5 * (i + w) + 0.5 * (j + h) + 0.5;
//                                tr(i, j, w, h, y1, x2, Math.ceil(W - x2) * Math.ceil(H - y1)); 
                                ct += Math.ceil(W - x2) * Math.ceil(H - y1);
                            }else{
                                break;
                            } 
                        }
                    }
                }
            }            
            return ret + ct;
        }
            
        private function calc(W : int, H : int) : int
        {
            if(H > W){
                var d : int = W;
                W = H;
                H = d;
            }
            var sum : int = W * (W + 1) / 2 * H * (H + 1) / 2;
            
            var f : Array = new Array(2 * W * 2 * W);
            
            // W >= H
            var i : int, j : int;
            for(i = 0;i < 2 * W;i++){
                for(j = 0;j < 2 * W;j++){
                    var x : Number = -0.5 * W + 0.5 * i + 0.5 * j + 0.5;
                    var y : Number = 0.5 * W - 0.5 * i + 0.5 * j;
                    if(x > 0 && x < W && y > 0 && y < H){
//                        tr(i, j, x, y);
                        f[i * 2 * W + j] = 1;
                    }else{
                        f[i * 2 * W + j] = 0;
                    }
                }
            }
            
            var ct : int = 0;
            var w : int, h : int;
            var a : Array = [];
            for(i = 0;i < 2 * W;i++){
                for(j = 0;j < 2 * W;j++){
                    if(f[i * 2 * W + j] == 0)continue;
                    for(w = 0;w < 2 * W - i;w++){
                        for(h = 0;h < 2 * W - j;h++){
                            if(f[(i + w) * 2 * W + (j + h)] == 1 && f[i * 2 * W + j + h] == 1 && f[(i + w) * 2 * W + j] == 1){
                                ct++;
                                var y1 : Number = 0.5 * W - 0.5 * i + 0.5 * (j + h);
                                var x2 : Number = -0.5 * W + 0.5 * (i + w) + 0.5 * (j + h) + 0.5;
                                a.push([y1, x2]);
                            }else{
                                break;
                            } 
                        }
                    }
                }
            }
            return sum + ct;
        }

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