LoginSignup
5
2

More than 3 years have passed since last update.

@Mopepe51(雪下)

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

Posted at

まえがき

久しぶりにWikipediaの難解プログラミング言語の記事を見たら言語例にJSFuckという言語が追加されていました1．
やればできそうなのでこの言語を使って精選10問2を解いてみることにしました．

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 )()
ですね．3

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

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

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

一般解

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

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で標準入出力を扱うテンプレとしては


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

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

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

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

0. PracticeA - Welcome to AtCoder

解答はこんな感じです．

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


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

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

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

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

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

u=(s+[]).split('').reduce((x,y)=>x+ +y,0);

のところは
数値→文字列に変換→配列に変換→各文字を数値に変換しながら総和を取る
という操作になっています．
大変読みにくいですね，実務でこんなコードを書いた日には殴られそうです．

6. ABC088B - Card Game for Two

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

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

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

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

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 で提出できた例もあったので問題ないはずですが何故でしょう……

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

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

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の代わりに暗黙の型変換を使ったり，グローバルを汚染したりとなかなかなクソコードでのお目汚し，大変失礼致しました．10

  1. 変更履歴によれば2019/05/23のことである． ↩

  2. @drken さんによる記事 AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ に提示された初心者向け問題を集めた10問．言語を触って遊んでみるのに丁度いい難易度の問題が揃っています．現在はAtCoder Beginners Selectionとして問題セットがまとめられています. ↩

  3. "filter"は(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]，"constructor"は([][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]]+[])[!+[]+!+[]+!+[]]+(!![]+[][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]])[+!+[]+[+[]]]+([][[]]+[])[+!+[]]+(![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[+!+[]]+([][[]]+[])[+[]]+([][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]])[+!+[]+[+[]]]+(!![]+[])[+!+[]]となる． ↩

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

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

  6. 参考：https://qiita.com/ytanto/items/caf7bf0ba287da81b20f ↩

  7. 早速「(ほぼ)どんなコードでも実行できる」の反例が出てしまいました． ↩

  8. 参考：https://qiita.com/alucky0707/items/46f8a3e0c523d3bd4034 ↩

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

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

5
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
2