JavaScript
フィボナッチ数列
難読化

【JavaScript】10種類の文字だけでフィボナッチ数を計算する関数を書いてみた

初めまして。
まずは本題。
n番目のフィボナッチ数を計算する関数です。

Fibonacci.js
const getFibonacci = (_=>((_=[__=>([_=>_,()=>(_[!-[]-(-!-[])][__]=_[-[]](__-!-[])-(-_[-[]](__-!-[]-!-[])))][-(-(_[!-[]-(-!-[])][__]===[][[]]))](),_[!-[]-(-!-[])][__]),__=>((_[!-[]-(-!-[])]=[-[],-(-!-[])]),_[-[]](__))]),_[-(-!-[])]))();

関数の記述には(_,)=>!-[]の10種類の文字しか使っていません。
どうしてもソース全文でそれらだけにしたければ、
スペース詰めて関数名変えて宣言とセミコロン省いて
_=(_=> 〜 )()みたいにすればいいと思います。

getFibonacci(50)とか計算すると、
そこそこの速さで12586269025と出てくるので合ってそうです
(動作検証はChromeでしかしてませんが)。

何これ?

そのままだと中身見放題のJavaScriptの難読化の方法を考えていて、
「もっと文字の種類を減らせるのでは?」と思ったので、
手動でも難読化できそうなフィボナッチ数列でやってみました。

よくわからない解説

このままだと難読化したソースを紹介してるだけになってしまうので、
解説をつけてみます。

1. とりあえず改行とインデント

上のソースだと横に長すぎてふざけてるのかってレベルなので
改行とインデントを入れてみます。

Fibonacci1.js
const getFibonacci = (_=>(
  (_=
    [
      __=>(
        [
          _=>_,
          ()=>(_[!-[]-(-!-[])][__]=_[-[]](__-!-[])-(-_[-[]](__-!-[]-!-[])))
        ][-(-(_[!-[]-(-!-[])][__]===[][[]]))](),
        _[!-[]-(-!-[])][__]
      ),
      __=>(
        (_[!-[]-(-!-[])]=[-[],-(-!-[])]),_[-[]](__)
      )
    ]
  ),
  _[-(-!-[])]
))();

はい、馬鹿にしてんのかって感じですね。

2. みんな大好き+[]+!+[]

JavaScriptは特定の演算をした時に型変換されるので
+[]+00
+!+[]+!0+true+11
のように+![]だけで0や1を表現できます。

巷でよく見かける(?)のは上記の+を使った書き方ですが、
-[]-00
-(-!-[])-(-!0)-(-true)-(-1)1
という感じに-を用いても同じことができます。

これを踏まえてさっきのソースを見ると、
-[]-(-!-[])と言ったパターンがたくさんあるので
0と1に置き換えてやると、次のようになります。

Fibonacci2.js
const getFibonacci = (_=>(
  (_=
    [
      __=>(
        [
          _=>_,
          ()=>(_[2][__]=_[0](__-1)-(-_[0](__-2)))
        ][-(-(_[2][__]===undefined))](),
        _[2][__]
      ),
      __=>(
        (_[2]=[0,1]),_[0](__)
      )
    ]
  ),
  _[1]
))();

2になってるところはtrue+true等の結果です。
他にも[][[]]undefinedになっていますが、
これは空の行列[]''というプロパティを見に行って
そんなのは定義されていないのでundefined値が返ってきます。

文字や数字が現れてきましたが、
まだまだ読みやすいコードとは言えませんね。

3. そもそも変数名が悪い

変な記号がかなり減ったところで、
_とか__なんていうふざけた名前の変数をなんとかしましょう。
あとthisなんて影も形もないので、
アロー関数も普通のfunctionに置き換えて問題ないでしょう。

Fibonacci3-0.js
const getFibonacci = (function(a){
  return (
  (a=
    [
      function(b){
        return (
        [
          function(x){return x},
          function(){
            return(a[2][b]=a[0](b-1)-(-a[0](b-2)))
          }
        ][-(-(a[2][b]===undefined))](),
        a[2][b]
      )},
      function(b){
        return (
          (a[2]=[0,1]),a[0](b)
        )
      }
    ]
  ),
  a[1]
)
})();

少しインデントを変えています。
やっとJavaScriptっぽくなってきました。
b-1b-2が近くにあるあたりに少しフィボナッチ感も漂い出しました。

全体で5つの関数がありますが、そのうち3つの関数で、
returnのあとに,があって、何が返り値なのかわかりづらいです。
Minifier等を使うとよく見かける表現ですが、
読みづらいのでついでに変えておきましょう。

Fibonacci3-1.js
const getFibonacci = (function(a){
  a=[
    function(b){
      [
        function(x){return x},
        function(){
          return(a[2][b]=a[0](b-1)-(-a[0](b-2)))
        }
      ][-(-(a[2][b]===undefined))]();
      return a[2][b];
    },
    function(b){
      a[2]=[0,1];
      return a[0](b);
    }
  ];
  return a[1];
})();

4. aの抹殺

ここまでくると、この関数がどういう構造なのか
わかりやすくなってきたんじゃないでしょうか。

中に2つの関数があって、それがaに配列として代入されています。
このaですが、一番外側の無名関数の引数に見えて、
下を見ると関数の実行時には何も代入されておらず、
関数の一番初めに配列が代入されています。
グローバルスコープを汚さないための匠の暖かい心遣いですね。

とはいえ、2つの関数の定義を外に出してやれば
このaなんて必要なさそうな気がします。
a[0]a[1]をそれぞれf0f1に置き換えてみましょう。

……と、その前に、
aは2つの要素しかない配列のはずが、よく見るとa[2]なんて奴がいます。
こいつは関数じゃなさそうなのでa2と置き換えます。

Fibonacci4.js
const getFibonacci = (function(){
    let f0 = function(b){
        [
            function(x){return x},
            function(){
                return(a2[b]=f0(b-1)-(-f0(b-2)))
            }
        ][-(-(a2[b]===undefined))]();
        return a2[b];
    };
    let f1 = function(b){
        a2=[0,1];
        return f0(b);
    };
    let a2;
    return f1;
})();

しれっとインデントをスペース4つに変えました。

見事にaの消去に成功しました。
f0f1は再代入されていないようなので、
あとで変数宣言をconstに変えておきます。

5. 謎の空間

ただ、こうしてコードとして整ってくると、
f0の中に謎の空間があることに気づきます。

謎の空間-0
[
    function(x){return x},
    function(){
        return(a2[b]=f0(b-1)-(-f0(b-2)))
    }
][-(-(a2[b]===undefined))]();

この部分ですね。

-が重なってるところや、余計な括弧を省いたりしても、

謎の空間-1
[
    function(x){return x},
    function(){
        return a2[b]=f0(b-1)+f0(b-2);
    }
][+(a2[b]===undefined)]();

という風にしかならず、直感的に理解できるとは言い難いでしょう。

実はこの部分がこの関数の肝であり、
10種類の文字だけで記述するのに不可欠な要素なのです。

せっかくなので、要素を一つひとつ見ていきましょう。

5.1. 配列の中身

謎の空間の配列-0
[
    function(x){return x},
    function(){
        return a2[b]=f0(b-1)+f0(b-2);
    }
]

2つの関数が収まっていますね。
1つ目は代入された値をそのまま返す関数、
2つ目はフィボナッチっぽい関数です。

実はこれらの関数は、返り値がどこかに代入されることはないので、
returnは不要だったりします。
そうなると1つ目の関数は何もしない関数になってしまい、

謎の空間の配列-1
[
    function(){},
    function(){
        a2[b]=f0(b-1)+f0(b-2);
    }
]

というすっきりした感じになります。

5.2. 配列のアドレス

array[i]iの部分をなんて読んでいいかわからないので
とりあえずアドレスと読んでいます。

謎の空間でいうところの

+(a2[b]===undefined)

の部分です。

ここではa2[b]undefinedと比較して、
その結果に+をつけています。
+!+[]+[]と同じように、
頭に+をつけて真偽値を10に変換しているんですね。

したがって、a2[b]の値がundefinedであれば、
+(a2[b]===undefined)+(true)1となり、
そうでなければ、
+(a2[b]===undefined)+(false)0となるわけなのです。

5.3. 後ろの()

JavaScriptでは昔から、

周りにfunction=>がいない()を見たら
何かの関数を実行していると思え!

とは言われてはいないと思いますが、
この場合はまさにそれですね。

配列の中の2つの関数から、
a2[b]の値によって片方を選んで、
そいつを実行しているわけです。

5.4. 謎の空間の正体

謎の空間では、
a2[b]の値がundefinedなら
配列の1番目の関数function(){a2[b]=f0(b-1)+f0(b-2);}を実行し
a2[b]の値がundefinedでないなら
配列の0番目の関数function(){}を実行する(つまり何もしない)わけです。

とっくにお気づきかもしれませんが、
これは条件分岐、つまりはif文です。
謎の空間を冗長に書き直すと、

謎の空間の正体-0
if(a2[b]===undefined){
    (function(){
        a2[b]=f0(b-1)+f0(b-2);
    })();
}else{
    (function(){})();
}

となり、余計な部分を省くと、

謎の空間の正体-1
if(a2[b]===undefined){
    a2[b]=f0(b-1)+f0(b-2);
}

という何の変哲もないif文となってしまいました。

通常、if文を書こうと思うとifを使うか三項演算子a?b:cを使うわけです。
どちらを選んでも、(_,)=>!-[]以外の文字を2つ使う必要があります。
また、Minifierを使うとしばしば見られる表現ですが、&&を使って、

a2[b]===undefined&&(a2[b]=f0(b-1)+f0(b-2))

のように書くこともできますが、それでも&が余計に必要です。

実は最初にこのコードを書いた時には&さんがいました。
1箇所だけにしかいないこいつを何とか排除したくて、
配列を使った方法を思いつき、
謎の空間が生まれ、
そのまま上がったテンションでこんな文章を書いているというわけなのでした。

6. 最終形態

さて、ただのif文ごときに手間取ってしまいましたが、
おかげでただのJavaScriptのソースコードに見えるところまできました。

Fibonacci6-0.js
const getFibonacci = (function(){
    const f0 = function(b){
        if(a2[b]===undefined){
            a2[b]=f0(b-1)+f0(b-2);
        }
        return a2[b];
    };
    const f1 = function(b){
        a2=[0,1];
        return f0(b);
    };
    let a2;
    return f1;
})();

あと残った謎はa2くらいでしょうか。

関数の流れを追ってみると、getFibonacci(n)を実行すると、
f1の初めで、a2に配列[0,1]が代入されています。
そしてf0が呼ばれ、
a2[b]の値がundefinedならf0(b-1)+f0(b-2)を代入し、
最終的にa2[b]が返ってきます。

f0(b-1)+f0(b-2)の部分はフィボナッチ数の定義そのままです。
また、f0(0)a2=[0,1]の0番目の要素なので0、
f0(1)a2=[0,1]の1番目の要素なので1が返ってくるので、
計算すると、0,1,1,2,3,5,8,13,...という
フィボナッチ数列になります。

6.1. メモ化

ここで、a2[b]に計算結果を代入しているのは、
同じnに対してf0(n)を何度も計算しないで済むように、
1度計算した値を保存しておくメモ化というテクニックです。
f1でわざわざ初期化してるのは、計算時間を測定したかったんですかね。

フィボナッチ数列のように再帰的に計算する必要がある場合は、
劇的に速度が上がるみたいです。
一番初めに「そこそこの速さで」と書いたのはそれが理由ですね。
メモ化について詳しく書く気はないので、気になる方は調べてみてください。

6.2. 元の状態と比較

さて、全ての謎が解けたところで、
冗長な部分を消したり体裁を整えたりすると、次のようになります。

Fibonacci6-1.js
const getFibonacci = (function(){
    let memo;
    const f = function(n){
        if(memo[n]===undefined){
            memo[n] = f(n-1) + f(n-2);
        }
        return memo[n];
    };
    return function(n){
        memo = [0,1];
        return f(n);
    };
})();

うーん、ごく普通のフィボナッチ数を計算する関数ですね
undefined周りが少し気になるかもしれませんが)。
最初の頃と比較してみましょう。

Fibonacci1.js
const getFibonacci = (_=>(
  (_=
    [
      __=>(
        [
          _=>_,
          ()=>(_[!-[]-(-!-[])][__]=_[-[]](__-!-[])-(-_[-[]](__-!-[]-!-[])))
        ][-(-(_[!-[]-(-!-[])][__]===[][[]]))](),
        _[!-[]-(-!-[])][__]
      ),
      __=>(
        (_[!-[]-(-!-[])]=[-[],-(-!-[])]),_[-[]](__)
      )
    ]
  ),
  _[-(-!-[])]
))();

インデントの形は似ているような気がしないでもないですが、
こうして見るとまるで別物ですね。

最後に

今回、フィボナッチ数を計算する関数を
(_,)=>!-[]だけを使って書いてみましたが、
どんな関数でも書けるわけではないと思います。

ただ、いくつか記号を追加して、
window等のルートオブジェクトとnew'SCgohm'なんて文字列を用意すれば、
大抵のコードは今回のように難読化できる気がします。

手動でやると頭がおかしくなりかねないので、
自動で難読化するプログラムを書いてみてもいいんじゃないでしょうか。

特に使えるような内容ではありませんでしたが、
何かのヒントになれば幸いです。

おまけ

(_,)=>!-[]
「どうして10種類の文字列が(_,)=>!-[]なんていう変な順番なんだ」と
気になった方がいるかもしれません。
大した理由ではありませんが、
JavaScriptとして実行してエラーにならない並びだったからです。
文法的に不正でないかは知りません。
他の並びはあと1種類しか思いつきませんでした。