2010 年小町算

小町算 - Wikipedia の結果は通常 100 になるように求めますが、2010 年にちなんで 2010 になるものを求めてみます。

ただし、以下のプログラムは決して良い例とは言えないので、良い方法があれば書き換えます。(このあたりはアルゴリズムの勉強が自分に不足していると反省)

  • 四則演算のみを使います
  • 括弧には対応しません
  • 1 桁の数字同士の四則演算では 2010 にならないので複数桁も含めます
  • awk には eval がないので、自力で中期記法を解きます
#! /usr/local/bin/nawk -f
# komachi.awk
# 小町算を解く
# usage: nawk -f komachi.awk [num]

BEGIN {
    target = ARGV[1] ? ARGV[1] : 100;

    max = split("+ - * / _", ops);

    for (a = 1; a <= max; a++) {
        for (b = 1; b <= max; b++) {
            for (c = 1; c <= max; c++) {
                for (d = 1; d <= max; d++) {
                    for (e = 1; e <= max; e++) {
                        for (f = 1; f <= max; f++) {
                            for (g = 1; g <= max; g++) {
                                for (h = 1; h <= max; h++) {
                                    eqn = 1 " " ops[a] " " 2 " " ops[b] " "\
                                          3 " " ops[c] " " 4 " " ops[d] " "\
                                          5 " " ops[e] " " 6 " " ops[f] " "\
                                          7 " " ops[g] " " 8 " " ops[h] " " 9;
                                    gsub(/ +_ +/, "", eqn);
                                    meqn = -1 " " ops[a] " " 2 " " ops[b] " "\
                                            3 " " ops[c] " " 4 " " ops[d] " "\
                                            5 " " ops[e] " " 6 " " ops[f] " "\
                                            7 " " ops[g] " " 8 " " ops[h] " " 9;
                                    gsub(/ +_ +/, "", meqn);

                                    if (eval(eqn) == target) {
                                        print eqn " = " target;
                                    }

                                    if (eval(meqn) == target) {
                                        print meqn " = " target;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

function eval(eqn) {
    split(eqn, term, /[ ]+/);

    for (idx in term) {
        term_num++;
    }

    i = 1;

    return expr();
}

function expr(    e) {
    e = terms();

    while (term[i] == "+" || term[i] == "-") {
        e = term[i++] == "+" ? e + terms() : e - terms();
    }

    return e;
}

function terms(    e) {
    e = factor();

    while (term[i] == "*" || term[i] == "/") {
        e = term[i++] == "*" ? e * factor() : e / factor();
    }

    return e;
}

function factor(    e) {
    if (term[i] ~ /^[+-]?([0-9]+[.]?[0-9]*|[.][0-9]+$)/) {
        return term[i++];
    } else if (term[i] == "("){
        i++;
        e = expr();
        i++;
        return e;
    } else {
        return 0;
    }
}

実行してみます。

$ time mawk -f komachi.awk 2010
1 + 2 / 3 * 45 * 67 + 8 - 9 = 2010
-1 + 2 / 3 * 45 * 67 - 8 + 9 = 2010
1 + 2345 * 6 / 7 + 8 - 9 = 2010
-1 + 2345 * 6 / 7 - 8 + 9 = 2010
-1 - 2 - 3 + 4 * 567 * 8 / 9 = 2010
-1 * 2 * 3 + 4 * 567 * 8 / 9 = 2010
12 * 34 * 5 + 6 * 7 - 8 * 9 = 2010
12 * 34 * 5 - 6 - 7 - 8 - 9 = 2010
mawk -f komachi.awk 2010  16.09s user 0.01s system 98% cpu 16.405 total

時間がかかっているのは eval を自前で行う部分が大きく効いていると思います。

tag_nawk.png tag_nawk.png tag_nawk.png tag_nawk.png