T-Rex Player (Google Chromeの隠しゲームを自動でやるやつ) を作った話

この記事は、TSG Advent Calendar 2015の19日目です。16日目は lip_of_cygnus さんの 任意の数字を出現させる話でした。

今回は、先月の駒場祭のTSGの展示で僕が展示した 「T-Rex Player」について書こうかと思います。

紹介

まずはこちらをご覧ください。



これです。
で、ソースコードは　ここ　です。

概要

Google Chromeには、隠し機能(イースターエッグ?)として、「インターネットにつながりません」の画面において、恐竜をジャンプさせるゲームが遊べる、というのがあります。*1これを自動でプレイさせる、というのを文化祭でやってみました。

目的とか

駒場祭に展示するため。実用性は(ほぼ)ない。もともと、あるブロック崩しを自動でクリアするために書こうとして尻切れトンボになっていたコードがあったので、それを流用して作った。*2

技術

画面の情報を得たり、キーボード入力を自動でやったりするのには、たいていWindowsAPIを使っています。いろいろなライブラリが出回っている昨今、直接APIを叩く機会はあまりないですが、このレベルの機能を使うことによって、今回のようなこと以外にも、APIフックとかDLLインジェクションとかができたりします。*3

WINAPIのとこのちょっとした解説

ウィンドウズのハンドルやデバイスコンテキストハンドルを適宜取得することによってやってます。
画面のHDCを得るのには、rensya_window.cpp の CopyWindow 関数を使ってます。これは、関数が呼ばれた瞬間のウィンドウを、いったん作ったビットマップに転写して、そのビットマップのHDCを返す関数です。これを使うとたとえば、一気に大量のウィンドウキャプチャを取っておいて、それを時間をかけてゆっくり画像にしていく、みたいなことができます。*4 *5
得たHDCをAIのjudjerに投げたあと、judjerで適当なところの色をGetPixelで得、その結果に従ってキーボード入力を自動でやっています。また、デバッグとかをしやすいように*6、その上から図形を上書きしたりしてます。
キーボード入力は、SendMessageで対象ウィンドウにWM_KEYDOWNとかWM_KEYUPとかを送ることによってやっています。(send_key.cpp内)　*7

judjerについての蛇足

AIと銘打ってはいますが、中では画像認識などの大層なことはしていません。いわゆるルールベースというやつです。 *8
得た画像の中ほどの高さのところの色を横一列に得ると、例えば
....#.#.....#.###.#.....##.#.....
とかいう感じで、障害物のあるなしが得られるので、これに従って、
....###.....#######.....####.....
というように障害物の位置を推測し、直前のものと比較して現在の画面の移動速度を得、また、障害物が近ければ飛ぶようにしています。

その他

展示中はわりかし順調に(2～30分ほど)跳び続けていたので、「このくらい人間にも簡単では?」と思われてしまい、来た人がなかなか驚いてくれませんでした。もうちょっと展示法を工夫するべきだったかなと思っています。*9

今後の展望

駒祭中に、「Googleの画像検索でブロック崩しが遊べる」を自動でプレイするのを書いたりしてましたが、わりと簡単に(おおざっぱに)書いてある程度動いたので、単純なゲームを自動プレイさせるのには向いてるんじゃないでしょうか。


この記事は、TSG Advent Calendar 2015の19日目でした。
23日目は、今のところ levelfour_ さんの「MLっぽい自作言語を実装する（願望）」ですが、他にも部員がいろいろ居るはずなので、その方々の記事が間に入ってくるはず(期待)です。

*1:Wifiを切るなり、機内モードにするなり、LANケーブルを引っこ抜くなりした状態で適当なウェブページに繋ごうとすると、DNS_PROBE_FINISHED_NO_INTERNETが出るので、その画面でスペースか上十字キーを押すとゲームが始まります。オンラインでも、こことかこことかでできるみたいです。

*2:何度やってもクリアできなかったので、プログラムにやらせようと思ってコードを書いていたのですが、実験としてやってるうちにクリアできてしまったので、やる気がなくなってしまってお蔵入りしてたのです

*3:展示二日目あたりに手を加えたところ、オブジェクトの破棄し忘れをやってしまい、頻繁にプログラムが落ちちゃってました。この現代においてメモリリークでバグらせるのはなかなかたいぎなので、特殊な用途でない限りはラッパを使った方がいいかと思います

*4:というか、ファイル名からして、その用途で使ってたものでした

*5:HDCから実際にピクセルの色を得るには、GetPixel関数が使えますが、これはあんまり速くなく、640×480の画像全体の画素を得る、とかすると到底リアルタイムでは処理できないのです(もっと速い方法を知ってる方がいれば教えてください)

*6:あと、展示としての見栄えがよくなるよう、展示中にいじって「それらしく」したりしてました

*7:これももっといい方法があったら教えてください

*8:当初は、適切なパラメタを機械学習させてやろうと思っていたのですが(ちょうど強化学習分科会とかやってましたし)、適当に手でいじっていると、安定して跳べるようになってしまったため

*9:あと、パックマンとかブロック崩しとかと比べて見てて単調なので、あんまり見る面白みがなかった気がする

第＊回超絶技巧分科会(難解プログラミング言語)

  • Brainf*ck

esolangとしてはわりかし分かりやすい言語です。
ひとつの左右に無限に長いメモリと、その上を動くひとつのポインタからできています。


命令は8つあり、C言語風に表すと、

 + ・・・memory[index] += 1;
 - ・・・memory[index] -= 1;
 > ・・・index += 1;
 < ・・・index -= 1;
 . ・・・printf("%c",memory[index]);
 , ・・・scanf("%c",&memory[index]);
 [ ・・・while(true){ if(memory[index]==0)break;
 ] ・・・if(memory[index]==0)break; }

といった感じ。というか、多分ソースコードをこれで置換してやるとそのままうまくいくと思います。

インタプリタ書きましたので参考までに。
https://gist.github.com/satos---jp/5212947b771e3779487b

まあ、たとえばこちらの方が便利かもしれませんが。
http://www.usamimi.info/~ide/programe/brainfuck/brainfuck.html
あと、小技として、
たとえば、20インクリメントしたいとき、

++++++++++++++++++++

ではなく掛け算的に

>++++[<+++++>-]

とするとか、if文的なことをしたいときに、

[ if文の中身 [-]]

とするとか。

第二回超絶技巧分科会。

Quineを楽して書きたい。

Cなどの場合、自分で書く->コピペをするのはつらい。

メタプログラミングしましょう。

P124参照。

s = <<'HERE'
#include<stdio.h>
char s[1024]=@;
int main(void){
	char *p,*q;
	for(p=s;*p;p++){
		if(*p!=64)putchar(*p);
		else{
			putchar(123);
			for(q=s;*q;q++){
				printf("%d",*q);
				if(*(q+1))putchar(44);
			}
			putchar(125);
		}
	}
	return 0;
}
HERE

os = s
os = os.sub("@"){s.dump}

print os

=begin
ruby make_c_quine.rb > o.c
gcc o.c
a > o2.c
gcc o2.c
a > o3.c
diff o2.c o3.c
=end

「C言語のQuineを出力するC言語のコード」を出力するRubyのコード

よい。楽。

ここで、ハタと気づく。

s = <<'HERE'
#include<stdio.h>

char bfc=0;
void tobf(char c){
	while(bfc<c){
		putchar('+');
		bfc++;
	}
	while(bfc>c){
		putchar('-');
		bfc--;
	}
	putchar('.');
}


char s[1024]=@;
int main(void){
	char *p,*q,d,b;
	for(p=s;*p;p++){
		if(*p!=64)tobf(*p);
		else{
			tobf(123);
			for(q=s;*q;q++){
				d = *q;
				if(d>=100)tobf(d/100+48);
				if(d>=10)tobf((d/10)%10+48);
				tobf(d%10+48);
				if(*(q+1))tobf(44);
			}
			tobf(125);
		}
	}
	return 0;
}
HERE

os = s
os = os.sub("@"){s.dump}

print os

=begin
ruby make_c_bf_yuine.rb > o.c
gcc o.c
a > o2.bf
inp.exe o2.bf > o3.c
gcc o3.c
a > o4.bf
diff o2.bf o4.bf
=end

「C言語 <-> Brainf*ck　間で動くYuine」 を出力するRubyのコード

Yuineとは
http://shinh.skr.jp/slide/ppencode2/007.html

むしろ、BFのみでQuineを書くより楽。

ということで、「自分の好きな言語 <-> Brainf*ck　間で動くYuine」
を作ってみましょう。

第一回超絶技巧分科会

Quineを(とりあえず)書く

eval s="print 'eval s='+s.inspect"

$ cat quine.rb
eval s="print 'eval s='+s.inspect"
$ ruby quine.rb
eval s="print 'eval s='+s.inspect"

「Quine」・・「プログラムのソースコード」と「そのプログラムを実行した結果出力」が
一致するようなプログラム。



考えなしにやろうとした結果

print "print "
print "\"print \"\nprint "
print "\"\\\"print \\\"\\nprint \"\nprint "

ちょっと考えて、文字列を使うようにした

$ cat quine_turai2.rb
s = "; print \"s = \" + s + s"; print "s = " + s + s
$ ruby quine_turai2.rb
s = ; print "s = " + s + s; print "s = " + s + s

おしい。
文字列を囲っている""をどうにかする必要がある。

解決法

  • エスケープシーケンス(%cみたいなやつ)を使う
  • 数字->文字の変換をする(.chrとかchr()とか)
  • そのほか、言語特有の機能を使う
スクリプト言語でQuine

asciiコードの対応
" ・・ 34
' ・・ 39
% ・・ 37
$ ・・ 36

あと、スクリプト言語の場合、「exec」 もしくは　「eval」 みたいな「文字列をソースコードとみなして実行する」ということができるので、同じ文字列を二回書かずに済む。

s="s=%c%s%c;print(s%c(34,s,34,37))";print(s%(34,s,34,37))

s='print "s=%c"%39 + s + "%c;exec(s)"%39';exec(s)

115 ・・ "s" のアスキーコード
61 ・・ "=" のアスキーコード

s="; puts 34.chr + s + 34.chr + s"; puts 115.chr + 61.chr + 34.chr + s + 34.chr + s

eval s="print 'eval s='+s.inspect"

ヒアドキュメントを使用した例

s = <<'H'
print ("s = <<'H'\n" + s + "H\n" + s)
H
print ("s = <<'H'\n" + s + "H\n" + s)

eval(
s = <<'H'
print ("eval(\ns = <<'H'\n" + s + "H\n)")
H
)

eval($s='print"eval(".chr(36)."s=".chr(39).$s.chr(39).");"');
コンパイル式の言語(C言語)でQuine
#include<stdio.h>
int main(void){
	char s[500]="#include<stdio.h>\0int main(void){char s[500]=\0;printf(\0%s%c%s%c%s%c0%s%c0%s%c0%s%c0%s%c%s%c%s%c%s%c\0,s,10,s+18,34,s,92,s+18,92,s+46,92,s+55,92,s+100,34,s+46,34,s+55,34,s+100,10);return 0;}";
	printf("%s%c%s%c%s%c0%s%c0%s%c0%s%c0%s%c%s%c%s%c%s%c",s,10,s+18,34,s,92,s+18,92,s+46,92,s+55,92,s+100,34,s+46,34,s+55,34,s+100,10);
	return 0;
}

つらい。
自分で手打ちして作るものではない。

#include<stdio.h> 
#include<string.h>
char h[256]=
	"#include<stdio.h>\n"
	"#include<string.h>\n"
	"char h[256]={";
char t[256]=
	"\nint main(void){\n"
	"	printf(\"%s\",h);\n"
	"	for(int i=0;i<strlen(h);i++){\n"
	"		printf(\"%d,\",h[i]);\n"
	"	}\n"
	"	printf(\"};\\nchar t[256]={\",34);\n"
	"	for(int i=0;i<strlen(t);i++){\n"
	"		printf(\"%d,\",t[i]);\n"
	"	}\n"
	"		printf(\"};%s\",t);"
	"	return 0;\n"
	"}\n";
int main(void){
	printf("%s",h);
	for(int i=0;i<strlen(h);i++){
		printf("%d,",h[i]);
	}
	printf("};\nchar t[256]={",34);
	for(int i=0;i<strlen(t);i++){
		printf("%d,",t[i]);
	}
	printf("};%s",t);
	return 0;
}

わりと人間味のあるソースコードになった。
ちなみに、これによって生成されるクワインは、

#include<stdio.h>
#include<string.h>
char h[256]={35,105,110,99,108,117,100,101,60,115,116,100,105,111,46,104,62,10,35,105,110,99,108,117,100,101,60,115,116,114,105,110,103,46,104,62,10,99,104,97,114,32,104,91,50,53,54,93,61,123,};
char t[256]={10,105,110,116,32,109,97,105,110,40,118,111,105,100,41,123,10,9,112,114,105,110,116,102,40,34,37,115,34,44,104,41,59,10,9,102,111,114,40,105,110,116,32,105,61,48,59,105,60,115,116,114,108,101,110,40,104,41,59,105,43,43,41,123,10,9,9,112,114,105,110,116,102,40,34,37,100,44,34,44,104,91,105,93,41,59,10,9,125,10,9,112,114,105,110,116,102,40,34,125,59,92,110,99,104,97,114,32,116,91,50,53,54,93,61,123,34,44,51,52,41,59,10,9,102,111,114,40,105,110,116,32,105,61,48,59,105,60,115,116,114,108,101,110,40,116,41,59,105,43,43,41,123,10,9,9,112,114,105,110,116,102,40,34,37,100,44,34,44,116,91,105,93,41,59,10,9,125,10,9,9,112,114,105,110,116,102,40,34,125,59,37,115,34,44,116,41,59,9,114,101,116,117,114,110,32,48,59,10,125,10,};
int main(void){
	printf("%s",h);
	for(int i=0;i<strlen(h);i++){
		printf("%d,",h[i]);
	}
	printf("};\nchar t[256]={",34);
	for(int i=0;i<strlen(t);i++){
		printf("%d,",t[i]);
	}
		printf("};%s",t);	return 0;
}
簡単なesolangでQuine

esolangの問題点

  • 文字列を持てないものがある。(s = "hogehuga" みたいなのができない)

基本的な考え方として、

A:「値を積んでいくパート」
B:「Aの部分を(Aで積んだものを破壊することなく)出力するパート」
C:「Aの部分に積んだものに従って出力するパート」

を作ればよい。

  • 前回の記事のアレの場合
  • A
#1#59#64#126#52#49#35#46#64#42#54#35#61#49#35#58#95#64#126#53#50#35#44#46#53#51#35#92#58#64#42#50#49#35#61#48#35#58#43#126#49#35#54#52#35#46
  • B
#1~+:#0=#12*@:\#35.,#25~@_:

ここで、A,Bの部分だけで実行すると、
Aの部分のみがまるまる出力される。
ー> Aの部分でどれだけメモリに数字を積もうとも、Aの部分は出力されるようになる。
あとは、Aの部分で、B,Cの部分の文字列を積んでやればよい。

  • C
#1=#6*@.#14~@;

で、Cで、Aの部分の文字を出力する。

  • Brainf*ckの場合

(全くゴルフしていないので、とても長くなってしまった)

+>>+>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>>>++++++[<+++++++>-]<+>>++++++++[<++++++++>-]<--<.>..<.>.<<<-[+><-[+<<<-]+>[->+>>[>>>]>.<<-[+<<<-]+>]<->>>+>[>>>]>>...<<<-]<[.<<<]
  • A
+>>+>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>
  • B
>>++++++[<+++++++>-]<+>>++++++++[<++++++++>-]<--<.>..<.>.<<<-[+><-[+<<<-]+>[->+>>[>>>]>.<<-[+<<<-]+>]<->>>+>[>>>]>>...<<<-]
  • c
<[.<<<]
  • 製作過程でできたもの
$ inp.exe myquine.bf
inited
+>>+>+++>>>+++++>>>+++++++>>>
halt
[1,0,0,0,3,0,0,5,0,0,7,(0),0,43,62,0,]
runtime .. 0.002001
+>>+>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>> //適当に積まれた入力

>>++++++[<+++++++>-]<+ //＋をメモリに積む
>>++++++++[<++++++++>-]<-- //＞をメモリに積む。
<.>..<.>.<< //先頭の５文字(＋＞＞＋＞)を出力する

<-[+>
<-[+<<<-]+> //先頭までポインタを戻す
[
		->+>>
		[>>>]
		>.<     //＋の出力
	<-[+<<<-]+> //先頭までポインタを戻す
]

//ここまでで、＋が出力される。

<->>>+>
[>>>]
>>...<<
<-]

// ここまでで、先頭の部分が文字として出力される。

<
[.<<<]
  • make_bf_quine.rb
source = "+>>+>"
prog = ">>++++++[<+++++++>-]<+>>++++++++[<++++++++>-]<--<.>..<.>.<<<-[+><-[+<<<-]+>[->+>>[>>>]>.<<-[+<<<-]+>]<->>>+>[>>>]>>...<<<-]<[.<<<]"

(1..(prog.size)).each{|x|
	c = prog[prog.size-x]
	for i in 1..(c.ord)
		source += "+"
	end
	source += ">>>"
}

source += prog

print source

prog の部分は、B+Cの文字列が入ってます。

まあ、だいたい似たようなことをやってます。


参考文献(サイト)

Quine・難解プログラミングについて
http://www.slideshare.net/mametter/quine-10290517/51
Quine いろいろ
http://shinh.hatenablog.com/entry/20081102/1225569359
コードを愛でる
http://shinh.skr.jp/slide/mederu/000.html
自己出力プログラムと自己参照プログラム
http://kreisel.fam.cx/webmaster/clog/img/www.ice.nuie.nagoya-u.ac.jp/~h003149b/lang/quine.html
quine.bf
http://d.hatena.ne.jp/KeisukeNakano/20070626/1182879045
Quineのゴルフ場
http://golf.shinh.org/p.rb?Quine

MMACTF 1st 2015 問題 i のwriteup

i言語という独自言語でquineを書け、という問題でした。
変数を持つ場所としてスタックのみが使えるので、その上でどうにかしなければいけません。

.icnファイルが実行できず、手元にいつも使っているパソコンがなかったので、excelのvbaでインタプリタを書くことにしました。下にコードを上げてます。
あと、.icnの実行方法が結局分からなかったので、どなたか教えてください。


使った命令は、

#23 #42　とか (それぞれ、スタックに23,42を積む)
+-*/ (四則演算)
= (比較。等しければ1を、そうでなければ0を積む)
, (値を数字で出す)
. (値を対応するアスキー文字で出す)
~ (値を-1倍する)
: (値のコピー)
\ (スタックの頭からa番目の値をコピーして積む)
@ (プログラムの実行位置をa文字分移動する)
_ (なにもせずにpopする)
; (正常終了する)　

です。実際の動作は、下のインタプリタを見てください。(多分あってるはず)

quineは、

#1#59#64#126#52#49#35#46#64#42#54#35#61#49#35#58#95#64#126#53#50#35#44#46#53#51#35#92#58#64#42#50#49#35#61#48#35#58#43#126#49#35#54#52#35#46#1~+:#0=#12*@:\#35.,#25~@_:#1=#6*@.#14~@;


になりました。

本質的な部分は、

#46#1~+:#0=#12*@:\#35.,#25~@_
:#1=#6*@.#14~@;　

で、それより前の沢山スタックに値を積んでるところでは、本質的な部分の文字のアスキー値を積んでいます。

まず、

#a#1~+:#0=#b*@:hoge#c~@

とすると、

for(i=a;i>0;i--){ hoge; }　

みたいな動作をしてくれます。(b,cは適当に調節する)
そこで、まず 

#46#1~+:#0=#12*@:\#35.,#25~@_

とすると、これはだいたい

for(i=46;i>0;i--){
  printf("#%d", スタックの頭からi番目の値　);
}

みたいなことをやってくれます。
これにより、本質的な部分の直前までの文字(#1#59 ... #35) が、スタックに値を残したまま出力されます。
あとは、

:#1=#6*@.#14~@;

が、だいたい

for(;;){
  p = pop();
  if(p==1)break;
  printf("%c",p);
}

に対応しているので、これで自分自身の文字列が全て出力される、という仕掛けです。


以下が実際に書いて使ったインタプリタです。

Dim A(1000) As Integer
Dim top, pc, isend
Dim s As String
Dim out As String

Sub initi()
 out = ""
 top = 0
 pc = 0
 isend = 0
End Sub

Function push(x)
  A(top) = x
  top = top + 1
  push = A(top - 1)
  Cells(1, top) = x
  
End Function

Function pop()
  Cells(1, top) = ""
  top = top - 1
  pop = A(top)
End Function

Sub instr(x)
  Dim p As Integer, q As Integer
  
  Select Case x
    Case "#"
        push (0)
    Case "="
        p = pop()
        q = pop()
        If p = q Then
            push (1)
        Else
            push (0)
        End If
    Case "*"
        p = pop()
        q = pop()
        push (p * q)
    Case "+"
        p = pop()
        q = pop()
        push (p + q)
    Case "-"
        p = pop()
        q = pop()
        push (q - p)
    Case ":"
        p = pop()
        push (p)
        push (p)
    Case "!"
        p = pop()
        If p = 0 Then
            push (1)
        Else
            push (0)
        End If
    Case ";"
        'MsgBox ("end")
    Case "\"
        p = pop()
        push (A(top - p - 1))
    Case "@"
        pc = pop() + pc
    Case "."
        out = out + Chr(pop())
    Case ","
        out = out + LTrim(Str(pop()))
    Case ";"
        isend = 1
    Case "0"
        push (pop() * 10 + 0)
    Case "1"
        push (pop() * 10 + 1)
    Case "2"
        push (pop() * 10 + 2)
    Case "3"
        push (pop() * 10 + 3)
    Case "4"
        push (pop() * 10 + 4)
    Case "5"
        push (pop() * 10 + 5)
    Case "6"
        push (pop() * 10 + 6)
    Case "7"
        push (pop() * 10 + 7)
    Case "8"
        push (pop() * 10 + 8)
    Case "9"
        push (pop() * 10 + 9)
    Case "~"
        push (pop() * -1)
    Case "_" '_
        pop
    Case Else
        MsgBox ("err! " + x)
        
    End Select
End Sub

Sub run(sss As String)
    Count = 0
    
    For i = 0 To 1000000
        Dim ns As String
        If Len(sss) <= pc Then
            Exit For
        End If
        
            
        ns = Mid(sss, pc + 1, 1)
        Cells(2, 1) = ns
        Cells(2, 2) = pc
        
        instr (ns)
        
        'If pc >= 68 Then
        'pc = pc
        
        'End If
        
         pc = pc + 1
       
    Next i
    
End Sub
'#1#59#64#126#52#49#35#46#64#42#54#35#61#49#35#58#95#64#126#53#50#35#44#46#53#51#35#92#58#64#42#50#49#35#61#48#35#58#43#126#49#35#54#52#35#46#1~+:#0=#12*@:\#35.,#25~@_:#1=#6*@.#14~@;

Sub main()
    initi
    
    Dim se As String
    
    se = "#1#59#64#126#52#49#35#46#64#42#54#35#61#49#35#58#95#64#126#53#50#35#44#46#53#51#35#92#58#64#42#50#49#35#61#48#35#58#43#126#49#35#54#52#35"
   'se = "#1#59#64#126#52#49#35#46#64#42#54#35#61#49#35#58#95#64#126#53#50#35#44#46#53#51#35#92#58#64#42#50#49#35#61#48#35#58#43#126#49#35#48#49#35"
   ' se = "#1#59#64#126#57#49#35#46#64#43#54#35#42#54#35#126#33#61#49#35#58#95#64#126#49#51#35#44#46#53#51#35#92#58#64#43#50#49#35#42#50#49#35#126#33#61#48#35#58#43#126#49#35#55#53#35"
    'se = "#1#59#64#126#57#49#35#46#64#43#54#35#42#54#35#126#33#61#49#35#58#95#64#126#49#51#35#44#46#53#51#35#92#58#64#43#50#49#35#42#50#49#35#126#33#61#48#35#58#43#126#49#35#48#49#35"
    
    'se = "#1#59#64#126#57#49#35#46#64#43#54#35#42#54#35#126#33#61#49#35#58#95"
    'se = "#1#59#64#126#57#49#35#46#64#43#54#35#42#54#35#126#33#61#49#35#58#95#64#126#49#51#35#44#46#53#51#35#92#58#64#43#50#49#35#42#50#49#35#126#33#61#48#35#58#43#126#49#35#48#49#35#57#53#35#52#54#35#54#50#49#35#55#53#35#57#52#35#53#51#35#54#52#35#52#54#35#51#52#35#52#53#35#53#51#35#50#52#35#52#53#35#53#51#35#54#50#49#35#51#51#35#49#54#35#57#52#35#53#51#35#56#53#35#53#57#35#52#54#35#54#50#49#35#57#52#35#49#53#35#53#51#35#52#52#35#54#52#35#51#53#35#49#53#35#53#51#35#50#57#35#56#53#35#52#54#35#51#52#35#48#53#35#57#52#35#53#51#35#50#52#35#48#53#35#57#52#35#53#51#35#54#50#49#35#51#51#35"
    
    'se = "#1#56#35#49#48#35#49#126#43#58#35#48#61#33#126#35#49#50#42#35#49#50#43#64#58#92#35#51#53#46#44#35#51#49#126#64#95#58#35#49#61#33#126#35#54#42#35#54#43#64#46#35#49#57#126#64#59"
    'se = "#1#12#12#12#14#13#16#15#17#19#18#25#1#38"
    'se = se + "#57#1~+:#0=!~#12*#12+@" 'forのための。
    se = se + "#46#1~+:#0=#12*@" 'ないなら0なので。
    se = se + ":\#35.,#25~@" 'ループ1
    'run (se)
    'MsgBox (out)
    se = se + "_:#1=#6*@"
    se = se + "."
    se = se + "#14~@"
    se = se + ";"
    Cells(3, 1) = se
    run (se)
    'MsgBox (out)
    Cells(4, 1) = out
    
    Dim cs As String
    cs = ""
    ccs = ""
    
    For j = (Len(se) - 43) To Len(se)
        nc = Mid(se, j, 1)
        cs = ("#" + LTrim(Str(Asc(nc)))) + cs
        ccs = ccs + nc
    Next j
    
    Cells(5, 1) = cs
    Cells(7, 1) = Len(cs)
    Cells(6, 1) = ccs
    Cells(8, 1) = Len(se)
    
End Sub