はじめに

CodeIQというところで開催していた、他言語コードゴルフ、デスコロC #1 に参加しました。これは、以前のtbpgrさんによるデスマコロシアムを ciel さんが引き継ぎ、自動採点版とした新シリーズの1回目です。

結果、Rubyで175文字+ペナルティ20のスコア195の2位でチャンピオンバッジを頂きました。有難うございます。…ただ、トップのtailsさんにはダブルスコア ( 短い文字数程良いので、ハーフスコア?? ) 以上の大差なので、あまり手放しで喜べるところではないのですが。

問題

お題

以下の文字列 ( 1000文字 ) を、途中空白や改行を挟まず出力するというものです ( 末尾の改行は任意 )。入力はありません。

bPP00$zzzuuuVVUUUQQ11000vvvWWWVVVRRR22211wwXXXWWWSSS333222xxYYYXXTTT444333yyyZZZYYUUU555444zzzaaZZZVV66555000bbaaaWW7766111cccbbbXXX8887722dddcccYYY999888333eeeddZZZAAA999444ffeeeaaaBBBAAA555ggfffbbCCBBB666hhhgggccDDCC77iiihhhdddEEEDD88jjjiieeeFFFEEE999kkkjjfffGGGFFFAAAllkkkggHHGGGBBBmmlllhhIIHHCCCnnnmmmiiiJJJIIDDooonnnjjjKKKJJJEEpppookkkLLLKKKFFFqqqpplllMMMLLLGGGrrqqqmmNNMMMHHHsssrrrnnOONNIItttsssttoooPPPOOJJuuuuupppQQQPPPKKKvvvvvvqqqRRRQQQLLLwwwwwrrrSSSRRRMMMxxxxxssTTSSSNNNyyyzzzyyytttUUUTTOOPP000zzuuuVVVUUUQQQ11100vvvWWWVVVRRR22111wwwXXXWWWSSS33222xxYYXXXTTT444333yyZZYYUU555444zzzaaaZZVVV66655000bbbaaaWWW77766111cccbbbXXX88777222dddcccYYY99988833eedddZZAAA99944ffeeaaBBBAA555gggffbbbCCCBB666hhhgggcccDDCCC777iiihhhdddEEDDD888jjjiiieeeFFFEEE99kkjjjffGGGFFFAAAlllkkggHHHGGBBBmmmlllhhhIIIHHCCCnnnmmmiiiJJIIIDDDooonnnjjjKKJJJEEppoookkkLLLKKKFFqqppllMMMLLLGGGrrrqqmmmNNNMMHHHsssrrrnnnOONNNIIItttssstttoooPPOOOJJJuuuuuupppQQQPPPKKvvvvqqRRRQQQLLwwwwrrSSSRRMMMxxxxxxsssTTTSSNNNyyyzzzyyytttUUTTTOOO

判定は、CodeIQ の自動採点システム ( ideone企業版 ) による出力チェックで行われ、パスしたコードの言語/文字数がトーナメントにエントリーされる、という方式になっています。

謎解き

さて。今回難易度が高めという事で、「○○○○○っぽい方法で生成した文字列を○○○変換」というヒントが出ていたのですが…。結局謎は解けずじまいでした ( 詳しくは上にあるCodeIQ Magagineのリンクを )。見付けだした規則性、後半の○○○変換の何かと思っていたのですが、どうやら前半の「○○○○○っぽい方法」の性質が残っていたのにかろうじて喰い付いていたものと判明。結局開催期間中、全然先に進めず、途中で縮めての提出となりました。

当時の考察

観察

1文字目の b と、6文字目の $ が特殊なのですが、そこを無視して現れる文字のパターン ( 連続する文字数もさておき ) を見てみると、
P0zuVU → Q10vWV → R21wXW → … と言うように、6種の文字がどんどんずれていっているように見えます。同一の文字種としての終わりである 9,Z,z の次はそれぞれ A,Z,0 になっているようなので、0～9,A～Z,a～zの62文字で巡回しているのだろうと考えました。

ところが、途中でイレギュラーな部分にぶつかります。それは25組目 nnOONNIItttsss → 26組目 ttoooPPPOOJJu… の所。文字種の組合せはトータルでは1ずれではあるものの、出現順が内部で1ずれています ( nONIts→oPOJut ではなく toPOJu )。30組目 …xssTTSSSNNNyyy → 31組目 zzzyyytttUUUTTOO の所でさらに1ずれて、32組目からは元通り、その後また56→57組目、61→62組目で同じようなずれが見られます。なお、… としているのは、同じ文字がつながってしまい、組どうしの境目も分からなくなってしまうからです。

ただ、そのことに目を瞑れば、6種の文字がずれていくという規則性に変わりはありません。また、曖昧な組の境目も何とか区切れば、同一の文字種が2～3文字しか連続していないことに気付きます。

規則性まとめ

という事で、観察の結果見つけ出した規則性 ( イレギュラーも含め ) は次の通り。

同一の文字が2～3文字連続するブロックから構成される。
6ブロック単位で構成する文字が1ずつずれていき、0～9,A～Z,a～zの62種を循環する。
6ブロックを1組として、26～30組目・57～61組目は、文字種の現れる順番が1、31組目・62組目は2ずれる。
1文字目のb、6文字目の$ ( 同一文字種のブロックで言うと、1ブロック目と3ブロック目の先頭 ) は規則性にあてはまらない。

その後の方針

「同一の文字が2～3文字連続するブロック」という事で、情報量的にはちょうどブロックがbitに相当します。コーディングに非印字文字は使えないため1文字に8bitを詰め込むことはできませんが、6bitを1文字とすることは、別にBase64を使わなくとも可能です。なのでこれで6bit×62組を62文字にしてそこから次の規則性を探っていく…予定でした。

ただ、調べてみると、似たbitパターンが現れるものの、完全には同じではないため圧縮をかけても展開コードのコストでトントンになってしまうと言う。ここで行き詰ってしまったので、仕方なく現状のままコードを縮めて提出と相成りました。

コード

と、いう事でRuby(175)です。

372.times{|x|j=x/6%31;k=x-j/30-j/25+5;$><<"b\0$"[x]<<(?0..?z).grep(/[^_\W]/)[(j-5**k/4)%62]*('V^ykowV\yoww^XiowV\ykow^Xioww^y]}~rcO}}~sCM}~~sO]}~rcO}~~sCM}~'[x/6].ord[k%6]+2)}

なお P0zuVU のような6文字の組合せ ― 0～9,A～Z,a～z の中のオフセットで言うと、25,0,61,56,31,30 という組み合わせ ― ですが、定数配列で管理しても良かったのですが、ちょうど -(5**(i+5)/4)%62 という周期6の数列で生み出すことができるものですので、こちらを活用しました。また、6ブロック1組のbit列は、逆順にして64を足すことでASCII文字に変えています。bitが全て1というブロックは、境界の決め方をちゃんとすれば作らずに済むので、ASCIIコード64～126の印字文字の領域に収めることができます。ASCII文字からは、ordで文字コードの数値を取って、Rubyの[]演算子でbitをとることができるので、楽に処理ができます。

ネタバレ後

BWTはおろかブロックソートも知らなかったよ!! と、基礎の弱さを思い知らされた訳ですが。期せずして、コードを組む時に見つけた 5**k/4 ( %62 ) と言うのが、実は「線形合同法っぽい」の特徴を掴んでいたようです。以下ではそれについてちょっと触れます。

線形合同法っぽい値

想定解にある x=(65539*x+i)%62 ( xの初期値0、i=0,1,… ) という漸化式ですが、 $65539\equiv 5\,mod 62$ であることから、一般項 x=(5**(i+1)/4-(i+1))/4%62 ( i=0,1,… ) であることが分かります。
5のべき乗が、mod 31では周期3 ( 5→25→1 ) という短周期での変化を見せるため、xの値にもかなり短い周期での規則性が見られるようになっています。具体的には、(12個後のxの値)=((今のxの値)+28 )%62 といった具合です。