Function call expression & SQR
「いつまでも治らないバグ。迫りくるデッドライン。コードゴルフはじめました〜♪」
「MS11-022。あてたらパワポが使えない。コードゴルフはじめました〜♪」
「誰よりもDISK使うアンチバイラス。リブートしたらブルースクリーン。コードゴルフはじめました〜♪」
さて。
Function call expression
この問題は何通りかの解法があった。
まず、youz さんによるJavaScript 解。ただこの世界は私にはついていけないので特に語らず。
次は、パターンマッチと置換。つまり X '(' Y ')' を '(' X ' ' Y ')' に置換することを繰り返すことで答えを得る。正規表現の無い言語では、ちょっとつらい。最初はこの方法で解いていたが、もっと短くなる方法が見つかった。この方法のままなのは、sed 。youz さんに 2B 差で負けた。'\D' に持っていくのは、ほかの言語でやっていたのだが、sed の正規表現にはない。youz さんは、空白文字も置き換えることで、'\w' を使えるようにしている。うまいな。それにしても、sed の正規表現って、わりと貧弱なんだな。awk ほどではないけど。
３つめは、スタックマシン。この方法を思いついたら短い解ができた。この方法が一番素直な気がする。しかも、正規表現の無い（または使いにくい）言語にも有効だ。
この方法では、先頭から一文字ずつ読んでいきスタックに積む。')' を読んだときは、スタックから３つ POP して、"(X Y)" ストリングを作成し、また、スタックに積む。こうすると答えが得られる。たとえば、"f(f(f))" だと、
入力 | f | ( | f | ( | f | ) | ) | スタック | f | f | f | f | f | f |(f (f f))| | | ( | ( | ( | ( | ( | | | | | f | f | f | (f f) | | | | | | ( | ( | | | | | | | | f | | |
という風になる。
GolfScript はそれ自体スタックマシンなので、そのまま当てはめて 27B ができた。JavaScript, Groovy, vi もこの方法で縮んだ。C もこの方法でトップ 102B ができた。ただ、C の場合はメモリー管理が複雑になったため、わかりにくいコードかもしれない。また、asprintf() なるものを初めて使った。sprintf() の出力先を勝手に malloc() して返してくれるというもの。このため、スタックはポインターを保持するだけでよくなり小さくなったため、*b=&b で確保でき、大変効果的だった。
SQR
m*n のメッシュに含まれる正方形の数を数えるというもの。当初、多くの人がやっているように、
s+=m--*n--
で答えを求めていたが、次のように変形するともっと短くなった。
m>=n とする m*n+(m-1)*(n-1)+...+(m-n)*0 = Σi*(m-n+i) // i=0..n = Σ(i*i + (m-n)*i) = Σi*i + (m-n)Σi // ★ = n*(n+1)*(2*n+1)/6 + (m-n)*n*(n+1)/2 = n*(n+1)*(1+3*m-n)/6
n>m のケースの微調整がいるが、この方法が効果的だった。
なお上で「★」を付けた式だが、左側Σは正方形(n*n)に含まれる正方形の数で、右側Σは正方形(n*n)からの逸脱により増加する正方形の数になっている。
〜〜〜〜〜
土曜の晩だったか、ニコ動で koi さんが Arecibo message を解くのを見た。inaniwa さん、not さんも参加していた。たまには、こういうのもいいね。
5/24追記
夕べ koizuka さんが、またニコ生をやっていた。途中から入ったら、ちょうど私の 102B の解読・解説を始めるところだった。見ていたが、かなり読みにくかったようで、苦労されていた。
ちょっと、以下に解説を試みる。
*b=&b;
main(p){
for(;
read(*b=0,++b,1)&*b
?asprintf(&p,"(%s %s)",1[b-=6],p)
:*b>10
?p=b
:puts(p)**b
;)*++b=p;
}＃整形しても読みにくいな。
前にも書いたとおり、方針はスタックマシンだ。スタックフレームは２ワードで、はじめのワードには、読み込んだ文字が入り、次のワードには、その文字(列)へのポインターが入る。という構造。なので、一回のループで、スタックポインター b は、＋２される、というもの。
まず、*b=&b; だが、これは、a[99];*b=a; とほぼ等価だ。変数 b の次のアドレスからをバッファー（スタック）として使う。*b=&b+1 のほうがわかりやすいかもしれないが、どうせ、まず前置＋＋されるので、＋１は不要だ。
for 文の条件節の中に処理が大量に入っているのは、この問題の場合、入力の最後に改行文字がないためだ。あなごるの問題には、最後の改行ありとなしのパターンがあり、readline()@JS や gets()@C の場合には関係ないが、getchar() や read() でストリーム処理をする場合は影響がある。本解答では、このため、EOF になった後に、一回処理して出力し、ループを終了するという構造になっている。また、read()のリターン値を使うのをやめると以下と等価だ。
for(;f=read(*b=0,++b,1), *b&1?asprintf(...):*b>10?p=b:puts(p), f;)...;
さて、スタック処理をする上で、キーとなるのは、閉じ括弧 ')' の入力で、この文字コードは、41 で奇数だ。そのほか、'f', '(', '\n' はみな偶数である。そのため、*b&1 で判断している。
入力が偶数の場合は、その文字を読み込んだスタックのアドレスをその次のワードに入れている。'f(f(f)' と読んだ場合のスタック様子は以下のようだ。
|'f', 0, 0, 0 |
|'f'のアドレス|
|'(', 0, 0, 0 |
|'('のアドレス|
|'f', 0, 0, 0 | <- b-=6
|'f'のアドレス| <- 1[b-=6]
|'(', 0, 0, 0 |
|'('のアドレス|
|'f', 0, 0, 0 |
|'f'のアドレス| <- p
|')', 0, 0, 0 | <- bスタックポインター b の指す内容を read() の第一引数のところで、ゼロクリアしているので、文字を読んだスタックの内容は、文字の後ろにゼロが来て、文字列として扱える。その文字列のアドレスが、次のワードに入る構造だ。
閉じ括弧 ')' を読んだ場合は、asprintf() を呼ぶ。この関数は malloc() した領域に sprintf() して返してくれる。そのアドレスをスタックにつむ。このとき、スタックを３個ポップするので、b-=6 としている。また、p は、前回のループで処理した文字列のアドレスが入っているので、これらを使って、
asprintf(&p,"(%s %s)",1[b-=6],p)
とし、その後、*++b=p とすると、スタックは、
|'f', 0, 0, 0 |
|'f'のアドレス|
|'(', 0, 0, 0 |
|'('のアドレス|
|'f', 0, 0, 0 | <- 残骸
|"(f f)" | <- b : 文字列 "(f f)" のアドレスとなる。
以上のような処理を行っている。おしまい。
5/24追記その２
http://d.hatena.ne.jp/rst76/20110523/1306161039 で、rst76 さんが Haskell 解を解説している。Haskell はまったくわからないのであるが、日記の最後でこの問題の閉じ括弧 '(' は『逆ポ』の演算子だと言っている。確かにその通りだ。だから、スタックマシンで解決できたのか。面白いな。
