デスマコロシアム(第12回・最終回?)に参加しました
はじめに
CodeIQというところで開催していた、多言語コードゴルフトーナメント「デスマコロシアム」に参加しました。↓の結果記事にある通り、惜しくも決勝で敗れましたが、Perl(44byte)で全言語最短タイ&準優勝という結果になりました。
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)にできることが分かっています。
C(63) http://t.co/wnceUAzIqb
#デスマコロシアム
— 庶民あざらし (@naoki_kp) September 18, 2015
Brainf**k
こちらは2重ループでの実装。Brainf**kでは値を評価するたび、同時に値をクリアしてしまいますから、ループ制御変数をずらしてコピーしていきつつ処理を進めます。ループ変数をデクリメントしていく方が文字数を縮めやすいので、文字を最後の方から作って残しておき、出力は後回しにしています。
なお、終端を設けてないので、出力は無限ループになりますが…、
なあに、そのうちシステムが止めてくれるので無問題。非印字文字を出力しても画面に出なければ無問題。
…ここらへんはちょっと気付きにくいです。
とはいえここまでは、Brainf**k最短のじゅんやさんに対抗していく中で気付いたのですが、実はもっと別のアプローチで121まで縮むという…。凄いですね。
というわけで、
提出版BF(125)
http://t.co/5Z8PytaUNu
と、幻のBF(121)
http://t.co/vfjAIe4Zqq
です。
#デスマコロシアム
— じゅんや (@jrainf__k) September 18, 2015
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に突き放されお蔵入りに。カワイソス。
@angel_p_57 そこで問題だ! この四面楚歌の状況でどうやって優勝を狙うか?
3択 - 一つだけ選びなさい
①angelは突如文字数を縮めるアイデアがひらめく
②仲間がP勢のペナルティを増やしてくれる
③ねらえない。現実は非常である。
#デスマコロシアム #コードな情報戦
— angel-p57 (@angel_p_57) August 29, 2015
答え-① 答え① 答え① #デスマコロシアム #コードな情報戦 ( いや、まあ、これでやっと5分 - というか 4:4:2位? だけど )
— angel-p57 (@angel_p_57) August 29, 2015
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つずつ大文字がずれていく」を実現できるのですね。
…これで最短かと思っていたのですが…。
デスコロ採点中だけど面白いことになってる #デスマコロシアム
by ドラクエ風ジェネレーター http://t.co/AXTdrwEaZ7 pic.twitter.com/hwc2SMjquW
— てぃーびー (@tbpgr) August 27, 2015
と。優勝者tailsさんのPerl(44)提出とタイミングが被り、打ち負けるという結果に。なんか前からこんなんばっかや…。
あ…ありのまま今起こった事を話すぜ!「おれはPerl(46)でペナルティ込み暫定1位になったと思ったら言語内最短ですらなかった」な…何を言っているのか(以下略) #デスマコロシアム #コードな情報戦
— angel-p57 (@angel_p_57) August 27, 2015
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さんが後を引き継がれるという事で。新生デスマコロシアム(仮)として続いていくのは、ホント嬉しいことです。
…言語たくさん手を出すと、解説書くの大変…。