「あべこべのダンジョン」 私の面白コードの解説
はじめに
CodeIQで、「あべこべのダンジョン」という問題が出題されました。
問題の内容を大雑把に言うと、「8桁の数 n が与えられたときに、各桁の数字（1~9）を「10-元の数字」に変換した数を作るJavaScriptのコードを書く」、というものです。
これだと何のこっちゃなので、問題と解答例について、出題者の柳井政和様による解説記事をご覧ください。（まあ、このブログを読んでいる人は、解説記事を既に読んでいるでしょうね！）
解説記事 → https://codeiq.jp/magazine/2014/05/9266/
問題はLV1, LV2, LV3の3問があり、それぞれ文字数制限と使用禁止文字列が定められています。また、コードは穴埋め形式になっていて、そこに適合させて全体で正しく動くような穴埋め部分のコードが、解答となります。つまり、元の8桁の数が変数 n で与えられたときに変換後の値を表すような式が正解となります。
さらに、この問題（に限らずダンジョンシリーズ）の面白いところは、それぞれのレベルで定められている文字数制限と使用禁止文字列を満たしていれば正解となり、バッジが付与されますが、実際には場外（TwitterとかCodeIQ MAGAZINEとか）で出題者様主導で解答コードの短さが競われているのです！ いわゆるコードゴルフです。このことは問題文には一切書かれていなくて、バッジほしさに適当に解答を送ると、知らずにコードゴルフに引きずり込まれるという、恐ろしい罠が仕掛けられているのです！
さて、解説記事を読んで気付いたのですが、なんと、私（tails）は、
- レベル1の最短コード
- レベル2の最短コード
- レベル3の最短コード
- 面白コード
の4部門（？）の全てに名を連ねてしまいました！（しかもレベル1とレベル2は最速だったようです。） これは私自身、全く予想していませんでしたし、狙ってさえいませんでしたから、びっくりです。
というわけで、前置きが長くなりましたが、今回は最短コードは置いといて、面白コードに採用された私のコードについて解説してみます。そのコードとは、レベル3の解答として提出した
n+8747258937^268435455
というものです。（最短を狙って提出したのですが、面白コードになってしまいました！）
解き方の基本方針
解説記事にも書かれているように、求めるコードは、要するに
111111110-n
です。
ところが、レベル3では「-」「~」「0」「1」がいずれも使用禁止のため、これらを使わずに等価な式になるように書き換えなければなりません。
「－」（マイナス）を外そう
「0」と「1」は後回しにして、まずは -n の部分の - を外す方法を考えてみます。
よく知られているように、 ~n が -(n+1) と等価なので、これを用いて
111111111+~n
と変形できます。さらに、「~」を外すために、
111111111+(0xffffffff^n)
と変形します。このあたりのことも解説記事に書かれていますね。（実際のコードに十六進表現を用いる必要はありませんが、このほうが解りやすい…ですよね？）
「（ ）」（括弧）を外そう
上の式を見ると、 n に対して、最初に定数値との「^」（排他的論理和）を計算し、その後で別の定数値との「+」（和）を計算しています。JavaScriptの演算子は、「+」のほうが「^」よりも優先順位が高いため、一見すると括弧は外せそうにありません。
しかし、よく考えてみましょう。上の式の結果を仮に r とします。つまり、
r = 111111111+(0xffffffff^n)
です。このとき、 r は n の各桁の数を変換（1～9 → 9～1）したものです。ということは、見方を変えれば、 n は r の各桁の数を変換したものということです！ すなわち、
n = 111111111+(0xffffffff^r)
ということですね。（このように、2回で元に戻る変換を「対合」というらしいです。）これを改めて r について解けば、
n = 111111111+(0xffffffff^r)
↓n-111111111 = 0xffffffff^r
↓r = n-111111111^0xffffffff
となり、見事に括弧を外すことに成功しました！
しかし、最初に折角外した「-」が復活してしまっています。どうしたものでしょうか。
心配いりません。今は変数ではなく定数のほうに「-」が付いている点で、最初の「-」とは異なっています。ある数から 111111111 を引くということは、当たり前のことですが、 -111111111 を加えるということです。ということは、…簡単ですね。どうせ後で32ビットの論理演算をするのですから、 -111111111 とビット表現が等価な正の数、すなわち -111111111 に2の32乗を加えた数で代用すればいいのです。具体的に式全体を十進数で書き下してみると、
n+4183856185^4294967295
となりました。
ビット幅を考えよう
いよいよ仕上げです。今まで無視していましたが、「0」と「1」も使用禁止です。上の式では「1」が2回使われているので、何とかしなければなりません。どうしたものでしょうか（2度目）。
これを解決するために、ビット演算について、もう少し掘り下げて考えてみます。
式をもう一度見てみましょう。
n+4183856185^4294967295
n は、8桁の比較的小さな数です。これに32ビット上限に近い 41... を加え、その後全ビットを反転させています。違和感を感じませんでしょうか？
最上位ビットを考えてみましょう。 n の最上位ビットは、当然0です。これに 41... を加えることで、最上位ビットは1になります。その後、 42... との排他的論理和を取る（つまり全ビットを反転する）ことで、最上位ビットを再び0に戻しています。これは必要な操作でしょうか？いや、明らかに無駄です。
もちろん、最上位ビットだけの話ではありません。 n は8桁の数であり、ビット数で言えば27ビットです。そして、式の結果も n と同じ範囲なので27ビットです。それより上のビットを、一旦1にしてから反転したりする必要はないのです。
ということで、上の式は
n+何か正の数^0x07ffffff
で充分ということになります。「何か正の数」の値は、 41...&0x07ffffff です。具体的に十進数で書き下してみると、
n+23106617^134217727
となります。
「0」と「1」は外れるどころかむしろ増えてしまいましたが、数値に選択の余地があることがわかりました。しかも、副作用として、元の式より短くなりました。この選択の余地を利用して、使用禁止の「0」と「1」を外すことを考えてみます。
「0」と「1」を外そう
最初に得た n+4183856185^4294967295 という式では、2つの定数の第27～31ビットは、無駄に全て1でした。これらのビットを全て0にして n+23106617^134217727 という式を得ましたが、これらのビットは、要するに、何でもいいのです。これらのビットは5ビットなので、32パターンを取ることができます。32パターンに対応する式を列挙してみましょう。果たして、「0」も「1」も含まない式があるでしょうか？
n+23106617^134217727
n+157324345^268435455
n+291542073^402653183
n+425759801^536870911
n+559977529^671088639
n+694195257^805306367
n+828412985^939524095
n+962630713^1073741823
n+1096848441^1207959551
n+1231066169^1342177279
n+1365283897^1476395007
n+1499501625^1610612735
n+1633719353^1744830463
n+1767937081^1879048191
n+1902154809^2013265919
n+2036372537^2147483647
n+2170590265^2281701375
n+2304807993^2415919103
n+2439025721^2550136831
n+2573243449^2684354559
n+2707461177^2818572287
n+2841678905^2952790015
n+2975896633^3087007743
n+3110114361^3221225471
n+3244332089^3355443199
n+3378549817^3489660927
n+3512767545^3623878655
n+3646985273^3758096383
n+3781203001^3892314111
n+3915420729^4026531839
n+4049638457^4160749567
n+4183856185^4294967295
ありました！1つだけ、「0」も「1」も含まない式が！
めでたし、めでたし。
おわりに ～ さらに縮めてみよう
上で求めたコードを、私は実際に解答として提出しました。ところが、その後、ここから1文字縮めることに成功したコードを改めて提出し、それが面白コードとして採用されました。2つのコードを比べてみましょう。
n+2573243449^2684354559 // 上で求めたコード（23文字）n+8747258937^268435455 // 面白コード（22文字）
下のコードがどのようなものであるかは、ここまでの解説の延長線上にありますので、ちょっと考えていただければわかると思います。
