拡張正規表現でカウンタを書く
Esolang Advent Calendar の10日目になんとなく参加みたいな話です。自己紹介を書いておくと、好きな esolang は見た目よりむしろ中身重視というか、行なわれる処理や処理のしかたがユニークなものを好む傾向があるみたいです。あと先日 世界一の Befunge コーダーであることが判明しました(誇張)。
なにしようかなぁ考えたのですが、私の好きな言語のひとつに sed っていうか正規表現があるので、それについて。どの程度好きかというと、ほとんど 正規表現しか無いような wake という esoteric language を作ってみたことがある程度には好きな感じです。
正規表現ってヤツは普通文字列のマッチングに使うやつで、もちろんループとかは書けないわけですけど、しかしまぁちょっとした計算くらいなら割とできたりします。ループや出力の部分だけ、元の言語の機能から借りてやれば、割と色んなプログラムが書けます。例えば FizzBuzz
\%!; until (/;/) { #|fizzbuzz: l1,1 #%q; :
\%!; $\=$/; #\(\) #|k(.);.*\1(.).*:"$2" #%! s/$/;0123456789;/
\%!; s/$/;0123456789;/; #|j(.):k$+;0123456789 #%! s/9;\(.*;\)/;\10/
\%!; s/9;(.*;)/;${+}0/; #|i:"1" #%! s/\(^\|#\);/\10;/
\%!; s/(^|#);/${+}0;/; #|i(.*)9:i$+ "0" #%! s/\(.\);[^;]*\1/;/
\%!; s@\(\)|(.);[^;]*\1| #|i(.*)(.):"$2" j$3 #%! s/;\(.\).*;/\1/
\%!; @;@; #|o.*[50]:"Buzz\n" #%! s/^/#/
\%!; s/;(.).*;/$1/; #|o(.*): "$+\n" #%! h
\%!; s/^/#/; #|f.*[50]:"FizzBuzz\n" #%! x
\%!; $n=$_; #|f.*:"Fizz\n" #%! s/^\(###\)*/Fizz/
\%!; s/^(###)*/Fizz/; #|n(.*),(.):l$(i$2),$3 #%! s/.*#//
\%!; s/.*#//; #|l101,\d: #%! s/[0-9;]*[05]$/Buzz/
\%!; s@[0-9;]*[05]$| #|l(.*),0:f$+ n$+,1 #%! s/z[0-9]*$/z/
\%!; @Buzz@; #|l(.*),1:o$+ n$+,2 #%! p
\%!; s/z[0-9]*$/z/; #|l(.*),2:o$+ n$+,0 #%! x
\%!; print; #|#: #%q; /;/!b
\%!; $_=$n; #|#: #%! d
\%!; } # (C) 2011 #|#: Shinichiro Hamaji #%i All Rights Reserved上のプログラムは (なるべく正規表現以外使わないようにしてある)Perl, wake, sed の polyglot になってます。つまりその3つの処理系どれでも FizzBuzz として実行できます。わかりやすいように左から Perl, wake, sed と、だいたい別れている構造になっています。それぞれ横幅20文字でおさえるかな…と思ったので、主にそのへんで苦労した気がします。
あとはまぁ適当にカウンタを作る説明など。
Perl なんかにある、正規表現ってヤツですが、後方参照があって、正規表現でマッチして置換、みたいなことができる言語だと、結構計算ができたりします。 0,1,2,..,8,9 を 1,2,3,...,9,0 に変換するような関数は、 Perl だと
sub inc { $_ = pop; s/$/;01234567890/; s/(.);.*\1(.).*/$2/; $_; } print inc(0), "\n"; print inc(4), "\n"; print inc(8), "\n";
という感じに書けます。 inc の真ん中2行がインクリメントをしている部分です。まず最初の、
s/$/;01234567890/;
というコレは、入力 X を、 X;01234567890 として、後ろにヘンな文字列をくっつけてるだけです。例えば入力が 4 の時は 4;01234567890 になります。で、次の、
s/(.);.*\1(.).*/$2/;
が本質です。最初の (.) は入力 X にマッチします。入力が 4 なら 4 ですね。その後 ;.* でセパレータと何文字が読み飛ばして、次に来るのが後方参照 \1 です。これは以前の括弧の中にマッチしているので、入力が 4 なら 4 です。つまりここまでで、 ;.* が ;0123 にマッチして、次の 4 まで読んだ状態、つまり残ってる文字列は 567890 です。後は簡単で、 (.).* で、最初の文字を2つ目の後方参照に保持した後、残りを読み捨てます。で、置換後文字列の $2 は 2つ目の後方参照 (.) なので、これは 567890 の先頭の文字であるところの 5 です。これで 4 が 5 に変換できてることが確認できました。
ここまでをまとめると、
(.) - 4 ;.* - ;0123 \1 - 4 (.) - 5 .* - 67890
というふうにマッチしています。
あとはまぁ頑張れば繰上がりを含むカウンタ、任意精度の加算、乗算などなんでもできます。結構頑張れば。
興味がある人は、加算についてはこのへん に書いたり、あと このあたりにもうちょっと具体的な問題を解いてた時のコメントがあったりします。
Perl は見るだけで吐き気とかを催す人がいるかもしれないので、拡張正規表現があれば基本一緒だよ、ということで他の言語でも適当に書き散らかしてみます。
def inc(x) x.to_s.sub(/$/, ';01234567890').sub(/(.);.*\1(.).*/, '\2').to_i end puts inc(0) puts inc(4) puts inc(8)
import re def inc(x): x = re.sub(r'$', ';01234567890', str(x)) x = re.sub(r'(.);.*\1(.).*', lambda m: m.group(2), x) return int(x) print inc(0) print inc(4) print inc(8)
function inc(x) { x = String(x).replace(/$/, ';01234567890'); return x.replace(/(.);.*\1(.).*/, "$2"); } console.log(inc(0)); console.log(inc(4)); console.log(inc(8));
とかなんとか。
