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

先制 hello, worldに参加しました

はじめに

CodeIQという所で開催していた「先制 hello, world」という、総当たり式変則コードバトルに参加しました。

codeiq.jp

出題者の@Nabetani 鍋谷さんは、これまでもこういった ( ゴルフやタイムアタックでない ) 変則的な、しかしながら面白いコードバトルを出題されています。
最終順位速報が出て、Perlで8位という結果になりました。本記事執筆時点 ( 2015/9/23 ) では、まだ詳細未公開ですが、途中で引っ込めたコード含め、少し解説したいと思います。

問題

レギュレーション

コード自体は、“preemptive "hello, world"”という、空白含め25文字を出力するのみ ( 末尾の改行は任意 ) で、ASCIIコード32~126 の範囲の文字しかコードに使えない以外、特に制限はありません ( ※文字数は一応10,000字が上限だと思いますが )。それもideone(CodeIQの実行くん)上で実行して標準出力への出力結果が合っていることのみの要求です。( この辺は地味に重要な条件です )

バトル

問題は、各参加者のコードで行うバトルの部分です。総当たり式で1対1のバトルを全参加者分行い、その勝敗に応じた勝ち点により順位が決めるため、自然「強い」コードを組む事が要求されます。で、その1対1バトルの決着方法ですが、自分なりに噛み砕いた内容としては、

  • どちらか一方のみがコード内で使用している文字については勝敗に影響しない
  • コード内で両者が使用している文字については次の通り
    • コード内で初めてその文字が現れる位置を、両者で比較する
    • 初めて現れる位置が遅い ( 1文字目から見てより遠い ) 方は、自コード内の同一文字の文字数を、自分のkilled countに加算
    • 初めて現れる位置が同じ場合は、それぞれのコードの同一文字の文字数を、それぞれ自分のkilled countに加算
  • 全ての文字種に対して上記計算を行い、killed countの少ない方が勝ち、多い方が負け。同じであれば引き分け。
  • 勝ち、負け、引き分けに対する勝ち点は、おおよそ 3:0:1弱。引き分け3つはほぼ勝ち1つに等しいが、微妙に及ばない。

ちなみに、この勝敗判定を行うツールとしてhttp://ideone.com/lqLMrLを作りました。標準入力に、両者のコードを1行ずつセットすれば、それぞれのkilled countを計算してくれます。

勝つためには

上記バトルの性質から、次のポイントが浮かび上がります。

  1. 自分の良く使う文字を早い位置に配置する。→ 自分のkilled countにカウントされないよう、防御用
  2. 相手の使いそうな文字を早い位置に配置する。→ 相手のkilled countを稼ぐよう、攻撃用
  3. コード中盤以降、1に該当しない文字は、なるべく相手の使わない文字を選択する。→ 防御しきれない分、攻撃を受けないためのお祈り用
  4. 1~3を考えた上で、トータルの文字数を減らせるなら減らした方が良い。

f:id:ange1:20150922090635p:plain この3,4の性質は、以前出題されたMinority's hello, worldに類似しています。なので、同じようなノリも要求されるのですが、それだけだと 2 が疎かになって、負けないけど勝てない、引き分けを連発することにもなりかねません。
また、1,2 はどちらもコードの先頭の使い方ということで競合しています。そのため、3も含めてバランスの取り方がかなり難しくなっています。
なお相手というのはと読み替えても同じです。順位は総当たりによる勝ち点の合計で行われるわけで、一部の特定の相手に勝利する事よりも、広く多数に勝利する方が優先されるからです。

ジョーカーの存在

問題発表時から、ある特定の言語がジョーカーになるという予感がありました。

それはBrainf**k。そして、優勝こそBashに譲ったものの、一時は上位を独占するという驚異的な強さを発揮しました。私もBrainf**kで途中3位~1位程度の上位に安定していることができました。ここでは、なぜBrainf**kが驚異的な強さを発揮したか、また最終日までの自分のBrainf**kコードについて触れます。

Brainf**kの機能

言語仕様についてはWikipediaにまとめてありますが、基本的な性質としては、

  • コードを構成する文字種は、+-<>[],. のたった8種類
  • 上記以外の文字は全てコメント扱い ( 無視される )
  • その代り、他の言語に比べて、非常に多くの文字数を必要とする

ということが挙げられます。文字数が多いために弱点をつかれる ( 相手に、早い位置で構成文字を使われる ) とあっさり負けてしまいますが、文字種が少ないこと自体は、高い防御力に直結します ( 他の人はBrainf**kだけを相手する訳に行かないのです )。またほとんどの文字を攻撃用に、任意の位置に配置できますから、非常に高い攻撃力も期待できます。

Brainf**kの戦略

絶対防御力

実は、Brainf**kは、最低限2種類の文字でレギュレーションを満たすことができます。.+ もしくは .- です。
出力を行う . は、現在地の値をASCIIコードとして putchar する訳ですが、この値は mod 256 で扱われます。すなわち、“preemptive "hello, world"”に沿って 112→114→101→… と値を上下させずとも、112→114→357→… という単調増加、もしくは -144→-398→-411→…という単調減少で値を変化させれば十分ということです。そのため、値を変化させるには +- どちらか一方で良い、と。
加えて「ideoneで実行させた時の出力」というのも重要で、NUL文字(ASCIIコード0)等を含めた非印字文字の一部は無かったことにできるので、最初にいきなり . で出力を行うことも可能です。よって、.+ / .- 他にも +. / -+. といった2~3文字で、自身の構成コードの防御が完了してしまいます。.+ で始まるコードの例はhttp://ideone.com/CaKHSKにあります。
Brainf**kに対抗するために先頭文字を . で始められる言語はかなり限定されますし、+- の2択だと50%の確実性、しかも .+- はあまり「使われる」文字ではないため、他言語用には役に立ちづらい。これがBrainf**kの絶対的な防御力の源泉となっています。 f:id:ange1:20150923082126p:plain

別の選択肢

というように考えていたのですが、別の選択肢もあることを教えて頂きました。

実装してみるとhttp://ideone.com/QADRPyのような感じになります。末尾に“[.<]”という出力ループ処理を持ってきて、それまで > と +/- で文字データを各所に配置する、という構成です ( > はポインタ変化、つまり演算位置の移動の機能を持ちます )。末尾の4文字は防御が効かない ( だからあまり考慮していなかった ) 代わり、. の代わりに > が使えます。最初に > を配置できる言語はちょっと思いつきませんから ( Falconはできるけど無駄が大きい… )、.+ .- よりもトータルの防御力は上かも知れません。
※ > の代わりに < を使う、すなわち <+ <- の場合は、PHPの1文字目の < に刺される可能性が残りますから、>+ >- の方が勝ると思います。

自分のコード

9/8集計時から、最終集計時 ( 締切直前 ) まで提出していたコードhttp://ideone.com/4cf3fZです。

.-" )2}【-と.によるコア】

という構成になっていて、3~7文字目の " 空白 ) 2 } の5文字を攻撃用にあてています。数字の2は、空白を16進 "\x20" で記述した場合や、" を16進"\x22"や8進"\42" で記述した場合の対策です。また、括弧を避けられない言語は多いですし、閉じ括弧を早い位置に配置するのは困難です。空白、" もなんだかんだでポピュラーです。なので、広く勝ちを稼ぐために攻撃はこれだけに絞って十分と考えていました。( あまり増やすと被告にされかねませんから )
これでずっと1~3位 ( 途中6位というのもあったけど ) だったので、まあ有効だったのだろうと思います。

最後に(続く)

詳細が公開されていないので、Perlのコードのネタバレはまだにしたいと思います。もともとBrainf**ckよりもPerlで勝負したいと思っていたのですが ( 最初ここまで強いと思っていなかったのと、Perlの吟味が遅れて最終日ギリギリになってしまった )、うーん。やはりBrainf**kや、それを抑えたBash、等々、には敵いませんでしたね。残念です。