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

CodeIQ

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

大雑把に説明すると、

  • 問題文で与えられたある文字列を出力するコード（プログラム）を提出する。
  • 言語は 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）のようです。

『そろばんのダンジョン』私の解答

CodeIQ

テンプレ

この問題（に限らずダンジョンシリーズ）の面白いところは、定められた文字数制限と使用禁止文字列を満たす JavaScript のコードを提出すれば正解となってバッジが付与されるのですが、実際には場外（Twitter とか CodeIQ MAGAZINE とか）で出題者様主導で解答コードの短さが競われているのです！ いわゆるコードゴルフです。このことは問題文には一切書かれていなくて、バッジほしさに適当に解答を送ると、知らずにコードゴルフに引きずり込まれるという、恐ろしい罠が仕掛けられているのです！

はじめに

今回は『そろばんのダンジョン』というお題でした。 0 ～ 999 の整数 i が与えられたときに、その整数を表すそろばんの珠の並び r を求めるというものです。例えば i が 7 の場合は、 5 の珠 1 個と 1 の珠 2 個なので、 r は "12" となります。 i が 12 の場合は r は "0102" 、 i が 999 の場合は r は "141414" です。 i が 0 の場合は r は "00" です。より正確なルールは、 CodeIQ MAGAZINE の公式解説記事をご覧ください。


大人気ダンジョンシリーズ！そろばんのダンジョンLV1～LV2の解説+最短コード発表 #javascript｜CodeIQ MAGAZINE

以下では、私が提出したコードについて、どのようにそのコードに至ったのかなどの説明をしたいと思います。

LV1

LV1 は、 eval や Function などいくつかの禁止文字列が設定されているものの、ほぼ無制限です。

37文字（4位）のコード

for(x=i;r=[x/5&1]+x%5+[r],x=x/10|0;);

解説記事で、 for 文を使った方法で最短として紹介されたコードです。このコード自体はどうということはないのですが、頂いたフィードバックで事件は起きました。

「for of」文と非常に短い計算で、上手く処理を組み立てていました。

上記コードで用いられているのは for of 文ではなく for 文であり、フィードバックは単なる書き間違いだろうと思います。ところで、 for of 文の存在自体はググって知っていましたが、一度試してみたときにうまく動かなかったので、このフィードバックを頂くまで、 for of 文は使えないものと思い込んでいました。しかし、本当に使えないのなら、例え間違いであってもこのようなフィードバックを頂くはずがありません。 for of 文は使えるのです！

30文字（1位）のコード

for(d of''+i)r=[r]+[d/5&1]+d%5

そんなわけで for of 文が使えることに気付いて書いたのがこのコードです。ちょっとずるい気もしますが、ともあれ無事に最短コードに並ぶことができました。

LV2

LV2 は、 LV1 の禁止文字列に加えて新たに ( ) { } が禁止されています。私のコードの動作については、大変ありがたいことに、解説記事の中で出題者様が確認コードを書いて下さっています。私自身もはっきりわかって書いていたわけではないので、なるほどこうなっていたのか！というのが正直な感想ですｗ

「無双」と評された64～59文字（5～1位）のコードは、考え方は一切変えずに書き方を工夫していった（そして縮むたびに提出した）だけですので、順を追って見ていくことにします。

64～62文字（5～3位）のコード

r=i*200-i%500*100-i%100*80-i%50*10-i%10*8-i%5;r='.'+i<.5?"0"+r:r

r='.'+i<.5?'0':0;r+=i*200-i%500*100-i%100*80-i%50*10-i%10*8-i%5

r='.'+i<.5&&'0';r+=i*200-i%500*100-i%100*80-i%50*10-i%10*8-i%5

書き方が少しずつ違っているだけで、やっていることはどれも一緒です。 r の値を十進数の数値計算で求めて、必要に応じて先頭に "0" を付加しています。少し具体的に説明します。

（１）先頭の "0" の判定

答えを数値計算で求める関係上、 r の先頭が "0" になる場合には、その "0" を明示的に付加しなければなりません。 r の先頭が "0" になるのは、 i の最上位の桁の値が 0～4 の場合です。これを、

'.'+i<.5

という式で判定しています。つまり、 i の先頭に小数点を付けて、その結果が数値的に 0.5 より小さければ r の先頭に "0" が必要と判断しています。

（２）数値計算

胆となる計算の部分です。どのコードも共通で

i*200-i%500*100-i%100*80-i%50*10-i%10*8-i%5

となっています。これをどのように導出したのでしょうか？

基本的な方針は、「先に大雑把な値を求めて、細かい部分はあとで微調整する」です。つまり、 r の上位の桁から下位の桁に向かって辻褄を合わせていくことにします。

r の最上位は、500の珠の数です。 r の最上位だけが異なる2つの i を考えてみます。例えば

  • i == 499 → r = "041414"
  • i == 999 → r = "141414"

なので、大雑把に「 i が 500 増えると r が 100000 増える」と言えます。言い替えると「 i が 1 増えると r が 200 増える」となります。これが、上記の式の先頭の項 i*200 というわけです。

次に、 r の上から2桁目、100の珠の数を考えます。これも先程と同様に

  • i == 899 → r = "131414"
  • i == 999 → r = "141414"

ですから、大雑把に「 i が 100 増えると r が 10000 増える」すなわち「 i が 1 増えると r が 100 増える」となります。ところで、 r の最上位考えたときに i*200 としてしまいましたから、 r の最上位が変化しない場合には i*200 - i*100 = i*100 分が多すぎることになります。これを調整するのが、2番目の項 -i%500*100 というわけです。

このような調整を r の最下位の桁まで繰り返すことによって、最終的な式を得ることができます。確かめてみてください。

ここで、またも事件が起きます。じつは、これらのコードを提出したときまでは、 { } ではなく [ ] が禁止文字列だと勘違いしていたのでした！

61文字（2位）のコード

r=[i]<'5'&&'0';r+=i*200-i%500*100-i%100*80-i%50*10-i%10*8-i%5

コードを縮めようといろいろ試行錯誤しているときに、うっかり、禁止文字であるはずの [ ] を使ってしまい、提出してしまいました。テストページの判定がバグっているだとか、提出を無かったことにしてくれだとか、 Twitter でひとしきり大騒ぎした後、ただ自分が禁止文字を勘違いしていただけだと判明してかなり恥ずかしかったですし、今まで勝手に一人縛りプレイをやっていたと知って愕然としました。 [ ] は使えるのです！

59文字（1位）のコード

r=[[i]<[5]?0:r]+[[[i*2-i%500]+0-i%100*8-i%50]+0-i%10*8-i%5]

これまで禁止文字だと思っていた [ ] を、思う存分使って縮めてみました。なんと 6 組も使っています。前述の（２）の計算式

i*200-i%500*100-i%100*80-i%50*10-i%10*8-i%5

は、自明に

[[i*2-i%500]*10-i%100*8-i%50]*10-i%10*8-i%5

と書き換えることができます。これだけだと短くも長くもなっていませんが、 […]*10 は要するに数値の右に "0" を付けるということなので、 […]+0 とも書くことができます。これを利用して

[[i*2-i%500]+0-i%100*8-i%50]+0-i%10*8-i%5

と書き換えることができ、2文字も縮めることができました。

おわりに

楽しかったです。

『正規表現でどう書くの？』ひねくれた別解

CodeIQ

（※ジョーク記事です。）

問題及び模範解答

増井雄一郎(@masuidrive)さんの「正規表現でどう書くの？」問題解説記事 #正規表現｜CodeIQ MAGAZINE より：

（引用ここから）

問題

Perl、Rubyの最新版でサポートしている正規表現を利用して、下記の条件にマッチするようにア、イ、ウを埋めて下さい。

正規表現: “123456″ =~ /([0-9]+ア)/
条件: $1 == “1″

正規表現: “123456″ =~ /(イ[0-9]+ア)([0-9]+)/
条件: $1 == “23456″

正規表現: “123456″ =~ /123(ウ45)4/
条件: マッチする

正規表現: “123456″ =~ /123(ウ45)6/
条件: マッチしない

解答

ア：?
イ：?:
ウ：?= （もしくは、?<!）

（引用ここまで）

（まともな）別解現る 

ひねくれた別解

私も別解を考えてみました。方針としては、模範解答がいずれも「?」を含んでいるので、「?」を使わない方向で。

ア：A|1*
イ：23456)(　もしくは　\B.*)(
ウ：|A

Ideone で実行：
http://ideone.com/nZojmy

どうだエヘン！

ちなみに、動作確認は Perl でのみ行っています。 Ruby のことは知りません。

以下、一応説明です。

１つ目の式：
“123456″ =~ /([0-9]+A|1*)/

説明：「A」は、文字列に現れない文字なら何でもいいのですが、ともかくこれで | の左側はマッチしないのでキャンセルできます。結局 $1 は 1* にマッチする "1" になります。

２つ目の式：
“123456″ =~ /(23456)([0-9]+A|1*)([0-9]*)/

説明：$1 == "23456" になるようにするのですから、先頭に (23456) と書いてしまうのが素直な書き方というものです（多分ね！）。ちなみに $2 と $3 には空文字列がマッチします。

３つ目・４つ目の式：

"123456" =~ /123(|A45)4/
"123456" =~ /123(|A45)6/

説明：これも「A」はほぼ何でもよく、 | の右側をキャンセルしています。これで、上側の式は "1234" の部分がマッチしますが、下側の式はマッチしません。

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

CodeIQ

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

大雑把に説明すると、

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

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

第6回の問題

今回の出力は

2:3:5:7:11:13:17:19:23:29:31:37:41:43:47:53:59:61:67:71:73:79:83:89:97:101:103:107:109:113:127:131:137:139:149:151:157:163:167:173:179:181:191:193:197:199:211:223:227:229:233:239:241:251:257:263:269:271:277:281:283:293:307:311:313:317:331:337:347:349:353:359:367:373:379:383:389:397:401:409:419:421:431:433:439:443:449:457:461:463:467:479:487:491:499:503:509:521:523:541:547:557:563:569:571:577:587:593:599:601:607:613:617:619:631:641:643:647:653:659:661:673:677:683:691:701:709:719:727:733:739:743:751:757:761:769:773:787:797:809:811:821:823:827:829:839:853:857:859:863:877:881:883:887:907:911:919:929:937:941:947:953:967:971:977:983:991:997

という文字列です。997以下の素数を ":" で区切ったものになっています。ちなみに、私の出題予想はフィボナッチ数列でした。

素数列も一瞬頭をよぎったのですが、言語によっては素数が組み込みで用意されていて単に出力するだけになってしまうので、まあ無いだろうと思って脳内却下したのですが…

というか、むしろ Perl を除け者にするための問題としか思えないのですが！

私が提出した解答

1. Perl (45)

期待されては、本気を見せざるを得ません。本気の Perl (45) を提出しました。

$,=":";print grep+(1x$_)!~/^(11+)\1+$/,2..999

正規表現で素数判定するコードです。具体的には、2～999の範囲の整数 $_ が素数かどうかを判定するために、 1x$_ で 1 を n 個並べた文字列を作り、その文字列が 2 文字以上の文字列の 2 回以上の繰り返しになっているかどうかを判定しています。ちなみに、私が最初にこの方法を知ったのは、 tybalt89 さんのこのコードです。感動したのを覚えています。
http://golf.shinh.org/reveal.rb?Gaussian+Prime/tybalt89_1323996492&pl

2. Perl (44)

Perl (45) は本気のコードのはずだったのですが、翌日になって見直してみたらあっさり縮んでしまい、 Perl (44) を提出しなおしました。素数判定の方法は同じです。

print 2,map":$_"x(1x$_)!~/^(11+)\1+$/,3..999

なお、同日に Octave (26) を提出したため、この Perl (44) は集計に反映されませんでした。

3. Octave (26)

この時点での集計では Octave (27) が最短でした。最短賞狙いの私としては、早速試してみたのですが、リファレンスとにらめっこしつつどう書いても (34) より短くなりません。

printf("%d:",primes(991));disp 997

ヒントを求めていろいろやっている中、 Google で「octave delimiter」で検索してみたところ、このようなページが見つかりました。
GNU Octave: Simple File I/O
これぞ求めていた情報です！

dlmwrite(1,primes(999),58)

dlmwrite という関数は、指定した区切り文字を用いて出力するという、まさにこの問題のために存在するような関数です。短くならないわけがありません。ていうか、このコードは (26) なので、最短更新です。喜び勇んで提出しました。

この後しばらく、最短は Octave (26) で動きがなく、今回の最短コードはこれで決まりかと思われたのですが…

4. Perl (5)

と、トップが変わるですと！？

本当だ！ しかも、よりによって Ruby ですか！ Ruby は触ったことがないので、さっぱりわからりません（ゴルフで Ruby が Perl より有利になることなんて滅多にないのでスルーし続けてきました）。困った…。

ところで、細則を利用して賢く文字数を稼ぐって、どういうことでしょうね？ 短縮に使えそうな細則といえば、モジュールのインポートくらいでしょうか。モジュールを賢くインポート… って、もしかして、 Perl で書けば、こういうこと！？

use 5.01;
use constant a,"2:3:5:7:11:13:17:……中略……:991:997";
say a

1行目はひとまず置いておくとして、2行目は constant.pm というモジュールをインポートしていますが、（当時の）細則によればこれは文字数にカウントされません。結局、このコードの長さは、3行目だけがカウント対象なので (5) になってしまいます。

まあ、当然のごとく、この解答は却下され、モジュールのインポートの際にパラメータを渡した場合には文字数にカウントするというルールが整備されることとなりました。

5. Ruby (22)

どうやら最短を目指すためには Ruby を書かなければならないようです。 Ruby には手を出さないというアイデンティティと、デスマコロシアムは最短賞・最小賞を獲りに行くというアイデンティティとが、激しくコンフリクトしています。まあ、少しやってみて駄目だったら諦めるということで…

Ruby での短縮ということで、まず思ったのが goruby です（こんなことだけは知っている）。 goruby 自体はコマンドですが、モジュールとしては golf_prelude.rb というものになるようです。しかし、このモジュールは Ideone にはインストールされていないようです。

ということは、別のモジュールでしょうか。とりあえず Ruby の標準モジュールを片っ端から見て回ることにします。何せ Ruby を触るのはほぼ初めてなので、どのようなモジュールがあるのかさっぱり知らないのです。 CSV モジュールとかは Octave の dlmwrite に似ていて怪しい気もしますが、どうもコンマ区切り専用のようで、使えそうもありません。むむ…

まあ、とりあえずモジュールのことは置いておいて、普通に書いてみましょうか。ええとなに、 Prime は Enumerable で Object なのか。さっぱりわからんが、こんな感じ？

require 'prime'
$><<Prime.take(168)*?:

おや！？ 普通に (22) で書けてしまいました！ うわ、モジュールのドキュメントをひたすら読みまくったあれは一体何だったんだ…

結果

Ruby (22) でなんとか無事に最短賞を獲得できました。デスマコロシアムでの最短賞・最小賞は、これで5回連続5回目です。おめでとうございます。ありがとうございます。せっかくなので、これからもトーナメントそっちのけで最短賞・最小賞を狙っていきたいと思います。

『ワンライナーでクールに解く！』所感（ネガティブ注意）

CodeIQ

はじめに

CodeIQ で『ワンライナーでクールに解く！』と題した2問の出題に解答してみました。どちらも、与えられた問題の答えを解くためのワンライナーを書けという問題です。「解答評価のポイント」は「冗長さをそぎ落とし、どれだけ簡潔に問題を解決できているかが評価のポイントとなります。」とのことです。（この「解答評価のポイント」は、次のリンクから読むことができます。）

挑戦者求む！【プログラミング】ワンライナーでクールに解く！その１ by 無形ソフトウェアLLC 代表社員：村山 男也│CodeIQ

挑戦者求む！【プログラミング】ワンライナーでクールに解く！その２ by 無形ソフトウェアLLC 代表社員：村山 男也│CodeIQ

その１

問題

「一番大きいマトリョーシカの中に、6つの少しずつ小さなマトリョーシカが入って10500円で売っています。（マトリョーシカは全部で7つです。） マトリョーシカはひとつ大きくなるにつれて、150円ずつ値上がりします。一番小さなマトリョーシカの値段はいくらですか？」

要するに、等差数列の総和が与えられたときの初項を求める問題です。

私の解法

真ん中の大きさ（小さいほうから4番目）のマトリョーシカが 10500 / 7 円なので、それより3つ小さい一番小さなマトリョーシカは 10500 / 7 - 150 * 3 円です。これを Perl ワンライナーで素直に書くと、

perl -e 'print 10500/7-150*3'

となります。これが私の解答です。これ以上、複雑になりようがありませんね。逆に、これ以上簡単にしようとすると単に答えを表示するだけになってしまうので、まあこんなもんでしょう。

評価結果

評価は「4」でした。

今回はプログラム言語のワンライナーというカテゴリーですので、 ループ処理や組み込みのリスト演算などをクールに使用している 回答者様に高得点を差し上げております。ご了承いただければ幸いです。

とのことで、「高評価を獲得した解答例」として示されていたのが、次のコードです。

perl -e 'for($n=10500,$i=0;$i<7;$n-=150*$i++){}print $n/7'

…へ？

まあ確かにワンライナーですが、なんというか、普通のスクリプトから改行を機械的に取り除いただけですよね。

ていうか、「冗長さをそぎ落とし、どれだけ簡潔に問題を解決できているかが評価のポイント」じゃないんですか？ 上記の「高評価を獲得した解答例」は、むしろ可能な限り複雑に書いてあるようにしか見えないんですが。

まあ、どのようなコードを「クール」と感じるかは人それぞれなのでそれはいいのですが、評価基準を示した以上、それに従って評価してもらわないと困ります。これではただの価値観の押し付けです。ともあれ、この問題や評価からは、出題意図がさっぱり見えてきません。

その２

問題

「1個の値段が40円、50円、77円の品物を合わせて11個買ったところ、代金が601円になりました。それぞれ何個ずつ買いましたか？」

私の解法

これは非常に困りました。ワンライナーで書くのに適したような簡単な解法を思いつかなかったからです。

ところで、「解答評価のポイント」には、「変数名などにキラリと光るネーミングセンスを感じるものなどは、高評価につながります。」とも書いてあります。そこで、変数名（の扱い）に趣向を凝らして、こんなコードにしてみました。

perl -e '@a=(50,40,77);$n50=11;do{$total=0;$total+=$_*${n.$_}for@a;++${n.$a[$cond=$total<=>601]};--$n50}while$cond;print"$_=>${n.$_}\n"for@a'

到底ワンライナーと呼べるような代物ではありませんが（それこそ改行を機械的に取り除いただけ）、簡単な解法を思いつかないので、仕方ありません。しかも、趣向を凝らしたせいで、可読性もさっぱりです。

評価結果

Perlの特徴を思う存分に発揮されており、文句なしの「5」評価です。

なんと、気に入られてしまいました。どうも、こういうコードが「クール」なようです。どうも私とは価値観が正反対です。

まとめ

結局、この出題者は、どのような意図でこれらの問題を出し、解答者に何を求めたかったのか、さっぱりわかりません。

CodeIQ では、以前にもひどい問題が出されたことがありますが（ボゴソートの計算量のやつとか）、 CodeIQ の中の人は、もっと問題や評価の質に気を配るべきだと思います。出題の質が低下したときに、最初に離れていくのは、スキルの高いユーザです。自分よりレベルが低い（と感じる）出題者から評価を受けようなどと思う人はいませんから。つまり、 CodeIQ の存在価値を維持し高めていくためには、出題の質は非常に重要だということです。

 

誕生日

誕生日

誕生日でした。ある意味、今までで一番賑やかな誕生日だったように思います。
もしかして：モテ期到来？

あ、今日、誕生日だ。と思って何となくつぶやいたのです。そしたら、

いや、神だなんて！ 私は、ただ、短くて、小さいだけです。私がというか、私のが。それを、なぜかみんな褒めてくれるんです。

お祝いコード

お祝いコードをいただきました。

いきなり Lazy-K ですね。以前、誰かが確か「Lispがバイナリダンプのような言われようだ」と言ったのに対して「バイナリダンプがSKIコンビネータのような言われようだ」と返したのを思い出します。ていうか、 Lazy-K は私が挫折した言語の一つです。素晴らしいです。ありがとうございます！

ありがとうございます！ ていうか、なぜ修造ｗ
それにしても、皆さん難解言語好きですねｗ

↑これではあんまりなので、私も難解言語で返事を書いてみました。

00607988772869385095152818394450817988297758363+9*+P1^6?77*3-c

Hack VM という処理系用の言語です。
Hack VM - A Virtual Machine for Hackers
実行方法は、↑このリンクのページの「Enter your code here」の所に上のコードをコピペしてから「Run!」を押してください。（コードに改行や余分な文字が入るとエラーになるので注意！）

お祝いメッセージ

コード以外にも、多数のお祝いメッセージをいただきました。本当にありがとうございます。

なんと CodeIQ 公式さんまで！

constant.pm の件は反省しておりますですｗ

年齢

（説明：「今日俺の誕生日だ」ツイートは、素数に関する問題を出題中の『第6回デスマコロシアム』のQAを受けてのものなので、「年齢が素数だったら面白い」わけです。しかし実際には素数ではなく3の倍数なので、「Fizz歳」と返しました。具体的な年齢・年代を一切明かさずに素数でないことを端的に示すのみならず、ちょうど前回の『第5回デスマコロシアム』が FizzBuzz 問題だったのでタイムリーな表現になっています。）

2D マップ上の最短パスを求める新しいアルゴリズム S* の提案

はじめに

ゲームのキャラクタを自動で移動させる場合などに、 2D マップ上の２点間の最短パスを求めることが行われます。

典型的なやり方としては、マップを格子状のマス目に分割し、マス目ごとに通れるか通れないかを決定しておき、キャラクタの現在地である開始点と、目的地となる終了点との２点間のパス（経路）を A* アルゴリズムで求める、という方法が一般的かと思います。

しかし、マップをマス目に分割するのは、本当に必要なことなのでしょうか？ もっと直接的に、幾何学的な最短パスを A* で求めればいいのではないでしょうか？ ちょっと実装して実験してみました。

デモ

未署名の Java アップレットですすんません。 Java の設定でセキュリティを下げて実行してくださいすんません。

 

線の色は、パスの長さを表しています。パスが切り替わったときにも線の色が不連続には変化していないことから、等しい長さのパスの間で切り替わっていることが確認できます。

２点を変化させながらリアルタイムに探索していますが、 CPU をほとんど使っていないことがわかります。

S* アルゴリズム

上のデモで実装したアルゴリズムを、とりあえず「S*」と呼ぶことにします。「 Saito の A*」 の略です。単純なアルゴリズムなので、考え付いたのは私が最初というわけでもないでしょうし、既にちゃんとした名前があるようにも思いますが、知りません。

アルゴリズムの内容は、上のデモから一目瞭然なのですが、次のような感じです。

準備

  1. マップ上の障害物を、多角形で近似する。（上のデモでは、障害物の形状自体を三角形にしています。）
  2. 多角形の頂点同士を結ぶ線分のうち、多角形の内部を通過しないもののリスト（頂点間リスト）を作成する。

探索

  1. 頂点間リストに、開始点と終了点を一時的に追加する。
  2. 開始点から終了点に向かって、頂点間リストに A* アルゴリズムを適用する。このとき、 A* のヒューリスティック関数には、終了点までのユークリッド距離を用いる。

以上です。とてもシンプルですね！

マス目 A* との比較

従来の探索方法を、ここでは「マス目 A* 」と呼ぶことにします。

S* の利点

  • マス目に分割する必要がない。（マス目 A* では、マス目の分割のパラメータ（特にマス目の大きさ）で探索結果が変化しうるが、 S* はそのようなパラメータの影響がない。）
  • 常にユークリッド距離での最短パスが求まる。（マス目 A* では、通過するマス目の数が最小になるようなパスが求まるが、必ずしもユークリッド距離で最短とはならない…ですよね？）
  • パスが最初から折れ線で求まるので、折れ線化するための後工程が不要。（マス目 A* では、折れ線化が必要。）

S* の欠点

  • 見晴らしの良い広大なマップでは、頂点間リストを素朴に作ると、遠くの多角形同士の頂点間で無駄に多い線分が頂点間リストに登録されるので、工夫が必要。
  • 移動する障害物が多数あるような場合には不向きかも。
  • ていうか、実際のゲームなどのアプリケーションで試したことがないので、本当に実用に耐えうるのか疑問。誰かやってみてください！

S* アルゴリズムの利用について

S* アルゴリズムに関しては、私は、何らの主張もしません。しかし、他者が特許を取っている（またはこれから取る）可能性などについては関知しませんので、その点は自己責任でお願いします。

デモアプレットについては、著作権を主張します。 All rights reserved です。ていうか、突貫で作ったウンコードなので恥ずかしいから解析するな、ってことです。