『第4回デスマコロシアム』私の Perl (57)

CodeIQ

はじめに

『第4回デスマコロシアム』に参加しました。今回のルールは、

  • $&(*,.02468:<>@BDFHJLNPRTVXZ\^`bdfhjlnprt$(,048<@DHLPTX\`dhlpt$*06<BHNTZ`flr$,4<DLT\dlt$.8BLV`jt$0<HT`l$2@N\j$4DTdt
    という文字列を出力するプログラムを書く
  • 評価基準は【文字数×(重複文字数+1)】が小さいほど良い
  • 言語ペナルティやトーナメントはいつもと同じ

といったところです。要するに、短くて、しかもなるべく同じ文字を使わないものが高評価ということです。

出題者様による結果記事
https://codeiq.jp/magazine/2014/07/12364/

私は、最終的に Perl (57) でエントリして、最小賞をいただきました。前々回と前回に続いて、3度目の最小賞受賞です。おめでとうございます。ありがとうございます。

結果の公開後、私のコードに対して、ツイッター上で「すごい」「頭おかしい」「変態」など、見ず知らずの多くの方々からお褒めの言葉をいただきました。ゴルファー冥利に尽きます。

コードとその解説

私が提出した Perl (57) のコードは、次の通りです。

eval
q<悃int ch掃雛_四郎囎2抛36f恃雎刈40/把郛;>=~y{遂胄刊掛}[$o-s*.+]drx8

文字数 57、重複文字 0で、大きさは 57×(0+1) =57 です。

文字化けしているわけではありません。わけがわからないと思いますが、正直、書いた本人にもさっぱり読めません。ともあれ、１つずつ解釈していくことにします。

まず、

y{遂胄刊掛}[$o-s*.+]dr

の部分を見てみましょう。 Ideone.com では、日本語文字は UTF-8 として解釈されますから、1文字につき3バイト（例えば「遂」という文字は \xe9, \x81, \x82 の3バイト）です。 Perl の y/// は、どうやらマルチバイト文字は特に認識せずに、単純にバイト単位で置換を行うようで、この置換の対応を表にすると次のようになります。

元の文字置換後の文字
遂 \xe9 $
\x81 o
\x82 p
胄 \xe8 q
\x83 r
\x84 s
刊 \xe5 *
\x88 .
\x8a +
掛 \xe6 （削除）
\x8e
\x9b

この置換を、

悃int ch掃雛_四郎囎2抛36f恃雎刈40/把郛;

という文字列に適用しています。（なお、コードでこの文字列を囲んでいる q<......> というのは、展開を伴わない文字列を表す '......' の別記法です。）例えば先頭の「悃」という文字のバイト値は \xe6, \x82, \x83 なので、上の表によって pr という2文字に置換されることがわかります。文字列全体を置換すると、

print chr$_*$r*2+36for$*..40/++$r;

という文字列になります。

この文字列、どこかで見たな… という鋭い方もいらっしゃるかと思います。そう、結果記事で解説されている antimon2 さんの文字列とほとんど同じなのです（こういう一致は嬉しいですね(^^)）。違いとしては、私の文字列では、 $k が $r に、  0 が $* になっていますが、置換の圧縮効果のため、私の解法ではこのほうが文字数的に有利なのであって、コードとしての意味は一緒です。

この後のプログラムの動作は antimon2 さんの解説の通りで、 y/// に r オプションを付けることで結果の文字列を取得し、それを x8 で8回繰り返し、それを eval で評価しています（詳しくは結果記事の antimon2 さんの解説を読んでください…）。めでたし、めでたし。

結局、置換対象を日本語文字で表現する解法には、

  • 同じバイト値を複数回使っても、組み合わせを変えて別の文字にすることで、重複文字になるのを回避できる。
  • 最大でコード3文字を日本語1文字で表現できるので、圧縮が効く

という一石二鳥の利点があります。ちなみに、 NeoCat さんも全く同じアプローチだったようです。

余談：「機種依存文字」

ところで、デスマコロシアムの解答のルールとして、 CodeIQ の入力欄で「機種依存文字」と判定される文字は使用禁止という制限があります。これは問題文には記載されていない（出題者様のブログのQ&Aに記載されている）細則なのですが、今回はこの細則が本質的に重要だったように思います。というのも、「機種依存文字」でない漢字は、 Unicode のコードポイントにおいて飛び飛びに（しかも不規則に）存在しているため、任意の3バイトを組み合わせた文字が解答で使用可能とは限らない（むしろ使用不可能な文字の方が圧倒的に多い）からです。

そこで、私の解法では、手探りでいろいろ試行錯誤して「遂」「胄」「刊」「掛」の4文字を選び、これらを構成するバイト値を組み替えて文字列を表現することにしました。その結果、日本語文字1文字でコード3文字を表現できたのは「刈」→ *.. の1か所だけで、他は全て1文字で1～2文字しか表現できていない、非効率なものになってしまっています。日本語文字の選択や置換の割り当てを最適化するツールを作って文字列を生成すれば、もっと短い解が得られたはずだと思いますが、今回は解答期間の多くを nasm での解の短縮につぎ込み、この Perl の解は途中集計の最終回になんとか間に合わせたため、そこまでする余裕がありませんでした。（解答をファイルでアップロードする形式か、 Ideone.com のURLを解答する形式だったら、「機種依存文字」を気にしなくていいので、もう少し楽ができたなあ…と思います。）