Weasel の問題を解く
ついにこのAWK ならどう書く?も 150 回を越えました。 問題に偏りがあるため、全てを網羅しているとは言えませんが、この約 1 年間で話題になったプログラムを awk で解いてみました。 無駄なプログラムもありますが、少しでもお役に立てれば幸いです。
さて、今回はMETHINKS IT IS A WEASEL DouKaku? を今までに使った関数をメインに解いてみたいと思います。
#! /usr/bin/gawk -f
# weasel.awk
BEGIN {
srand();
target = "METHINKSITISAWEASEL";
# １：ランダムな２０文字を持つ文字列をもった３００個作ります。
# 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);
}
}
# ５：以後３：と４：を繰り返す。
while (1) {
# ２：その文字列が"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 {
# ３と4の間でソートしたもので一番上位のものを毎回表示させると変化が楽しめます。
print str[1];
}
# ３：それぞれの文字列のなか1文字を別の文字に変化させたものを３つ用意します。
# ４：それを２：のソートをして上位３００個残す。
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
さて、非常に時間がかかっているわけですが、どのあたりがボトルネックになっているのかを含めて検討すると面白いかもしれません。
