初心者用課題

プログラミングスレまとめ in VIP - 初心者用課題 を解いてみます。 名前は「初心者用」となっていますが、アルゴリズムを知っていないと難しいものもありますので、アルゴリズムの勉強にもなると思います。

解いていくと、AWK Users JP :: AWK ならどう書く? の中で取り上げた課題とダブる部分が多いことに気が付くと思います。 また、課題のとおりでない部分もありますが、参考にしてみてください。

ループ練習

これは任意の数だけ回るループを組めば良いので、for 文で作成しています。

また、以後の課題も同じですが、デフォルトの引数を持ちたいということもあり、条件演算子 (三項演算子) でデフォルトの引数を定義しています。

#! /usr/local/bin/nawk -f
# loop.awk
# ループ練習
# usage: nawk -f loop.awk num

BEGIN {
    num = ARGV[1];
    num = num ? num : 5;

    for (i = 1; i <= num; i++) {
        print "Hello World! " i;
    }
}

実行してみましょう。

$ gawk -f loop.awk
Hello World! 1
Hello World! 2
Hello World! 3
Hello World! 4
Hello World! 5

デフォルトの 5 回分 "Hello World!" が表示されました。

素数判定

素数の判定は AWK Users JP :: 素数の二進法表記AWK Users JP :: ベンフォードの法則を確かめてみる で用いているものです。

#! /usr/local/bin/nawk -f
# is_prime.awk
# 素数判定

## is_prime():  素数の判定
##  in:     数値 num
##  out:    素数なら数値 num、素数でないなら 0
function is_prime(num,    div) {
    for (div = 2; div <= num; div++) {
        ## 素数の場合
        if (div * div > num) {
            return num;
            break;
        }

        ## 素数でない場合
        if (num % div == 0) {
            return 0;
        }
    }
}

ここでは is_primt() 関数のみを定義してみました。

素数を求める

まずは先ほどの素数判定を用いたもので作成します。

#! /usr/local/bin/nawk -f
# prime.awk
# 素数を求める
# usage: gawk -f primt.awk num

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

    for (i = 1; i <= num; i++) {
        ## 素数の場合に表示
        if (is_prime(i) != 0) {
            printf("%d ", i);
        }
    }

    print "";
}

実行してみましょう。

$ gawk -f prime.awk -f is_prime.awk
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

awk はこのようにスクリプトをいくつも指定して実行することができ、関数化させたものを分離することもできます。

エラトステネスの篩 - Wikipedia を使えということなので、エラトステネスの篩を使って解きます。 エラトステネスの篩も AWK Users JP :: エラトステネスの篩で素数を求める で既に取り上げています。

#! /usr/local/bin/nawk -f
# eratosthenes.awk
# エラトステネスの篩
# usage: nawk -f eratosthenes.awk

BEGIN {
    num = ARGV[1];
    num = num ? num : 100;
    max = (num - 3) / 2;

    printf("2 ");

    for (i = 0; i <= max; i++) {
        flag[i] = 1;
    }

    for (i = 0; i <= max; i++) {
        if (flag[i] == 1) {
            p = i + i + 3;

            printf("%d ", p);

            for (k = i + p; k <= max; k += p) {
                flag[k] = 0;
            }
        }
    }

    print "";
}

こちらも実行してみます。

$ gawk -f eratosthenes.awk
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

同様に 100 までの素数が表示されました。

うるう年測定

うるう年であるかどうかは、4 で割り切れる場合にはうるう年、ただし、100 年で割り切れる場合にはうるう年ではなく、400 年で割り切れる場合にはうるう年になれば良いので、これをプログラムにします。

#! /usr/local/bin/nawk -f
# leap.awk
# うるう年判定
# usage: nawk -f leap.awk year

BEGIN {
    year = ARGV[1];
    year = year ? year : 2011;

    if (year % 4 == 0 && year % 100 !=0 || year % 400 == 0) {
        print year " はうるう年です。";
    } else {
        print year " はうるう年ではありません。";
    }
}

実行してみます。

$ gawk -f leap.awk
2011 はうるう年ではありません。

$ gawk -f leap.awk 2000
2000 はうるう年です。

ハノイの塔

ハノイの塔 - Wikipedia はある順序に従って並び替えることで求められます。

#! /usr/local/bin/nawk -f
# hanoi.awk
# ハノイの塔
# usage: nawk -f hanoi.awk num

BEGIN {
    num = ARGV[1];
    num = num ? num : 3;

    hanoi(num, "Position A", "Position B", "Position C");
}

## hanoi():     ハノイの塔の順番を表示する
##  in:     ハノイの塔の数 num
##          場所 ftom
##          場所 to
##          場所 buffer
function hanoi(num, from, to, buffer) {
    if (num > 0) {
        hanoi(num - 1, from, buffer, to);

        print from " -> " to;

        hanoi(num - 1, buffer, to, from);
    }
}

実行してみます。

$ gawk -f hanoi.awk
Position A -> Position B
Position A -> Position C
Position B -> Position C
Position A -> Position B
Position C -> Position A
Position C -> Position B
Position A -> Position B

転置行列

転置行列 - WikipediaAWK Users JP :: 転置行列を作る で作成しています。 さらに、AWK Users JP :: 横書き縦書き変換AWK Users JP :: 串刺し印刷のナンバリングを行う といったところでも活用されています。

#! /use/local/bin/nawk -f
# transposed_matrix.awk
# 転置行列
# usage: nawk -f transposed_matrix.awk foo.txt

{
    for (i = 1; i <= NF; i++) {
        val[i, NR] = $i;
    }
}

END {
    for (i = 1; i <= NF; i++) {
        for (j = 1; j <= NR; j++) {
            printf("%s%s", val[i, j], OFS);
        }

        print "";
    }
}

実行してみます。

$ cat transposed_matrix.txt
1 2 3
4 5 6
7 8 9

$ gawk -f transposed_matrix.awk transposed_matrix.txt
1 4 7
2 5 8
3 6 9

線形合同法

線形合同法 - Wikipedia を用いて乱数を発生させるという問題です。

#! /usr/local/bin/nawk -f
# linear_congruential_generator.awk
# 線形合同法
# usage; nawk -f linear_congruential_generator.awk num

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

    ## 初期変数の定義
    {
        m = 65536;
        a = 997;
        b = 1;
        x = 12345;
    }

    for (i = 1; i <= num; i++) {
        x = (a * x + b) % m;
        sum += x;

        printf("%1.4f ", x / m);

        if (i % 10 == 0) {
            print "";
        }
    }

    print "";

    printf("平均 = %1.4f\n", sum / m / num);
}

初期変数の定義として故意に括弧で括っていますが、awk ではこのように括弧でくくって分かりやすくすることもできます。

実行してみます。

$ gawk -f linear_congruential_generator.awk
0.8047 0.2430 0.2977 0.7755 0.1405 0.1119 0.5266 0.0315 0.4149 0.6418
0.9050 0.2534 0.6121 0.2548 0.0421 0.9879 0.9665 0.6227 0.7974 0.0321
0.9626 0.6673 0.2803 0.4326 0.3346 0.5605 0.8500 0.4865 0.0669 0.7243
0.1161 0.7406 0.3940 0.8304 0.9378 0.9918 0.8002 0.8008 0.4246 0.2869
0.0199 0.8074 0.9357 0.9228 0.0374 0.2719 0.0807 0.4464 0.0871 0.8663
0.7188 0.6546 0.6535 0.5125 0.9595 0.5943 0.4708 0.3823 0.1620 0.5622
0.5235 0.8976 0.9359 0.1054 0.0459 0.7303 0.1404 0.0206 0.5224 0.8023
0.8850 0.3548 0.6873 0.2854 0.5290 0.4047 0.5252 0.6015 0.6818 0.7174
0.2702 0.4225 0.2027 0.0897 0.4069 0.6702 0.2012 0.5684 0.6695 0.5166
0.0366 0.4504 0.0425 0.3835 0.3182 0.2826 0.7602 0.9427 0.9056 0.8619

平均 = 0.5070

数当てゲーム

数当てゲームの最初のお題は比較的簡単です。

#! /usr/local/bin/nawk -f
# kazuate.awk
# 数当てゲーム
# usage: nawk -f kazuate.awk num

BEGIN {
    num = ARGV[1];
    num = num ? num : 10;

    srand();
    answer = random(num);

    while (1) {
        printf("Input ");
        getline input;

        if (answer > input) {
            print "more larger";
        }
        if (answer < input) {
            print "more smaller";
        }
        if (answer == input) {
            print "correct!";
            break;
        }
    }
}

## random():    1 から num までの乱数を返す
##  in:     数値 num
##  out:    1 から num までの整数の乱数
function random(num) {
    return int(rand() * num) + 1;
}

出題がランダムになるように 1 から n までの乱数を発生させる random() という関数を作成しています。

遊んでみます。

$ gawk -f kazuate.awk
Input 5
more larger
Input 9
more smaller
Input 7
correct!

数当てゲーム その 2 (Hit & Blow)

Hit & Blow (マスターマインド - Wikipedia) も既に AWK Users JP :: マスターマインド として解かれています。

#! /usr/local/bin/nawk -f
# hit_blow.awk
# 数当てゲーム (Hit & Blow)
# usage: gawk -f hit_blow.awk num

BEGIN {
    num = ARGV[1];
    num = num ? num : 4;

    answer = make_num(num);

    while (1) {
        printf("%d 桁の数を入力 ", num);
        getline input;

        if (check_hit(answer, input) == num) {
            print "Correct!";
            break;
        } else {
            printf("%d blow ", check_blow(answer, input));
            printf("%d hit\n", check_hit(answer, input));

        }
    }
}

## check_hit():     Hit の数をチェックする
##  in:     正解 ans
##          回答 input
function check_hit(ans, input,    num, i, hit) {
    num = length(ans);

    for (i = 1; i <= num; i++) {
        if (substr(ans, i, 1) == substr(input, i, 1)) {
            hit++;
        }
    }

    return hit;
}

## check_blow():    Blow の数をチェックする
##  in:     正解 ans
##          回答 input
function check_blow(ans, input) {
    return gsub("[" input "]", "", ans);
}

## make_num():  ある桁数のダブりのないランダムな数値の作成
##  in:     桁数 num
##  out:    桁数 num のダブりのないランダムな数値
function make_num(num,    arr, ans) {
    split("123456789", arr, "");

    shuffle_array(arr);

    for (i = 1; i <= num; i++) {
        ans = ans arr[i];
    }

    return ans;
}

## random():    1 から num までの乱数を返す
##  in:     数値 num
##  out:    1 から num までの整数の乱数
function random(num) {
    return int(rand() * num) + 1;
}

## shuffle_array():     配列をシャッフルする
#   in:     配列 arr
function shuffle_array(arr,    a, num_arr, i, j, tmp) {
    srand();

    for (a in arr) {
        num_arr++;
    }

    for (i = num_arr; i >= 1; i--) {
        j = int((i + 1) * rand());
        if (j == 0) {
            j = 1;
        }
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

今回はダブリがないようにするということで、シャッフルしていますが、これもまた AWK Users JP :: 配列のシャッフルAWK Users JP :: 行のシャッフルAWK Users JP :: カードをシャッフルするAWK Users JP :: 単語のシャッフルAWK Users JP :: ビンゴシートの作成 で使われているお馴染みのものです。

遊んでみます。

$ gawk -f hit_blow.awk
4 桁の数を入力 1234
2 blow 0 hit
4 桁の数を入力 3456
2 blow 1 hit
4 桁の数を入力 4765
3 blow 2 hit
4 桁の数を入力 4752
Correct!

Fizz Buzz

Fizz Buzz - Wikipedia は有名な問題ですね。 AWK Users JP :: awk で FizzBuzz でも AWK Users JP :: awk 基礎文法最速マスター でも例題として挙げたことがあります。

#! /usr/local/bin/nawk -f
# fizz_buzz.awk
# FizzBuzz
# usage: nawk -f fizz_buzz.awk num

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

    for (i = 1; i <= num; i++) {
        print fizz_buzz(i);
    }
}

## fizz_buzz():     FizzBuzz
##  in:     数値 num
##  out:    FizzBuzz
function fizz_buzz(num) {
    if (num % 15 == 0) {
        return "FizzBuzz";
    } else if (num % 5 == 0) {
        return "Buzz";
    } else if (num % 3 == 0) {
        return "Fizz";
    } else {
        return num;
    }
}

こうした if 文や switch 文の篩は数の少ないものから除去していくのが一般的です。

実行してみます。

$ gawk -f fizz_buzz.awk 15
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz

カレンダー出力

カレンダーの表示は AWK Users JP :: 1 ヶ月カレンダー で取り上げています。

#! /usr/local/bin/gawk -f
# cal.awk
# カレンダーを表示する
# usage: gawk -f cal.awk [[month] year]

BEGIN {
    ## オプションの設定
    year  = (ARGV[1] && ARGV[2]) ? ARGV[2] : ARGV[1] ? ARGV[1] : strftime("%Y");
    month = (ARGV[1] && ARGV[2]) ? ARGV[1] : strftime("%m");

    month = sprintf("%02d", month);

    month_days = "31 28 31 30 31 30 31 31 30 31 30 31 ";

    split(month_days, arr_days);

    ## うるう年の計算
    leap = (year % 400 == 0) ? 1 : (year % 100 == 0) ? 0 : (year % 4 == 0) ? 1 : 0;

    ## うるう年の場合に 2 月を 29 日にする
    if (leap == 1) {
        arr_days[2] = 29;
    }


    ## タイトル部分の印字
    print "    " year " / " month;
    print "SU MO TU WE TH FR SA";

    ## その月の最初 1 日が何曜日かによってスペースを加える
    for (i = 0; i < strftime("%w", mktime(year " " month " 1 12 00 00")); i++) {
        space = space "   ";
    }

    printf("%s", space);
    ## その月の日数だけループ
    for (i = 1; i <= arr_days[month + 0]; i++) {
        ## 日曜日の場合に改行する
        if (strftime("%w", mktime(year " " month " " i " 12 00 00")) == 0 &&
            i != 1) {
            print "";
        }
        printf("%2d ", i);
    }
    print "";
}

strftime() 関数や mktime() 関数を使っているので gawk 専用ですが、AWK Users JP :: nawk で時刻取得 を参考にすれば nawk でも動作させることができます。

実行してみます。

$ gawk -f calendar.awk
    2011 / 10
SU MO TU WE TH FR SA
                   1
 2  3  4  5  6  7  8
 9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31

配列いじり

awk にはポインタというものがなく、配列も連想配列なので、課題の意図と違ったものになっています。

#! /usr/local/bin/nawk -f
# array.awk
# 配列いじり
# usage: nawk -f array.awk num

BEGIN {
    num = ARGV[1];
    num = num ? num : 5;

    ## ランダムな配列の生成
    for (i = 1; i <= num; i++) {
        array[i] = random(9);
    }

    print "置換前";

    for (i = 1; i <= num; i++) {
        printf("%d ", array[i]);
    }
    print "";

    ## 置換
    ## awk の場合には連想配列だから shift とかを使えない
    for (i = 2; i <= num; i++) {
        array[i] = 0;
    }

    print "置換後";

    for (i = 1; i <= num; i++) {
        printf("%d ", array[i]);
    }
    print "";
}

## random():    1 から num までの乱数を返す
##  in:     数値 num
##  out:    1 から num までの整数の乱数
function random(num) {
    return int(rand() * num) + 1;
}

実行してみます。

$ gawk -f array.awk
置換前
3 3 8 2 6
置換後
3 0 0 0 0

Caesar 暗号解読

シーザー暗号 - Wikipedia も既に扱ったことがあり、AWK Users JP :: シーザー暗号 に出ています。

違いは、既にある文字列のならびに対して Caesar 暗号を解いているということです。

#! /usr/local/bin/nawk -f
# caesar.awk
# Casear 暗号解読
# usage; nawk -f caesar.awk caesar.txt

{
    ## . が正規表現マッチしてしまうので、一旦置換
    gsub(/\./, "_", $0);
    print caesar($0);
}

## caesar():    Caesar 暗号を解く (文字列 "person" を含む)
##  in:     文字列 str
##  out:    解読された文字列
function caesar(str,    order_str, num, i, j, ans) {
    order_str = "abcdefghijklmnopqrstuvwxyz _,-"
    num = length(order_str);

    for (i = 0; i < num; i++) {
        ans = "";
        for (j = 1; j <= length(str); j++) {
            if(match(order_str, substr(str, j, 1))) {
                ans = ans substr(order_str, (RSTART + i) % num, 1);
            } else {
                ans = ans substr(str, j, 1);
            }
        }

        if (ans ~ /person/) {
            gsub(/_/, ".", ans);
            return ans;
        }
    }
}

例題を解いてみます。

$ cat caesar.txt
qdq-gi.q-a ziatmxxitmdqibtqi-ustbi ri.qmoqrcxi.qbubu zir -ibtqi-qp-qaai ripmymsqkir \
-ibtqi-qy dmxi ri.cnxuoi rruoumxakir -ibtqiqzmobyqzbkii-q.qmxi -imyqzpyqzbi rixmeaki \
-puzmzoqai -i-qscxmbu zaimzpir -i btq-iymbbq-a;iz -iatmxximzgi.q-a \
zinqiuzimzgiemgipuao-uyuzmbqpimsmuzabir -ia. za -uzsiacotiimi.qbubu zj

$ gawk -f caesar.awk caesar.txt
every person shall have the right of peaceful petition for the redress of damage, \
for the removal of public officials, for the enactment,  repeal or amendment of laws, \
ordinances or regulations and for other matters; nor shall any person be in any way \
discriminated against for sponsoring such  a petition.

さて、これは何でしょう? この文書は日本国憲法第 16 条の「何人も、損害の救済、公務員の罷免、法律、命令又は規則の制定、廃止又は改正その他の事項に関し、平穏に請願する権利を有し、何人も、かかる請願をしたためにいかなる差別待遇も受けない。」の英文です。

フィボナッチ数列

フィボナッチ数 - Wikipedia も何度か取り上げています。 AWK Users JP :: フィボナッチ数AWK Users JP :: フィボナッチ数が黄金比に収束するかの確認AWK Users JP :: フィボナッチ数列 (その 2)AWK Users JP :: うさぎの数が世界人口を越えるには です。

まず、再帰を用いたフィボナッチ数列からです。

#! /usr/local/bin/nawk -f
# fibonacci.awk
# 再帰フィボナッチ数列
# usage: nawk -f fibonacci.awk num

BEGIN {
    num = ARGV[1];
    num = num ? num : 10;

    for (i = 1; i <= num; i++) {
        print fibonacci(i);
    }
}

## fibonacci():     再帰的にフィボナッチ数列を求める
##  in:    number
##  out:   fibonacci number
function fibonacci(num) {
    if (num > 2) {

        return fibonacci(num - 2) + fibonacci(num - 1);

    } else {

        return 1;
    }
}

次に、再帰を用いないフィボナッチ数列です。

#! /usr/local/bin/nawk -f
# fibonacci_non_rec.awk
# 非再帰でフィボナッチ数を求める
# usage: nawk -f fibonacci_non_rec.awk num

BEGIN {
    num = ARGV[1];
    num = num ? num : 10;

    for (i = 1; i <= num; i++) {
        print fibonacci_non_rec(i);
    }
}

## fibonacci_non_rec():     非再帰でフィボナッチ数を求める
##  in:     数値 num
##  out;    数値 num 番目のフィボナッチ数
##  * 配列 fib はグローバル配列であることに注意
function fibonacci_non_rec(num) {
    fib[0] = 1;
    fib[1] = 1;

    if (num == 1) {
        return fib[0];
    }
    if (num == 2) {
        return fib[1];
    }
    if (num >= 3) {
        fib[num - 1] = fib[num - 2] + fib[num - 3];
        return fib[num - 1];
    }
}

実行してみます。

$ gawk -f fibonacci.awk
1
1
2
3
5
8
13
21
34
55

$ gawk -f fibonacci_non_rec.awk
1
1
2
3
5
8
13
21
34
55

フィボナッチ数は時間のかかる計算でも知られており、メモ化を使った高速化の手法が使われます。 メモ化を使ったものは AWK Users JP :: フィボナッチ数列 を参考にしてみてください。

英単語しりとりゲーム

単語集を作成するのが面倒なので、Linux にある word ファイル (/usr/share/dict/words) を用いていますが、巨大な配列を作成することになるので、メモリの消費は大きくなっています。 また、コンピュータが先手になっています。

#! /usr/local/bin/nawk -f
# shiritori.awk
# しりとり
# usage: nawk -f shiritori.awk

BEGIN {
    srand();
    ## word ファイルの設定
    word_file = "/usr/share/dict/words";

    ## word ファイルを配列に格納する
    while (getline < word_file > 0) {
        if ($0 ~ /^[abcdefghijklmnopqrstuvwxyz]+$/) {
            word[++nr] = $0;
        }
    }
    close(word_file);

    ## 先手がコンピュータ (決め打ち)
    com_word = word[random(nr)];

    while (1) {
        printf("%s => ", com_word);
        getline man_word;
        is_correct = 0;

        ## しりとりになっているか?
        if (substr(com_word, length(com_word)) != substr(man_word, 1, 1)) {
            print "You lost.";
            exit;
        }

        ## 単語として存在するか?
        for (i in word) {
            if (word[i] == man_word) {
                is_correct = 1;
                delete word[i];
            }
        }

        if (is_correct == 0) {
            print "You lost.";
            exit;
        }

        printf("%s => ", man_word);
        is_found = 0;

        for (i in word) {
            ## しりとりになっているか?
            if (word[i] ~ "^" substr(man_word, length(man_word))) {
                com_word = word[i];
                print word[i];
                is_found = 1;
                delete word[i];
                break;
            }
        }

        if (is_found == 0) {
            print "I lost.";
            exit;
        }
    }

}

## random():    1 から num までの乱数を返す
##  in:     数値 num
##  out:    1 から num までの整数の乱数
function random(num) {
    return int(rand() * num) + 1;
}

実行してみます。

$ gawk -f shiritori.awk
onward => death
death => healers
healers => sea
sea => ammonifying
ammonifying => good
good => daut
daut => tee
tee => embargoed
embargoed => dee
dee => embargoes
embargoes => sfdfsdfrefre
You lost.

膨大な辞書を使っているので、コンピュータには勝てそうにないですね。

ファイル読み込んで標準出力に出す

awk の最も得意とするところです。

#! /usr/local/bin/nawk -f
# stdin.awk
# ファイル入力標準出力
# usage: nawk -f stdin.awk file

BEGIN {
    ## ファイルが存在するかどうかの確認
    for (i = 1; i < ARGC; i++) {
        if (getline < ARGV[i] <= 0) {
            print "file not exist." > "/dev/stderr";
            exit;
        }
        close(ARGV[i]);
    }
}

{
    print "[" $0 "]";
}

ファイルの有無の確認は getline を使って判定しています。 gawk4 以降であれば、AWK Users JP :: 【緊急特集】最新の gawk 4.0.0 を追え! にあるように BEGINFILE で代用できます。

Base64

Base64 - Wikipedia は gawk の and, lshift, rshift といった関数の恩恵にあずかれる少ない機会かもしれません。 AWK Users JP :: awk で BASE64 エンコード にありますが、デコードも関数化してみました。

#! /usr/local/bin/gawk -f
# base64.awk
# BASE64 のエンコードとデコード
# usage: gawk -f base64.awk str

BEGIN {
    str = ARGV[1];
    str = str ? str : "Hello AWK!";

    print str i           " == encode ==> " str2base64(str);
    print str2base64(str) " == decode ==> "base642str(str2base64(str));
}

## str2base64():    文字列を BASE64 エンコードする
##  in:     文字列 str
##  out:    文字列 str を BASE64 エンコードした文字列
function str2base64(str,
                    BASE64, result, asc, byte1, byte2, byte3,
                    base1, base2, base3, base4) {

    BASE64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
    result = "";

    for (i = 0; i < 256; i++){
        asc[sprintf("%c", i)] = i;
    }

    while (length(str) > 0) {
        # Specify byte values
        if (length(str) == 1){
            byte1 = asc[substr(str, 1, 1)];
            byte2 = 0;
            byte3 = 0;
        }
        if (length(str) == 2){
            byte1 = asc[substr(str, 1, 1)];
            byte2 = asc[substr(str, 2, 1)];
            byte3 = 0;
        }
        if (length(str) >= 3){
            byte1 = asc[substr(str, 1, 1)];
            byte2 = asc[substr(str, 2, 1)];
            byte3 = asc[substr(str, 3, 1)];
        }

        # Create BASE64 values
        base1 = rshift(byte1, 2);
        base2 = lshift(and(byte1, 3), 4) + rshift(and(byte2, 240), 4);
        base3 = lshift(and(byte2, 15), 2) + rshift(and(byte3, 192), 6);
        base4 = and(byte3, 63);

        # Compose BASE64 string
        if (length(str) == 1){
            result = result substr(BASE64, base1 + 1, 1);
            result = result substr(BASE64, base2 + 1, 1);
            result = result "==";
            str = "";
        }
        if (length(str) == 2){
            result = result substr(BASE64, base1 + 1, 1);
            result = result substr(BASE64, base2 + 1, 1);
            result = result substr(BASE64, base3 + 1, 1);
            result = result "=";
            str = "";
        }
        if (length(str) >= 3){
            result = result substr(BASE64, base1 + 1, 1);
            result = result substr(BASE64, base2 + 1, 1);
            result = result substr(BASE64, base3 + 1, 1);
            result = result substr(BASE64, base4 + 1, 1);
            str = substr(str, 4);
       }
    }
    return result;
}

## base642str():    文字列を BASE64 デコードする
##  in:     文字列 str
##  out:    文字列 str を BASE64 デコードした文字列
function base642str(str,
                    BASE64, result, base1, base2, base3, base4,
                    byte1, byte2, byte3, byte4) {

    BASE64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
    result = "";

    while (length(str) > 0){
        # Specify byte values
        base1 = substr(str, 1, 1);
        base2 = substr(str, 2, 1);
        base3 = substr(str, 3, 1);
        base4 = substr(str, 4, 1);

        # Now find numerical position in BASE64 string
        byte1 = index(BASE64, base1) - 1;
        if (byte1 < 0) {
            byte1 = 0;
        }
        byte2 = index(BASE64, base2) - 1;
        if (byte2 < 0) {
            byte2 = 0;
        }
        byte3 = index(BASE64, base3) - 1;
        if (byte3 < 0) {
            byte3 = 0;
        }
        byte4 = index(BASE64, base4) - 1;
        if (byte4 < 0) {
            byte4 = 0;
        }

        # Reconstruct ASCII string
        result = result sprintf("%c",
            lshift(and(byte1, 63), 2) + rshift(and(byte2, 48), 4));
        result = result sprintf("%c",
            lshift(and(byte2, 15), 4) + rshift(and(byte3, 60), 2));
        result = result sprintf("%c",
            lshift(and(byte3, 3), 6) + byte4);
        # Decrease incoming string with 4
        str = substr(str, 5)
    }

    return result;
}

実行してみます。

$ gawk -f base64.awk
Hello AWK! == encode ==> SGVsbG8gQVdLIQ==
SGVsbG8gQVdLIQ== == decode ==> Hello AWK!

累乗

冪乗 - Wikipedia を解いています。 解法としては既に AWK Users JP :: 同じ文字列のn回繰り返しを作る方法 (その 2) でも使っています。

#! /usr/local/bin/nawk -f
# power.awk
# 累乗
# usage: nawk -f power.awk num1 num2

BEGIN {
    num1 = ARGV[1];
    num2 = ARGV[2];
    num1 = num1 ? num1 : 2;
    num2 = num2 ? num2 : 32;

    print power(num1, num2);
    print power2(num1, num2);
    print power3(num1, num2);
}

## power():     冪乗を計算
##  in:     数値 num1
##          数値 num2
##  out:    数値 num1 を数値 num2 回かけた数値
function power(num1, num2,    ans) {
    ans = 1;

    for (i = 1; i <= num2; i++) {
        ans = ans * num1;
    }

    return ans;
}

## power2():     冪乗を計算
##  バイナリ法 (下位桁から計算する方式)
##  in:     数値 num1
##          数値 num2
##  out:    数値 num1 を数値 num2 回かけた数値
function power2(num1, num2,    ans) {
    ans = 1;

    while (num2 != 0) {
        if (num2 % 2 == 1) {
            ans = ans * num1;
        }

        num2 = int(num2 / 2);
        num1 = num1 * num1;
    }

    return ans;
}

## power3():     冪乗を計算
##  バイナリ法 (上位桁から計算する方式)
##  in:     数値 num1
##          数値 num2
##  out:    数値 num1 を数値 num2 回かけた数値
function power3(num1, num2,    bin_num, num_arr, bin_arr, ans, k) {
    bin_num = dec2bin(num2);
    num_arr = split(bin_num, bin_arr, "");

    ans = 1;

    for (k = 1; k <= num_arr; k++) {
        ans = ans * ans;
        if (bin_arr[k] == 1) {
            ans = ans * num1;
        }
    }

    return ans;
}

## dec2bin():   10 進数を 2 進数で返す
##  in:     10 進数 num
##  out:    2 進数
function dec2bin(num,    rem, str) {
    while (num > 0) {
        rem = int(num % 2);
        if (rem == 1) {
            str = "1" str;
        } else {
            str = "0" str;
        }
        num = int(num / 2);
    }
    return str;
}

べき乗が定義されていない場合には、バイナリ法を用いて高速化することができます。

実行してみます。

$ gawk -f power.awk
4294967296
4294967296
4294967296

総論

いかがでしたか? なかなか骨のある課題も多かったのではないでしょうか?

awk で作るべきじゃないと思われるプログラムもあるのですが、この程度なら awk でできてしまうという awk の可能性を感じていただけたのではないでしょうか。

また、AWK Users JP :: AWK ならどう書く? で取り上げたことのあるものも多くありました。 AWK Users JP :: AWK ならどう書く? はインターネットなどで見つけた awk でも解けそうな例題を awk で解いていって、これから awk を習得しようという方の役に立てばと思ってはじめたものですが、既に 300 近い例題となり、その例題の選択も間違っていなかったかなと思っています。

これからも AWK Users JP をよろしくお願いします。

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