2010を1~9の+-*で表す

by uwi 14 Jan 2010
Embed
/**
 * Copyright uwi ( http://wonderfl.net/user/uwi )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/cSLN
 */

// forked from uwi's 2010を1~9の四則演算で表す
package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    import flash.events.*;
    import com.bit101.components.*;
    
    public class Test extends Sprite {
        private var _tf : TextField;
  
        private const OPES : Array = ["+", "-", "*"];
        private var _ct : uint;
        private var _p : Array = [0, 1, 2, 3, 4, 5, 6, 7]; // 順列用
        private var _set : Object = {};
        private const N : int = 2010;
        private const STEP : uint = 100;
        
        // ネタ
        private var _pb : Meter;
        private var _il : IndicatorLight;
  
        public function Test() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf); 
            
            _pb = new Meter(this, 250, 0, "Progress");
            _pb.maximum = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1;
            
            _il = new IndicatorLight(this, 250, 100, 0xffff00, "Finished");
            _il.isLit = false;
            
            _ct = 0;
            addEventListener(Event.ENTER_FRAME, onEnterFrame);
        }
        
        private var _step : uint = 0;
        
        private function onEnterFrame(e : Event) : void
        {
            for(var i : uint = 0;i < STEP;i++){
                if(process()){
                    removeEventListener(Event.ENTER_FRAME, onEnterFrame);
                    tr(_ct);
                    _pb.value = _pb.maximum;
                    _il.isLit = true;
                    return;
                }
            }
            _step += STEP;
            _pb.value = _step;
        }
        
        private function process() : Boolean
        {
            var i : uint, j : uint, k : int;
            
            var inds : Array = _p.concat(); // 結合後インデックス
            var cur : Array = [[1], [2], [3], [4], [5], [6], [7], [8], [9]];
            var hist : Array = []; // 逆算用履歴
            for(i = 0;i < inds.length;i++){
                // 結合後のインデックスに直す
                for(j = i + 1;j < inds.length;j++){
                    if(inds[j] > inds[i])inds[j]--;
                }
                
                // 隣同士を結合させていく
                var next : Array = [];
                for each(var a : Number in cur[inds[i]]){
                    for each(var b : Number in cur[inds[i]+1]){
                        next.push(a+b, a-b, a*b);
//                        next.push(a+b, a-b, a*b, a/b);
//                        next.push(a+b, a-b, a*b, 10*a+b);
                    }
                }
                hist.push(cur[inds[i]+1].length);
                cur.splice(inds[i], 2, next);
            }
                
            for(j = 0;j < cur[0].length;j++){
                if(cur[0][j] == N){
                    // 逆算して演算子を割り出す
                    var q : Array = new Array(9);
                    var c : Array = [j];
                    for(k = inds.length - 1;k >= 0;k--){
                        q[k] = c[inds[k]] % 3;
                        var n : uint = c[inds[k]] / 3;
                        c.splice(inds[k], 1, uint(n / hist[k]), n % hist[k]);
                    }
                        
                    // 数式をくっつける
                    var strs : Array = ["1", "2", "3", "4", "5", "6", "7", "8", "9"];
                    var methods : Array = [-1, -1, -1, -1, -1, -1, -1, -1]; // 直前の演算子
                    for(k = 0;k < inds.length;k++){
                        if(q[k] >= 1){
                            // +以外でくっつけるとき、くっつけようとしている要素が+-で結合している場合はカッコで囲む
                            if(q[k] >= 2 && methods[inds[k]] >= 0 && methods[inds[k]] <= 1){
                                strs[inds[k]] = "(" + strs[inds[k]] + ")";
                            }
                            if(methods[inds[k]+1] >= 0 && methods[inds[k]+1] <= 1){
                                strs[inds[k]+1] = "(" + strs[inds[k]+1] + ")";
                            }
                        }
                        var nexstr : String = strs[inds[k]] + OPES[q[k]] + strs[inds[k]+1];
                        strs.splice(inds[k], 2, nexstr);
                        methods.splice(inds[k], 2, q[k]);
                    }
                        
                    // 既出か確認
                    if(!_set[strs[0]]){
                        _set[strs[0]] = 1;
                        tr(strs[0]);
                        _ct++;
                    }
                }
            }
                
            return nextPermutation(_p) == null;
        }

        // 次の順列を出す
        private static function nextPermutation(src : Array) : Array
        {
            for(var i : int = src.length - 2;i >= 0 && src[i] > src[i + 1];i--);
            if(i == -1)return null;
            for(var j : int = i + 1;j < src.length && src[i] < src[j];j++);
            var d : int;
            d = src[i]; src[i] = src[j - 1]; src[j - 1] = d;
            for(var p : int = i + 1, q : int = src.length - 1;p < q;p++, q--){
                d = src[p]; src[p] = src[q]; src[q] = d;
            }
            return src;
        }
        
        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
            _tf.scrollV = _tf.maxScrollV;
        }
    }
}