デスコロC #2に参加しました ( CodeIQ )

CodeIQ コードゴルフ デスマコロシアム

はじめに

CodeIQというところで開催していた、多言語コードゴルフ、デスコロC #2 に参加しました。cielさんの自動採点版となってから2回目です。

codeiq.jp

問題

今回のテーマは「アルファベット列の○○かつ○○○番目を大文字化」で。○にピッタリ合う文言は特に深く考えていませんでしたが…。
まあ、提示された出力内容から読み取れた内容は、

  • アルファベット26文字 ( a～z ) を50組、計1300文字をつなげて出力する。( 末尾の改行は任意 )
  • ただし、先頭を1文字目として、「素数文字目」かつ「3を含まない文字数目」( 例えば7文字目や19文字目は対象だけど3文字目や137文字目は対象外 ) は大文字にする

でした。

解説

ということで、やることは素数判定と、3を含むかどうかの判定の2つで、どちらも得意なのがPerlですね…。いや、言語的に素数判定関数なんて持ってないんですけど。

初期の提出

Perlで素数判定と言えば、『第6回デスマコロシアム』に参加しました - Tails の（仮） で紹介された正規表現によるものが真っ先に思い浮かびます。今ではPerlのバージョンも上がっているので、=~ 演算子の代わりに ~~ 演算子でカッコが省けて2文字もお得です。

ということで、Perl(55) ( 実際は2回目の提出 ) です。なお、非素数ということで1の判定も混ぜています。

print++$i=~3||1x$i~~/^(1|(11+)\2+)$/?lc:uc for(a..z)x50

「3を含むかどうか」を =~3 一発で判定できるのが素敵ですね。ループ自体は、a～z 50組のリストに対して回します。

同時期に提出していた%20さんもPerl(55)だったので、似たようなコードだったのではないでしょうか…??

改良版

まあしかし、tailsさんにあっさり抜かれました ( この時点でおそらくPerl(53) )。

いやまあ、割といつものことですが…。ということで、更に真剣に検討し直します。

「3を含むかどうか」はこれ以上縮めようがないので、素数判定をどうするか、ですね。なんというか「( 判定関数がない場合は ) 正規表現で」が常識になっている感がありますが、実は3通りは方法があります。

  • 正規表現
    既に出ているので割愛
  • フェルマーテスト
    素数$p$に対するフェルマーの小定理$a^p\equiv a\,\,mod\,p$を利用し、この合同式が成立する数を抽出する方法です。諸所の事情により、Perlでは対象の数値$iに対し2**$i%$i-2 がゼロという条件で、そこそこの数の奇素数を抽出することができます。
    …しかし。今回は上限1,300で範囲が広すぎます。何より、この方法は素数でない数も引っかかってしまうもので、殊にいかなるフェルマーテストもすり抜ける「カーマイケル数」これの1つ561が範囲内にありますのでままなりません。
  • 第一原理法
    上2つの方法があてにならないということで、今回初めて開発した方法です。これはそう、言うなれば素数の定義、原点に立ち戻る画期的な方法です。すなわち、「素数とは、1とそれ自身の2個以外に約数を持たない数」これを判定しようということです。

ということで最終提出版Perl(51)

print++$i!~3-(grep$i%$_<1,2..$i)?lc:uc for(a..z)x50

はい。カウンタ$iに対して、2～$iの中で、$iの約数となっているものを数えています ( grepはスカラコンテキストでは条件を満たす要素の数を返します )。約数の数が丁度 1 の時が素数ということですね。

…。

…ああ、やめて、石を投げないで!! いやだって、実際にこっちの方が短かったんですし…。もちろん計算量的にはかなり悪いんですが、1300個位ならまあ、なんとかなるということです。

ただ、トップのtailsさんがPerl(49)まで縮めていたので結局追い付けず、でした。詳細はまだですがどうも factor を `` で呼び出す方法を採られたようです。

(2016/2/25追記) tailsさんに改良版 Perl(49) を提示して頂きました。うぉ…この路線で追い付けたのか…。

print$_^$"x++$.!~3!~grep$.%$_<1,2..$.for(A..Z)x50

違いに絞って説明しますと、

  • uc,lcによって大文字・小文字を使い分ける代わりに、空白を xor する
    ご存じPerlでは、文字列同士のbit演算ができます。で、空白(文字コード32)を xor ( orでも良さそう ) することで、大文字を小文字に変えることができます。
    Perlでは特殊変数$"の初期値は空白です。これを x 演算子によって0文字/1文字に調整することで、大文字・小文字の違いを生み出します
  • !~演算子の多用
    Perlでは、=~,!~ 演算子はかなり高い優先順位を持っています。なので、== や != 等々の代わりに使うことで、カッコ () を省くことができ、文字数を抑えられます。
  • $.特殊変数
    この変数自体に特に意味はないのですが、$i等の一般的な変数名だと for にそのまま繋げられません。なので区切りの空白1文字お得です。

(追記終わり)

その他の実装

提出はしませんでしたが、素直にprimeモジュールを使った実装のRuby(71)

require"prime"
1300.times{|i|putc i%26+(!"#{i+=1}"[?3]&i.prime??65:97)}

ただ、モジュール使わない方が短くて、少なくとも次のRuby(70)にはできます。正規表現による素数判定ですね。

1300.times{|i|putc i%26+("#{i+=1}"[?3]||?1*i=~/^(1|(11+)\2+)$/?97:65)}

( 2016/3/1 追記 )
集計が出て、Ruby最短のgmkさんのを見たところ、i の代わりに$.を使えば1文字節約できることが分かりました。なので、次のRuby(69)ができます。

1300.times{putc$.%26+("#{$.+=1}"[?3]||?1*$.=~/^(1|(11+)\2+)$/?97:65)}

( 2016/3/2 更に追記 )
rotary-oさん ( Groovy最短 ) から更に短縮したコードを教えていただきました。

1300.times{|i|putc i%26+(?1*-~i+"#{~i}"=~/3|-1$|^(11+)\1+-/?97:65)}

3を含むかどうかと1・合成数の判定を1つの正規表現にまとめたものです。~iで-(i+1)を作り出して連結しているのが洒落てますね。$.をインクリメントする方式でも行けますが、文字数的なアドバンテージは無いようです。
( 追記終わり )

一度提出した後縮めたBrainf**k(419)

10でのdivmodを繰り返して3を含むかどうかの判定を行うのと、試し割りによる素直な素数判定を行うものですね。流石に対象の数nに対して、除数dの探索範囲を$\sqrt{n}$までにしないと時間がかかり過ぎるので、先にunderflow検知機能付きの減算を使って$n-d\times d$を試してから、引っかからない場合だけmodを計算しています。
元々は偶数判定も入れて性能を稼いでいたのですが、省いてもTLEにならないことが判明したため ( 約0.3秒 )、こっちに切り替えました。

終わりに

執筆時点 ( 2016/2/24 ) ではまだ集計が出てないので…。トップが獲れないのは確定しているので…。決勝までにトーナメントで tailsさんに潰されないよう祈りましょう。( Perl参加者が増えてたらペナルティでおじゃんですが )

( 2016/3/1追記)
集計が出ましたが最初の方で負けてしまいました残念!! 各最短コードがまとめてありますのでご参考まで。

codeiq.jp