awkで小町算

awk

さて、いよいよawkで小町算も大詰めを迎えようとしております。
今回も広井さんのサイトからです。いつも提供ありがとうございます。

www.geocities.jp

 [問題１] 小町算

1 から 9 までの数字を順番に並べ、間に + と - を補って 100 になる式を作ってください。

例：1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100

一番やりたかった問題です。
なかなか自分の頭で考えても出来なったので広井さんのサイトにあるC言語バージョンをそのままawkに書き直してみました。 ただし、switch文を使っているのでgawk専用です。 以下、ソース

#!/usr/bin/gawk -f
# 小町算

BEGIN{
    buff[0] = 1;
    make_expr(2,1,buff);
}
# 式の計算
function calc_expr(buff,x){
    sum = buff[0];
    for(i = 1;i < x; i+= 2){
        switch(buff[i]){
            case "+":
            sum += buff[i + 1];
            break;
            case "-":
            sum -= buff[i + 1];
            break;
            default:
            printf("not operator",buff[i]);
        }
    }
    return sum;
}

# 式の表示
function print_expr(buff,x){
    buff[x] = "=";
    for(i = 0;i < x;i += 2){
        printf("%d %c ",buff[i], buff[i + 1]);
    }
    printf("100\n");
}

# 式の生成
function make_expr(n,x,buff){
    if(n == 10){
        if(calc_expr(buff,x) == 100){
            print_expr(buff,x);
        }
    }else{
        buff[x] = "+";
        buff[x + 1] = n;
        make_expr(n + 1,x + 2,buff);
        buff[x] = "-";
        buff[x + 1] = n;
        make_expr(n + 1, x + 2,buff);
        temp = buff[x - 1];
        buff[x - 1] = buff[x - 1] * 10 + n;
        make_expr(n + 1,x ,buff);
        buff[x - 1] = temp;
    }
}

実行してみます。

$ awk -f komachi.awk 
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
1 + 2 + 34 - 5 + 67 - 8 + 9 = 100
1 + 23 - 4 + 5 + 6 + 78 - 9 = 100
1 + 23 - 4 + 56 + 7 + 8 + 9 = 100
12 + 3 + 4 + 5 - 6 - 7 + 89 = 100
12 + 3 - 4 + 5 + 67 + 8 + 9 = 100
12 - 3 - 4 + 5 - 6 + 7 + 89 = 100
123 + 4 - 5 + 67 - 89 = 100
123 + 45 - 67 + 8 - 9 = 100
123 - 4 - 5 - 6 - 7 + 8 - 9 = 100
123 - 45 - 67 + 89 = 100

C言語とawkって文法が似ているから、このような処理の場合、移植は楽ですね。
相変わらず式の理解が追いついていないので、しっかり勉強したいと思います。