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

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

テンプレ

この問題(に限らずダンジョンシリーズ)の面白いところは、定められた文字数制限と使用禁止文字列を満たす 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 の禁止文字列に加えて新たに ( ) { } が禁止されています。私のコードの動作については、大変ありがたいことに、解説記事の中で出題者様が確認コードを書いて下さっています。私自身もはっきりわかって書いていたわけではないので、なるほどこうなっていたのか!というのが正直な感想ですw

「無双」と評された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" を付加しています。少し具体的に説明します。

(1)先頭の "0" の判定

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

'.'+i<.5

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

(2)数値計算

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

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 組も使っています。前述の(2)の計算式

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文字も縮めることができました。

おわりに

楽しかったです。