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