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

『第10回デスマコロシアム』に参加しました

デスマコロシアムとは(テンプレート)

大雑把に説明すると、

  • 問題文で与えられたある文字列を出力するコード(プログラム)を提出する。
  • 言語は ideone で利用可能なものから選ぶ。
  • コードのサイズが短いほどよい。(1文字につき1点減点)
  • 同じ言語を選択した人が少ないほどよい。(1人につき10点減点)
  • その他、コーディングとは無関係な運の要素も加えて、トーナメントで競う。

といった感じです。要するに、コードゴルフに運の要素を加えたトーナメントです。

第10回の問題

treetreetreefiregoldtreetreetreetreegoldtreegoldtreegoldtreegoldtreegoldtreetreegoldtreegoldtreetreetreegoldtreetreetreewaterwatertreetreewatergoldgoldtreegoldtreegoldtreegoldtreegoldtreetreegoldtreegoldtreetreetreegoldtreetreefiregoldgoldwatermoontreemoontreegoldgoldtreewatergoldgoldtreetreegoldgoldtreetreemoonwatergoldgoldwatergoldtreetreemoongoldgoldmoon

という文字列を出力するという問題でした。この文字列は、 { moon, fire, water, tree, gold } の中から要素を88回選んで連結したものになっています。 /^(moon|fire|water|tree|gold){88}$/ にマッチする、と言ったほうがわかりやすいでしょうか。具体的にどのように作られた文字列なのかは、出題者の tbprg さんによる結果記事で説明されています。


「第10回デスマコロシアム」問題のトーナメント結果発表です!~優勝者は…!|CodeIQ MAGAZINE

さて、Perl (78) が気になると思いますが、まずは初日に提出した比較的わかりやすい Perl (81) について、仕組みと作り方を説明します。その後で Perl (78) を説明します。

Perl (81)

use v5.10;
say+((moon,fire,water,tree,gold)x60)[unpack C88,'伊畏伊!一!逸一逸伊袷仮!一!逸一逸鞍}援違仮/`依}/泳A']

(Ideone で開く → http://ideone.com/9yGZzt

初日に提出した Perl (81) です。最初の use v5.10; の行は文字数カウント外です。

デスマコロシアムはコードの長さをバイト数ではなく文字数で数えますが、 Ideone はコード中の文字を UTF-8 で扱うため、日本語文字を使えば1文字で3バイトを表現できます。これは第4回デスマコロシアムでも使用したテクニックですが、今回もこれを利用しない手はありません。

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

上記のコードの文字列

伊畏伊!一!逸一逸伊袷仮!一!逸一逸鞍}援違仮/`依}/泳A

は、日本語 29 文字+ASCII 1 文字で88バイトです。これを unpack C88 でバイト値のリストに分解しています。このバイト値それぞれの mod 5 を取り、その結果を moon, fire, water, tree, gold に対応付ければ結果の文字列が得られるのですが、 mod 5 を取る代わりに moon, fire, water, tree, gold のリストを60回繰り返したものと対応付けることで文字数を少し稼いでいます(60は適当な値です)。

Perl (81) コードの作り方

イデアは上記の通りなのですが、ではどのようにしてこのコードの文字列を作ればいいのでしょうか。 Unicode文字コード表を眺めながら条件に合う文字を1つずつ拾っていってもいいのですが、数が多いですし、あの CodeIQ の解答欄の悪名高い機種依存文字」判定のせいで、使いたいコードの文字が自由に使えないため、イラつくこと間違いありません。なんとかして自動化したいものです。

そこで今回私が取った方法は、一言でいうと「JIS文字コード表を UTF-8 で保存し、そこから文字を拾う」というものです。JIS第何水準とかよくわかりませんが、まあ普通のJIS文字コード表に載っている字は問題なく使えるだろうという判断です。以下、少し具体的に説明します。

まず、JIS文字コード表を用意します。これは Google で「JIS文字コード表」で検索すればいくらでも出てきます。そこから良さそうなものを1つ選んで、表の部分をテキストファイルにコピペすれば、UTF-8エンコードされたJIS文字コード表がすぐに作れます。

この文字コード表を利用して、出力文字列を日本語文字列に変換します。具体的には、次のようなスクリプトになります。

# 文字コード表(ファイル名 "kanji" )から1文字ずつ連想配列 %k に格納していく。
# 改行とかコードの値とかの余分な文字が混ざっていても読み飛ばすので気にしなくてよい。
# 入力を reverse することによって、コード表で先に登場する文字が優先的に使用される。
{
    my $h;
    open($h,"kanji");
    for(reverse<$h>){
        while(/([\xe0-\xff])(.)(.)/g){
            $k{ord($1)%5 .ord($2)%5 .ord($3)%5}=$&;
            ++$count;
        }
    }
}
# 何文字読めたか確認。インデックス重複分を含む。
print($count,$/);

# お題の文字列。
$_='treetreetreefiregoldtreetreetreetreegoldtreegoldtreegoldtreegoldtreegoldtreetreegoldtreegoldtreetreetreegoldtreetreetreewaterwatertreetreewatergoldgoldtreegoldtreegoldtreegoldtreegoldtreetreegoldtreegoldtreetreetreegoldtreetreefiregoldgoldwatermoontreemoontreegoldgoldtreewatergoldgoldtreetreegoldgoldtreetreemoonwatergoldgoldwatergoldtreetreemoongoldgoldmoon';

# お題の文字列を 0 ~ 4 に変換。
s/moon/0/g;
s/fire/1/g;
s/water/2/g;
s/tree/3/g;
s/gold/4/g;

# 変換済みのお題から3文字ずつ拾ってエンコード。 while($_ ne ""){ if(/.../ && $k{$&}){ print($k{$&}); }elsif(/./){ print(chr(65+$&)); } s///; }

これであの

伊畏伊!一!逸一逸伊袷仮!一!逸一逸鞍}援違仮/`依}/泳A

という文字列が得られました。めでたし、めでたし。

ところで、この結果の文字列には記号がいくつか含まれていますが、これは、スクリプトのコメントにも書いたように、文字コード表の上のほうの文字を優先的に使うようにしたためです。しかし、単純に文字コード表の下のほうの文字を優先させると、「齊」とかの難しい漢字(第2水準?)ばかりが使われることになって微妙です。そこで、文字コード表を加工して、記号を下のほうに移動しておけば、簡単な漢字が優先的に使われて、文字列部分のみが異なる次のようなコードが得られます。

use v5.10;
say+((moon,fire,water,tree,gold)x60)[unpack C88,'伊畏伊威一威逸一逸伊袷仮威一威逸一逸鞍偉援違仮壊夷依偉壊泳A']

(Ideone で開く → http://ideone.com/dz67QP

Perl (78)

上記の (81) のコードでは3ワードを1文字でエンコードしていますが、このまま頑張ってもこれより縮みそうもありません。もっと縮めるためには1文字でエンコードするワード数を増やさなければならないようです。

そこで、1文字で5ワードをエンコードするようにして作ったのが、次の Perl (78) のコードです。

use v5.10;
say+((gold,tree,water,moon,fire)x35)[map{ord,7&ord}'桐案閑卦卦斡牒呑刈鍍桑鐇ネ咥或鏥疫尻'=~/./g]

(Ideone で開く → http://ideone.com/i5FW0b

1つのバイト値を、そのまま(ord)と、8で割った余り(7&ord)とで2回使っています。ただし、UTF-8の各文字の先頭バイトは日本語文字に割り当てられているレンジが狭く(0xe3~0xe9の間くらい?)、2回使うのは現実的ではありません。そこで、このレンジの「そのまま」の値は無視されるようにリストの繰り返し回数を制限してあります。2バイト目と3バイト目は 0x80~0xbf の間くらいなので、「そのまま」の値もどれかのワードに対応します。

ところで、ワード数の88は5で割り切れません。そこで、リストの繰り返し回数をさらに制限し(35回繰り返しで要素数 0xaf )、2バイト目と3バイト目の「そのまま」の値も無視される場合があるようにしました。具体的には、最後の「尻」という文字は、2バイト目(0xb0)と3バイト目(0xbb)の「そのまま」の値が無視されて、3ワードをエンコードするようになっています。

イデアは以上ですが、実際には1文字で5ワードをエンコードするのは難しく、ワードの順序(gold, tree, water, moon, fire)を工夫する必要がありました。前述の Perl (81) を作ったときのスクリプトを改造して、1文字を5ワードに対応させるとともに、ワードの順序も固定ではなく120通り全て試して、うまくいったものを出力するようにしました。

なおさんの Perl (78)

use v5.10;
say map{(fire,gold,water,moon,tree)[vec('驛乾ddd鑑鑞"休斑派乙`!蝶α仔#ab丁',$_,4)%5]}0..87

結果記事で紹介されている、なお(naoki_kp)さんのコードです。なんと驚くことに、1文字で6ワードをエンコードしています。これは思い至らなかったので、このコードの長さに並ぶことができたのはラッキーでした。 "α" は2バイト文字(0xce, 0xb1)のようです。