読者です 読者をやめる 読者になる 読者になる

デスマコロシアム(第12回・最終回?)に参加しました

はじめに

CodeIQというところで開催していた、多言語コードゴルフトーナメント「デスマコロシアム」に参加しました。↓の結果記事にある通り、惜しくも決勝で敗れましたが、Perl(44byte)で全言語最短タイ&準優勝という結果になりました。

codeiq.jp

togetter.com

Perlコードについては、優勝者のtailsさんと基本的に同じなのですが、他に挑戦した言語も含めて色々ネタばれしようと思います。

問題

お題

お題は、

abCDEfghIjklmnOpQrstuvwxyzabcDEFghiJklmnoPqRstuvwxyzabcdEFGhijKlmnopQrStuvwxyzabcdeFGHijkLmnopqRsTuvwxyzabcdefGHIjklMnopqrStUvwxyzabcdefgHIJklmNopqrsTuVwxyzabcdefghIJKlmnOpqrstUvWxyzabcdefghiJKLmnoPqrstuVwXyzabcdefghijKLMnopQrstuvWxYzabcdefghijkLMNopqRstuvwXyZabcdefghijklMNOpqrStuvwxYzabcdefghijklmNOPqrsTuvwxyZabcdefghijklmnOPQrstUvwxyzabcdefghijklmnoPQRstuVwxyzabcdefghijklmnopQRStuvWxyzabcdefghijklmnopqRSTuvwXyzabcdefghijklmnopqrSTUvwxYzabcdefghijklmnopqrsTUVwxyZabcdefghijklmnopqrstUVWxyzabcdefghijklmnopqrstuVWXyzabcdefghijklmnopqrstuvWXYzabcdefghijklmnopqrstuvwXYZ

という572文字を、途中改行はさまず ( 最後に付け加えるのは可 ) 出力する、というものでした。

アプローチ

この572文字に着目すると、基本的にa~zの26文字の22周期分の繰り返し、なのですが、ところどころ大文字になっていることに気付きます。
この大文字の箇所は、最初が cdeioq ( codeiq ですね ) の6文字、次が defjpr の6文字、次が efgkqs … と言うように、1つずつずれていくという規則性があります。なので、素直に考えると、

for ( int i=0; i<22; i++ )
  for ( int j=0; j<26; j++ )
    switch (j-i) {
      case 2:
      case 3:
      case 4:
      case 8:
      case 14:
      case 16: putchar('A'+j);break;
      default: putchar('a'+j);
    }

という2重ループ ( 上の例はC99 ) で、大文字にする箇所を2種類のループカウンタの差で評価するコードが思い浮かびます。もしくは、ループを1重化して、

for ( int i=0; i<572; i++ )
  switch (i%26-i/26) {
    ...

とした方が良いかも知れません。この辺は言語に依ります。

文字数短縮のポイント

問題は上のコードの switch文に相当する、いつ大文字にするかの判定です。これ実はBrainf**kではあまり悩まずに済むのですが、他の言語でまともに6通りの条件判定を書いていてはシャレになりません。 そこで、2,3,4,8,14,16 を bit-set として扱う、つまり2進数の 10100000100011100、10進数で82204のどこのbitが立っているか、で条件判定をするのが今回の共通のポイントとなります。え? Octave? ワタシオクタアブヨクワカリマセン。

各言語での実装

C

ではまずはC(64)から。

上で挙げたポイントに素直に沿って実装しています。大文字・小文字の違いは、bit演算子を駆使して 32 を作り出すことで何とかしています。これは、同じアルファベットの大文字・小文字で、ASCIIコードが丁度32違うからですね。
なお、82204を使う代わりに文字定数を活用することでC(63)にできることが分かっています。

Brainf**k

次はBrainf**k(132)

こちらは2重ループでの実装。Brainf**kでは値を評価するたび、同時に値をクリアしてしまいますから、ループ制御変数をずらしてコピーしていきつつ処理を進めます。ループ変数をデクリメントしていく方が文字数を縮めやすいので、文字を最後の方から作って残しておき、出力は後回しにしています。
なお、終端を設けてないので、出力は無限ループになりますが…、
なあに、そのうちシステムが止めてくれるので無問題。非印字文字を出力しても画面に出なければ無問題。
…ここらへんはちょっと気付きにくいです。
とはいえここまでは、Brainf**k最短のじゅんやさんに対抗していく中で気付いたのですが、実はもっと別のアプローチで121まで縮むという…。凄いですね。

Ruby

次はRuby(45)
…これは記事に載ってるしイイよね。ポイントは整数値に対する [] 演算子で、指定したbitが取り出せるという事。これで驚異的に短く書けるので、一時はRubyが最短かと思っていましたが…。なお、ideoneではBashからrubyが呼べるようになったので、これでBash(54)も作れます。

R/WhiteSpace

今度のR(56)は、bit演算子が簡単に使えません。ライブラリをロードして関数として使う必要があるかと思います。なので、代わりに2のべき乗を使って似たような処理を実現しています。

WhiteSpace(203)も、そういう意味では似たようなことをしています。生コードの元は長いのでここでは割愛します。
※2015/9/21追記: WhiteSpace更新版(200)についてデスマコロシアム(第12回) 補足-WhiteSpace文字数更新 - ange1のブログに補足記事を載せました。

Falcon

Falcon(53)は切り札…の積りでした。まあどちらにしてもPerl6には負けていたのですが。

こちらは2重ループで処理しています。面白いのは、文字に対する / 演算子文字コードがずらせることと、さらに左辺値でないリテラルに対しても /= 演算子が使えること。これで余分な括弧を省けるように。
途中56文字で伸び ( 縮み? ) 悩んでいた所で、上のことに気付き喜んだ訳ですが…。最終的にペナルティのなくなったPerlに突き放されお蔵入りに。カワイソス。

Perl

最後にPerl(44)。あ、BashからPerlワンライナーにすればBash(53)も作れます。

Perl(46)

その前にちょっとPerl(46)に触れておきましょう。

print 82204>>$i++&1?uc:lc for(a..z,("")x37)x22

Perlはuc,lcで大文字・小文字が簡単に作れるので、無理に32を作らなくて良くて楽です。加えて文字も..演算子で連番にできますし。
さらにポイントは、bit-shift演算 ( <<, >> ) が、64周期であること。つまり、$x>>64 は $x>>0 と同じとか、そういうこと。なので、% で剰余を計算しなくても、ダミーの空文字列を入れて63×22のループを作れば、カウンタ$iをそのままbit-shiftに使うだけで、自動的に「1つずつ大文字がずれていく」を実現できるのですね。
…これで最短かと思っていたのですが…。

と。優勝者tailsさんのPerl(44)提出とタイミングが被り、打ち負けるという結果に。なんか前からこんなんばっかや…。

Perl(44)

ということでPerl(44)

print 1<<ord>>++$$_&82204?uc:lc for(A..Z)x22

A~Z 22セット分のループなのですが、2重ループのカウンタi,jに相当する部分を $$_ と ord で賄っているところがポイント。
$$xxx の形は、スカラ変数のリファレンスに対するデリファレンスなのですが、一般的には。リファレンスでなくて文字列データに対して使うと、その名前を持った変数として扱えるのですね。つまり $_="A" なら $$_ は $A と同じ。気付きにくい所ですが。
そうすると、アルファベットを1周する毎に $A~$Z が1ずつ増えますから、外側ループのカウンタが$A~$Zにまんべんなく保存されているのと同じで、しかも $$_という同じ表記で毎回取り出せることになります。
また、ord により文字コードを取り出すと、丁度 65~90。<< は64周期でしたから、ord が内側ループのカウンタ代わりに使えるという事になります ( a~z ではなく A~Z がミソ )。これで、除算・剰余を使わずに済みRubyを超える文字数が実現できたというわけです。
なお、ord を裸で使うので、演算の順番はかなりデリケートになります。なぜなら ord の次に来るものは ord の引数と解釈されかねないからです。( ord<<~ とかやると、<< が bit-shift でなくてヒアストリング開始と解釈されて楽しいことに )

おまけ(自動採点版)

本戦と異なり、a~zの順が入力文字列によって変わるという事で、かなり違う組み方が要求されるように思えた自動採点版ですが… codeiq.jp

実はPerlであれば、ほぼ同じロジックで短く組めるのですね。以下は Perl(50)

$_=uc<>x22;print 1<<ord>>++$$_&82204?uc:lc for/./g

A~Zの連番の代わりに入力文字列(の大文字化版)を使うように変えただけです。ううむ。まさかここまで見越して自動採点版を用意していたのか!!
※まあハッシュを使えば、他の言語でも似たようなことはできるでしょうが…。文字数的にはどうか…。

終わりに

本当は前回(第11回)分から記事にしようと思っていたのですが、ちょっと余裕がなく手を付けられませんでした ( コラ画像が上手くできなかったというのはナイショです )。で、いきなり最終回に…。と思いきや、cielさんが後を引き継がれるという事で。新生デスマコロシアム(仮)として続いていくのは、ホント嬉しいことです。
…言語たくさん手を出すと、解説書くの大変…。