Weasel の問題を解く

ついにこのAWK ならどう書く?も 150 回を越えました。 問題に偏りがあるため、全てを網羅しているとは言えませんが、この約 1 年間で話題になったプログラムを awk で解いてみました。 無駄なプログラムもありますが、少しでもお役に立てれば幸いです。

さて、今回はMETHINKS IT IS A WEASEL DouKaku? を今までに使った関数をメインに解いてみたいと思います。

#! /usr/bin/gawk -f
# weasel.awk

BEGIN {

    srand();
    target = "METHINKSITISAWEASEL";

    # 1:ランダムな20文字を持つ文字列をもった300個作ります。
    # Ref: http://gauc.no-ip.org/awk-users-jp/blis.cgi/DoukakuAWK_143
    for (i = 1; i <= 300; i++) {
        for (j = 1; j <= length(target); j++) {
            str[i] = str[i] sprintf("%c", int(rand() * 26) + 65);
        }
    }

    # 5:以後3:と4:を繰り返す。
    while (1) {
        # 2:その文字列が"METHINKSITISAWEASEL"に近いものからソートします。
        # Ref: http://gauc.no-ip.org/awk-users-jp/blis.cgi/DoukakuAWK_107
        num_str = 0;
        for (i in str) {
            str[i] = sprintf("%2d %s",\
                             levenshtein_distance(str[i], target), str[i]);
            num_str++;
        }

        # Ref: http://gauc.no-ip.org/awk-users-jp/blis.cgi/DoukakuAWK_038
        merge_sort(str, 1, num_str, 1);

        # METHINKS IT IS WEASELができたら終了。
        if (str[1] == " 0 " target) {
            print str[1];
            exit;
        } else {
            # 3と4の間でソートしたもので一番上位のものを毎回表示させると変化が楽しめます。
            print str[1];
        }

        # 3:それぞれの文字列のなか1文字を別の文字に変化させたものを3つ用意します。
        # 4:それを2:のソートをして上位300個残す。
        for (i = 1; i <= 300; i++) {
            split(str[i], arr_str, " ");
            str[i] = arr_str[2];
            for (j = 1; j <= 2; j++) {
                position = rand() * length(target) + 1;
                arr_str[2] = substr(arr_str[2], 1, position - 1) \
                             sprintf("%c", int(rand() * 26) + 65) \
                             substr(arr_str[2], position + 1);
                str[i + 300 * j] = arr_str[2];
            }
        }
    }
}


# 2 つの文字列のレーベンシュタイン距離を返す
function levenshtein_distance(s1, s2,   a_str1, a_str2, i, j) {
    len_s1 = length(s1);
    len_s2 = length(s2);
    split(s1, a_str1, "");
    split(s2, a_str2, "");
    for (i = 0; i <= len_s1; i++) {
        distance[i, 0] = i;
    }
    for (j = 0; j <= len_s2; j++) {
        distance[0, j] = j;
    }
    for (i = 1; i <= len_s1; i++) {
        for (j = 1; j <= len_s2; j++) {
            if (a_str1[i] == a_str2[j]) {
                cost = 0;
            } else {
                cost = 1;
            }
            distance[i, j] = min3(distance[i - 1, j    ] + 1,\
                                  distance[i    , j - 1] + 1,\
                                  distance[i - 1, j - 1] + cost);
        }
    }
    return distance[len_s1, len_s2];
}

# 3 つの最小値を返す
function min3(a, b, c,    min) {
    min = a;
    if (b <= min) {
        min = b;
    }
    if (c <= min) {
        min = c;
    }
    return min;
}

# function for recursive merge sort
function merge_sort(arr, a, b, key,   k) {
    if (a < b) {
        k = int((a + b) / 2);
        merge_sort(arr, a, k, key);
        merge_sort(arr, k + 1, b, key);
        merge(arr, a, k, b, key);
    }
}

# function for merge
function merge(arr, a, k, b, key,   i, j, p, c) {
    j = i = a;
    p = k + 1;
    while (a <= k && p <= b) {
        split(arr[a], arr_key1);
        split(arr[p], arr_key2);
        if (arr_key1[key] <= arr_key2[key]) {
            c[i++] = arr[a++];
        } else {
            c[i++] = arr[p++];
        }
    }
    while (a <= k) {
        c[i++] = arr[a++];
    }
    while (p <= b) {
        c[i++] = arr[p++];
    }
    while (j <= b) {
        arr[j] = c[j];
        j++;
    }
}

長いですが、function のところは既に使った関数のみを使用しています。 「ランダムな文字列の生成」にはAWK Users JP :: 囲まれた文字列の置換で使った手法を用いていますし、「文字列の近さ (= 距離)」はAWK Users JP :: ナイツ関数(ボケの方)を解いてみるで使ったレーベンシュタイン距離 (実際にはAWK Users JP :: Jaro-Winkler 距離の計算で出てきた Jaro-Winkler 距離の方が良いかもしれません) を用いています。 また、特定のフィールドでのソートには AWK Users JP :: 2 番目のフィールドでのソートで用いた key を持ったマージソートを使っています。

問題解決の最適化は行っていませんが、今までの知識だけで解くことができます。

実行してみましょう。

$ mawk -f weasel.awk
13 MTRIHMFAQIFAZWESLKS
13 MTRIHMFAQIFAZWESLKS
13 MTRIHMFAQIFAZWESLKS
13 MTRIHMFAQIFAZWESLKS
13 MTRIHMFAQIFAZWESLKS
13 MTRIHMFAQIFAZWESLKS
11 MTRIHMFATIFAZWESLLS
11 MTRIHMFATIFAZWESLLS
10 MTIIHMFATIFAZWESELS
<snip>
 1 METHINKSITPSAWEASEL
 0 METHINKSITISAWEASEL

さて、非常に時間がかかっているわけですが、どのあたりがボトルネックになっているのかを含めて検討すると面白いかもしれません。

tag_nawk.pngtag_nawk.pngtag_nawk.pngtag_nawk.png