String Halving

anarchy golf js sed C

昨晩、String Halving が終了した。面白い問題だった。

sed

sedは結構コンパクトにできたな(83B)と思っていたら、tails さん@70B にあっさり抜かれた。
この問題は、文字列を２分割して、それぞれを中かっこで囲えばいいのだが、２分割するところが工夫のいるところ。考えたのは、２つマーカーを設けて、１ポジションずつ文字列の内側へ向けて寄せていく方法。例示すると以下のよう。

B----------E
-B--------E-
--B------E--
---B----E---
----B--E----
-----BE-----

マーカーとして、中かっこを使えば最も効率がいいのだが、分割をしていくと中かっこが文字列中に現れるので、ほかの文字を使う必要があると思っていた。ところが、tails さんの解を見たら、中かっこを使っていた。確かに、右に動ける右中かっこは一つしか存在しないし、左に動けるものも同様なんだ。

    B     E
{{--}-----{--}{----------}}

この例のように、B と E は簡単に特定できる。

s/}\([^{}]\)/\1}/
s/\([^{}]\){/{\1/

中かっこはマーカーに使えないという思い込みがあったためか、気付けなかった。tails さんさすがです。

JavaScript(と C)

JavaScript は、youz さん@83B に 1B 差で負けた。以下は youz さんの解。

s=readline(i=0)
function r(n)"{"+(n<2?s[i++]:r(n/2+.5|0)+r(n>>1))+"}"
print(r(919))

特徴的なのは、i を使って、分割しきった長さ 1 の文字列の取り出しを、s[i++] で行っているところだ。入力文字列の先頭から順にアクセスされるということなんだ。試しに、私の解に以下のようにprint()を突っ込んでみたら、

s=readline(f=function(b,e)'{'+(e+~b?f(b,b=b-~e>>1)+f(b,e):(print(b),s[b]))+'}')
print(f(0,s.length))

確かに、

0
1
2
3
:

と順に表示された。これは、気づかなかった。
ということは、C では、getchar() で順に読み込んでやればいいんだと思い、自分の解を以下のように変更してみたら 88B ができた。

p(x){putchar(x);}f(l){p('{')+(l>1?f(l+1>>1)+f(l/2):p(getchar()))+p('}');}main(){f(919);}

これは面白いな。もう少し短くなるかも。

追記：

アクセスが文字列の先頭から順に行なわれるというのは、２分木の Depth-First サーチ（日本語ではなんていうんだろう？）だから、ツリーの左から順にアクセスされるということか。