AtCoderに登録したら解くべき精選過去問10を「JSFuck」で解いてみた

# まえがき
久しぶりにWikipediaの[難解プログラミング言語](https://ja.wikipedia.org/wiki/%E9%9B%A3%E8%A7%A3%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E8%A8%80%E8%AA%9E)の記事を見たら言語例にJSFuckという言語が追加されていました[^1]．
やればできそうなのでこの言語を使って精選10問[^7]を解いてみることにしました．

[^1]: 変更履歴によれば2019/05/23のことである．

[^7]: @drken さんによる記事 [AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～](https://qiita.com/drken/items/fd4e5e3630d0f5859067) に提示された初心者向け問題を集めた10問．言語を触って遊んでみるのに丁度いい難易度の問題が揃っています．現在は[AtCoder Beginners Selection](https://atcoder.jp/contests/abs/tasks)として問題セットがまとめられています.

# What's JSFuck?
JSFuckとは

> JavaScriptのような文法の言語。構成文字は`[`,`]`, `(`、`)`、`!`と`+`のみ
> (Wikipedia -難解プログラミング言語)

とのこと．

例えば

```
alert(1)
```
というプログラムは

```
[][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]][([][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]]+[])[!+[]+!+[]+!+[]]+(!![]+[][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]])[+!+[]+[+[]]]+([][[]]+[])[+!+[]]+(![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[+!+[]]+([][[]]+[])[+[]]+([][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]])[+!+[]+[+[]]]+(!![]+[])[+!+[]]]((![]+[])[+!+[]]+(![]+[])[!+[]+!+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]+(!![]+[])[+[]]+(![]+[][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]])[!+[]+!+[]+[+[]]]+[+!+[]]+(!![]+[][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]])[!+[]+!+[]+[+[]]])()
```
と書けます．

JavaScriptでなるべく少ない記号で書き表すことを追求した結果生まれた言語で，実はJavaScriptのプログラムとして実行できます．（Wikipediaの説明は語弊があってJavaScriptのような文法，というよりはJavaScriptの文法を制限したサブセットと言ったほうがわかりやすいのではないでしょうか）

JSのサブセットがどうやったらこんなBrainfuckじみたコードを生むのかというと，JSの変態的な暗黙の型変換と文字列を評価して実行する機能が鍵を握っています．すなわち

+ `hoge.fuga`は`hoge["fuga"]`で呼び出せる
+ `![]`=`false`
+ `+true`=`1`
+ `false+[]`=`"false"`
+ `eval("hoge")` で `hoge` の内容を実行できる

などを組み合わせ，
`1`=`+!![]`
`"a"`=`"false"[1]`=`(![]+[])[+!![]]`
などのようにしていろいろなリテラルを得ることができます．
さらに，`eval`は`[]["filter"]["constructor"]( hoge )()`で呼び出せるため，`"filter"`,`"constructor"`と`hoge`を上の方法で文字列として表せば，任意プログラム実行が可能になるというわけです．つまり，
`[][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]][([][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]]+[])[!+[]+!+[]+!+[]]+(!![]+[][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]])[+!+[]+[+[]]]+([][[]]+[])[+!+[]]+(![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[+!+[]]+([][[]]+[])[+[]]+([][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]])[+!+[]+[+[]]]+(!![]+[])[+!+[]]]( hoge )()`
ですね．[^2]

[^2]: "filter"は`(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]`，"constructor"は`([][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]]+[])[!+[]+!+[]+!+[]]+(!![]+[][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]])[+!+[]+[+[]]]+([][[]]+[])[+!+[]]+(![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[+!+[]]+([][[]]+[])[+[]]+([][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]])[+!+[]+[+[]]]+(!![]+[])[+!+[]]`となる．

その他詳しくはWikipediaを御覧ください．https://ja.wikipedia.org/wiki/JSFuck

また，本記事ではWikipediaと [jsfuck.com](http://www.jsfuck.com/) の記述を参考にしましたが，「`[`,`]`,`(`,`)`,`!`,`+`」の6文字以外にも「`[`,`]`,`(`,`)`,`=`,`+`」のように任意プログラムの実行が可能な記号セットを取ることが可能であることが知られています．[^8]
任意プログラムのコーディングが可能な記号セットは6文字が最小であるようです．[^10]
参考：https://github.com/aemkei/jsfuck ，[本格JavaScript記号プログラミング(1) 6種類の記号だけでJavaScriptを書こう](https://qiita.com/Tatamo/items/24099958b90cbed61d67)

[^8]: Qiita上で確認できる研究ではこちらのほうが優勢のようですが，なぜWikipediaには前者が載る事になったのかは不明です．

[^10]: `|>`演算子が導入されれば夢の5文字「`[`,`]`,`+`,`|`,`>`」が可能になるそう．

さて，JavaScriptとして実行できる，ということはAtCoderで提出ができるということ．というわけで精選10問を解いていきましょう．

# 一般解
結論から言うと以下のようなコードを書いて一字ずつ文字列に変換してevalすれば(ほぼ)どんなコードでも実行できます．


```js:echoのコード
function main(input){
    console.log(input);
}
var input = '';
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', c=>{input += c});
process.stdin.on('end', ()=>main(input))
```
入力は`input`に配列として格納されています．
Node.jsで標準入出力を扱うテンプレとしては

```js

var input = require('fs').readFileSync('/dev/stdin', 'utf8');
```

が知られています[^4]が，これを使わないのは`requre`がセキュリティ権限の問題で`eval`で実行できないため[^3]IOを監視して順次配列に格納するという方法を取っています[^5]．

[^4]: 参考：https://qiita.com/ytanto/items/caf7bf0ba287da81b20f

[^3]: 早速「(ほぼ)どんなコードでも実行できる」の反例が出てしまいました．

[^5]: 参考：https://qiita.com/alucky0707/items/46f8a3e0c523d3bd4034

ソースコードを一文字ずつJSFuck化するのは大変なので機械にまかせてしまいましょう．
こちらのサイト http://www.jsfuck.com/ の入力フォームにソースコードを入力すれば(適宜`;`をつけてワンライナー化する必要があります．)JSFuckで文字列として解釈できるソースコードに変換してくれます．
「Eval Source」にチェックを入れれば上記の`eval`で囲んだものになり，元のコードと同じ動作をするようになります．

この記事の内容としてはこれでほぼ終わりです．出入力だけ注意してJavaScriptで解答し，変換すればOKです．
正直，JSFuckに変換したコードは全部同じにしか見えない(難読化の手法として上げられるだけのことはある)ので変換前のコードだけ提示します．

# 0. PracticeA - Welcome to AtCoder
解答はこんな感じです．

```js:
var i='',f=process.stdin;
f.resume();
f.setEncoding('utf8');
f.on('data',c=>{i+=c});
f.on('end',()=>{
  var t=i.split('\n'),a=+t.shift(),r=t.shift().split(' '),u=t.shift(),n=+r.shift(),l=+r.shift();
  console.log(a+n+l+' '+u)
})
```

やたらと変な変数名をつけているのはコード量削減のためです．
JSFuckではオブジェクトの文字列表記などから文字を取得するなどいろいろと遠回りをしているのであまり長いコードになるとJavaScriptとして解釈するだけで結構実行時間を取られてしまいます．
"f", "t", "a"あたりの文字は13, 14, 15Byteで表せますが，"]"などは6591Byte必要です(このあたりは文字コードを指定して取得しているらしい)．
"v"あたりも1768Byteとそこそこ長いため`var`よりも`const`のほうが短くなるなど，単なるコードゴルフとは違った戦略が求められそうです．

JSFuckに変換して提出すると，コード長は198851 Byte，実行時間は343 msとなりました．(変換前に改行やインデントは削除しています．)
https://atcoder.jp/contests/abs/submissions/8383312
コード解釈にかなり時間がかかっていそうですね．

# 1. ABC086A - Product

```js

var i='',f=process.stdin;
f.resume();
f.setEncoding('utf8');
f.on('data',c=>{i+=c});
f.on('end',()=>{
  const t=i.split(' '),a=+t.shift(),r=+t.shift();
  console.log((a*r%2==0)?'Even':'Odd')
})
```
↓
https://atcoder.jp/contests/abs/submissions/8394727
コード長 205291 Byte，実行時間 362 ms

# 2. ABC081A - Placing Marbles

```js
var i='',f=process.stdin;
f.resume();
f.setEncoding('utf8');
f.on('data',c=>{i+=c});
f.on('end',()=>{
  var a=i.split(''),r=+a.shift();
  r+=+a.shift();
  r+=+a.shift();
  console.log(r)
})
```
↓
https://atcoder.jp/contests/abs/submissions/8394847
コード長 171766 Byte，実行時間 313 ms

# 3. ABC081B - Shift only

```js
var i='',f=process.stdin;
f.resume();
f.setEncoding('utf8');
f.on('data',c=>{i+=c});
f.on('end',()=>{
  var f=i.split('\n'),a=f[1].split(' '),r=0;
  while(1)
    if(a.every(t=>+t%2==0)){a=a.map(t=>+t/2);r+=1}
    else{break}
  console.log(r)
})
```
↓
https://atcoder.jp/contests/abs/submissions/8400487
コード長 223468 Byte，実行時間 375 ms

# 4. ABC087B - Coins

```js
var i='',f=process.stdin;
f.resume();
f.setEncoding('utf8');
f.on('data',c=>{i+=c});
f.on('end',()=>{
  var t=i.split('\n'),a=+t.shift(),b=+t.shift(),c=+t.shift(),
    x=+t.shift(),r=0;
  for(var s=0;s<=a;s++)
    for(var t=0;t<=b;t++)
      for(var u=0;u<=c;u++)
        if(500*s+100*t+50*u==x)r+=1
  console.log(r)
})
```
↓
https://atcoder.jp/contests/abs/submissions/8400694
コード長 287213 Byte，実行時間 473 ms

変数が増えてきてコード長を切り詰めるのがつらくなってきました．

# 5. ABC083B - Some Sums

```js
var i='',f=process.stdin;
f.resume();
f.setEncoding('utf8');
f.on('data',c=>{i+=c});
f.on('end',()=>{
  var t=i.split(' '),n=+t.shift(),a=+t.shift(),b=+t.shift(),r=0,s,u;
  for(s=0;s<=n;s++){
    u=(s+[]).split('').reduce((x,y)=>x+ +y,0);
    if(a<=u&&u<=b)r+=s
  }
  console.log(r)
})
```

https://atcoder.jp/contests/abs/submissions/8400819
コード長 248794 Byte，実行時間 436 ms

```js
u=(s+[]).split('').reduce((x,y)=>x+ +y,0);
```
のところは
数値→文字列に変換→配列に変換→各文字を数値に変換しながら総和を取る
という操作になっています．
大変読みにくいですね，実務でこんなコードを書いた日には殴られそうです．

# 6. ABC088B - Card Game for Two

```js
var i='',f=process.stdin;
f.resume();
f.setEncoding('utf8');
f.on('data',c=>{i+=c});
f.on('end',()=>{
  var t=i.split('\n'),n=+t[0],
    a=t[1].split(' ').map(x=>+x),
    sa=0,sb=0;
  a.sort((x,y)=>x<y?1:-1).forEach((x,k)=>(k%2==0)?sa+=x:sb+=x);
  console.log(sa-sb)
})
```
↓
https://atcoder.jp/contests/abs/submissions/8404271
コード長 250855 Byte，実行時間 417 ms

# 7. ABC085B - Kagami Mochi

```js
var i='',f=process.stdin;
f.resume();
f.setEncoding('utf8');
f.on('data',c=>{i+=c});
f.on('end',()=>{
  var t=i.split('\n'),n=+t.shift();
  console.log((new Set(t)).size-1)
})
```
↓
https://atcoder.jp/contests/abs/submissions/8404356
コード長 161183 Byte，実行時間 289 ms

# 8. ABC085C - Otoshidama

```js
var i='',f=process.stdin;
f.resume();
f.setEncoding('utf8');
f.on('data',c=>{i+=c});
f.on('end',()=>{
  var a=i.split(' '),n=+a.shift(),y=a.shift(),r='-1 -1 -1';
  for(var k=0;k<=n;k++){for(var l=0;k+l<=n;l++)if(k*10000+l*5000+(n-k-l)*1000==y){r=`${k} ${l} ${n-k-l}`;break}}
  console.log(r)
})
```
↓
https://atcoder.jp/contests/abs/submissions/8383748
コード長 326046 Byte，実行時間 810 ms

# 9. ABC049C - 白昼夢 / Daydream

初め，以下のコードを提出しようと試みました．

```js
i='',f=process.stdin,
    l=s=>s.length
    c=(s,t)=>l(s)>=l(t)&&s.substring(0,l(t))==t,
    r=(s,b)=>s.substring(b);
f.resume();f.setEncoding('utf8');f.on('data',t=>{i+=t});
f.on('end',()=>{
  i=i.substring(0,l(i)-1).split('').reverse().join('');
  while(i){
    if(c(i,'remaerd')){i=r(i,7)}
    else if(c(i,'maerd')){i=r(i,5)}
    else if(c(i,'resare')){i=r(i,6)}
    else if(c(i,'esare')){i=r(i,5)}
    else{console.log('NO');return}}
  console.log('YES')
})
```

これをJSFuckに変換すると365905 Byte になりますが，413 Request Too Largeで弾かれてしまいました．コード長制限は512KiBですし，以前 375197 Byte で提出できた例もあったので問題ないはずですが何故でしょう……

ちょっとここからコード長を詰めるのは辛かったので正規表現を使った解法で通すことにしました[^6]．

[^6]: 参考：https://qiita.com/kotatsugame/items/2619398606b30aaf097b#%E7%AC%AC9%E5%95%8Fabc049c---%E7%99%BD%E6%98%BC%E5%A4%A2--daydream

```js
var i='',f=process.stdin,r=(g,t)=>i.replace(g,t);
f.resume();f.setEncoding('utf8');f.on('data',t=>{i+=t});
f.on('end',()=>{
  i=i.trim();
  i=r(/eraser/g,'(');
  i=r(/erase/g,'(');
  i=r(/dreamer/g,'(');
  i=r(/dream/g,'(');
  i=r(/\(/g,'');
  console.log(i?'NO':'YES')
})
```
↓
https://atcoder.jp/contests/abs/submissions/8404356
コード長 315631 Byte，実行時間 520 ms


# 10. ABC086C - Traveling

```js
var i='',f=process.stdin;
f.resume();f.setEncoding('utf8');f.on('data',t=>{i+=t});
f.on('end',()=>{
  i=i.trim().split('\n');
  var n=+i.shift();
  console.log(i.every((x)=>{
    var r=x.split(' '),a=+r.shift(),b=+r.shift(),c=+r.shift();
    return a>=b+c&&a%2==(b+c)%2
  })?'Yes':'No');
})
```
↓
https://atcoder.jp/contests/abs/submissions/8428369
コード長 290242 Byte，実行時間 566 ms

# あとがき
コード長が膨れ上がり提出制限512KiBを超えるという懸念がありましたが，9.でちょっと引っかかった以外はなんとかすべて無事に通せました．
Brainfuckと違いどの記号がどんな処理をするか，といった対応がないため人力で書くのはなかなか骨が折れますがツールを使えば意外と簡単です．先人の研究に感謝です．

元のJSの時点で意味のない1文字変数が飛び交ったり，parseの代わりに暗黙の型変換を使ったり，グローバルを汚染したりとなかなかなクソコードでのお目汚し，大変失礼致しました．[^9]

[^9]: ところでJavaScriptで競プロを解くこと自体慣れていないのでより良い処理方法がありましたらご教授いただけると幸いです．