prime's diary

そすうの日々を垂れ流しちゃうやつだよ

AtCoder橙/Codeforces International Grandmasterになりました

この記事は色変記事アドベントカレンダー1日目の記事ではありません。

AtCoderで橙色、CodeforcesでInternational Grandmaster(IGM)になったので振り返り記事を書きます。

f:id:PrimeNumber:20210117052734p:plain
AtCoderのレーティング推移
f:id:PrimeNumber:20210117052826p:plain
Codeforcesのレーティング推移
まあ、Codeforcesの方はIGMになった後GMに落ちちゃったんですが…

感想

Codeforces IGMは昔からの憧れでもあったので、とても感慨深いものがあります。というか、自分がなれるものだとは思っていなかった節があります。 一方で、AtCoder橙は訓練を積めばそのうちなれると信じていたんですが、結果としてCodeforces IGMの方が早く達成できてしまいました。こういう人あんまりいないみたいで謎です。

やったこと

ABC-EF埋め

2020年2月ごろに全部埋めた。(今は数問埋まっていない…) 典型問題の処理がうまくなると、難しい問題の方針も立てやすいし、なにより序盤の簡単な・典型的な問題で時間ロスをしにくくなると思います。

黄Diff(🧪含む)埋め

2020年4~5月 AtCoder ProblemsでDifficultyが黄色になっている問題を全部解きました。黄色Diffばっかりやるのは黄Diff問題に頭が過学習する感じがあってあんまりよくなくて、橙や青Diffも混ぜて解くべきでした。 文字列系の問題は、これまでZ-algorithmとかSuffix Arrayとかほとんど使ったことがなかった(解けない or ローリングハッシュで殴りがち)ので、ここで復習できたのは良かったです。

同じ黄Diffでも体感難易度にはかなりばらつきがあって、これは自分の得意不得意の偏りだけでなく、そもそものDifficultyの算出精度の限界もありそうです。

黄Diffを全部埋めた後は橙Diffと青Diffを解こうとしましたが、橙Diffは全然解けなくて挫折してしまiいました。今年は橙Diffと正面から向き合っていきたいです。

コンテストに出る

これが自分にとってはかなり効いた感じがします。 というかこれまであんまり出てなかったのが良くなかったです。

コンテスト時間いっぱいあきらめずに噛り付くとか、実装の簡単な方針を考えるとか、複数の問題が残っているときにスッと戦略を切り替えるとか、そういう力が結構養われたように感じています。

今後について

この先の色変目標となると、AtCoder赤とかCodeforces Legendary Grandmasterになりますが、正直全然なれる気がしないので、あまり気負わずじわじわと強くなれるといいなと思っています。

どうしても平日は労働で疲弊してしまうのと、趣味で競プロ以外にもやりたいことがいっぱいあって、正直あまり多くの時間を割けない気はしますが…

まずはAtCoder橙/Codeforces IGMで安定できるようにしていきたいと思います。

あといい加減今使っている競プロライブラリがつらい(C++03/11、ICPC想定で可読性より短さ重視)ので、一新していくつもりですが、今のところリポジトリだけ作って放置しています…

github.com

フラグメントシェーダを用いて、VRChatのワールドで計算機を作る 【KMCアドベントカレンダー 2日目】

この記事はKMCアドベントカレンダー 2日目の記事です

adventar.org

概要

最近遊んでいるVRChatというゲームにはユーザーの作成したアバターやワールドをアップロードできる機能があります。さらに、アバターやワールドのバーテックスシェーダー*1/フラグメントシェーダー*2を自分で作ったものに差し替えてアップロードすることができます。

これを悪用(?)し、fragment shaderにBrainf*ckという難解プログラミング言語インタプリタを実装することで、VRChatで、ゲームプレイ中に指定した任意の計算を実行することができるような仕組みを実装しました*3

GPGPUとは

みなさんが普段ゲームなどのグラフィック処理をするときには、大抵GPU(Graphic Processing Unit)という装置*4が使われます。 GPUは、三次元のポリゴンの移動・変形や、陰影処理等の計算を行うために、たくさんの演算機を備えています。

この演算機の演算能力をグラフィック処理以外にも使おうというアイデアが、GPGPU(General Purpose compution on GPU)と呼ばれています。 今日では、GPGPUはCUDAやOpenCL、OpenACC、グラフィックAPIのCompute Shader等によって比較的手軽に行えるようになりました。

VRChatにおける演算

VRChatはゲームなので、これらの便利なGPGPUプログラミング環境を使う方法はありませんが、アバターやワールドのバーテックスシェーダー/フラグメントシェーダーなどである程度の計算を行うことができます。 バーテックスシェーダーでは各頂点ごとに、フラグメントシェーダーでは画面の各画素ごとにシェーダーのプログラムが実行されます。 が、通常これらのシェーダーは状態を保存したり、他の頂点/画素と通信することはできません。GPUはたくさんのプログラムを並列で計算することでスループットを稼いでいるため、単一の要素に対する計算はあまり高速ではありません。 したがって、まともな速度でゲームが進行するためには、1頂点/画素あたりの計算量は十分小さくないといけません。 つまり、これらのシェーダーで大規模な計算をすることはできません(完)。

という問題を解決する方法がいくつかあり、今回はCustomRenderTextureを使いました。 CustomRenderTextureでは、ダブルバッファリングを有効にすることで、フラグメントシェーダー上で「前のフレームの演算結果」をテクスチャの色情報として得ることができます。また、他のテクスチャ(他のCustomRenderTextureを含む)を入力として受け取ることもできます。 これを利用すると、テクスチャ上に状態を保存することで、フレームをまたいだ計算が可能になります。 また、前のフレームの別の画素の色情報を得ることもできるので、フレームをまたぐことで別の画素と通信が可能になり、並列計算への道が開かれます。 テクスチャは2048x2048程度は問題なく持つことができるため、400万ワードほどのメモリを持つことができます。

これにより、理論上は任意の計算を他のプレイヤーのGPU上で走らせることができます。 とはいえ、shaderのプログラムはアップロード時に決定されてしまうため、このままでは動的に(ゲームプレイ中に)実行するプログラムを差し替えることはできません*5

そこで、fragment shaderに何らかの仮想計算機を実装し、何らかの方法でゲームプレイ中にプログラムを与えることで、ゲームプレイ中にプログラムを差し替えて計算することができるようになります。

Brainf*ck

Brainf*ck*6は難解プログラミング言語と呼ばれる、「プログラミングすることが難しい」プログラミング言語のひとつです。Brainf*ckではソースコードは8つの命令のみで構成されていて、それぞれごく単純なことしかできません。 詳しくは、Brainfuck - Wikipediaなどを参照してください。 例えば、現在VRChatのBF Interpreterワールドに置かれている、4段のハノイの塔のパズルの解法を計算するプログラムは次のようになります。見やすさのために改行やインデントを入れています。 gist.github.com

Brainf*ckでまともな計算をすることはとても難しいですが、Brainf*ckの処理系(コンパイラ/インタプリタ)を作ることは(他のプログラミング言語に比べて)比較的簡単です。 今回は今後より実用的な処理系を作る練習として、実装の容易なBrainf*ckインタプリタを実装することにしました。

処理系の構成

f:id:PrimeNumber:20201202235407p:plain
BF処理系の全体像

処理系本体

処理系の本体はこの図の赤色の部分で、Interpreter Shaderが計算を、Memory/State Textureが状態を保存する役割を果たしています。 Memory/State Textureは64x64pxのRGB値を持ち、最初の1行が命令カウンタなどの状態管理用レジスタ、残りの行がBrainf*ckプログラムの使用するメモリ領域になっています。 状態管理レジスタは[命令カウンタ, データポインタ, 動作モード(実行/前方にジャンプ/後方にジャンプ/プログラム終了), 入力済みバイト数, 出力済みバイト数, 出力データ, ジャンプ時の[ ]の対応を見るカウンタ, 出力validフラグ]の8個となっています。 シェーダー内部では、R,G,Bの各色に対して8bitのデータをエンコードして持たせることで、1画素あたり24bitのデータを保持しています。

処理系の動作はおおむね次のように動きます。 状態管理レジスタに該当する画素: 各レジスタの次フレームの値を計算する - 命令カウンタなら、1進めたり、ジャンプ命令では戻ったり - データポインタは> <命令を実行する状態になっているときのみ増減させる - 出力validフラグは、.命令を実行する状態になっているときのみ1、それ以外を0にする など メモリ領域に該当する画素: データポインタが自身のアドレスと一致しているときのみ、いま命令カウンタが指している命令が+ - ,なら、適切に値を変更する

このような実装により、1フレームに1命令(ジャンプ時はジャンプ場所を線形探索するため何フレームもかかりますが)処理する処理系ができました。

Control Panel

ワールドに設置したカメラでアバターを検出することにより、タッチパネルを実現し、状態のリセットを行うことができます。カメラで撮影した画像をRenderTextureに出力する機能を利用しています。これにより他のシェーダーがプレイヤーの操作を受け取ることができます。 Control Shaderはカメラの入力画像をparallel reductionにより使いやすい形に変換しています。

Output Buffer / Output Text Buffer

出力バッファー用のシェーダーとテクスチャです。 Memory/State Textureの出力validフラグが来たら1文字読み、次の書き込み位置を一つずらします。 Output Text Bufferでは、改行が来たときにも次の書き込み位置を次の行の先頭に移動します。

表示用のシェーダー/テクスチャ

処理系内部では数値はRGB値にエンコードされているので、これを人間が理解できる形式に変換する処理が必要です。 デバッグ用の出力は2進数に変換して黒/白で表示しているだけです。 ソースコードと出力のテキスト表示は、しみさんの

をお借りして実現しています。図がぐちゃぐちゃになるので、上の構成図からはフォント用のテクスチャは省略してあります。 フォントデータが2値画像(をRGBA32bitに詰め込んだもの)なので、大きく表示したときにジャギーが目立つと感じたので、中央値を基にしたジャギー軽減アルゴリズムを実装しています。

今後の課題

  • ソースコードを編集する機能がないので、簡易なテキストエディタを実装して、プレイ中にソースコードを差し替える仕組みを作る
  • ワールドにはインターネット上から画像をダウンロードする方法が存在するので、これにより外部から動的にソースコードを持ってこれるようにする
  • より高級な計算用仮想マシンを実装する
    • Piet DM's Esoteric Programming Languages - Piet の処理系ができると見た目に楽しそう ただし、カラーブロックの連結成分の大きさを高速に求めるのは簡単ではない。
  • 並列計算が可能な仮想マシンアーキテクチャを実装する
    • フラグメントシェーダーはその仕様上、「指定した場所に値を書き込む」という仕組みの実現が難しい(複数フレームを掛けてデータをルーティングする必要がある)
  • 高級で並列計算可能な計算機で、実用的な計算速度を得る

*1:ポリゴンの頂点位置を計算するプログラム

*2:色や陰影を計算するプログラム

*3:CPU側に干渉するわけでもなく、負荷も軽いので他のプレイヤーが困ることはないです

*4:これは物理的に個別のユニットとして存在することもあれば、CPUと同じチップ内に存在することもあります

*5:数個程度なら条件分岐で差し替えることはできる

*6:*にはuが入ります

競技プログラミングはISUCONの役に立つ 【ISUCON10予選参加記】

単なる普通のISUCON参加記です。 そんなに競技プログラミングの話はないので、そういう話を期待していた人はごめんなさい。

こういうのは忘れないうちに書かないと書けないがち。

isucon.net

ISUCON10にチーム「:羽付きのお札:」で nana ( 久我山 菜々🐇🏰🕛🥕 (@nonamea774) | Twitter ) と yu3 ( ゆー (@yu3mars) | Twitter ) のメンバーで出て、最終1195点(時間中の最高点は1400点ほど)で予選落ちでした。

開始前日まで

チームでどの言語を使うかを事前にGo言語に決めて、Go言語の勉強ついでに、練習として去年の予選問題を解いたりしていた。 ちなみに自分では23,000点ぐらい(当時のスコアで言うと全体の6位くらい)出せていた(もちろん他の人のブログとかを参考にした)。

開始直前

nanaは偶然にも(?)東京に来ていたので私の部屋で一緒にやることにした。yu3とはslack call等でコミュニケーションを取る。 開始が遅れたのでゆっくり朝食をとった。

なぞって検索

開始するとさっそくポータルが502で落ちていた…まあ数分で見えるようになったので問題を呼んだりsshで入れることを確認したり、実際にブラウザで触ったりした。 明らかに「なぞって検索」がやばそう。案の定広い範囲を囲うとめちゃくちゃ遅い。 ポータルが不調で、まだベンチマークに掛けられなかったので、なぞって検索について考える。

こういう二次元データを囲った範囲に入る点を求めるのは、大抵なんらかの賢いデータ構造(kd-treeとかそういうやつ)が必要になるはず(これは割と競技プログラミングの経験が役に立った感じ)。 でもこれを手で実装するのはしんどそうで、nanaに相談したら、GISデータとかをmysqlとかでうまく扱える仕組みがあるはず、と教えてくれたので調べることにした。 なるほどたしかに、Geometryという形式で格納して、Spatial indexを有効にしておくといい感じにやってくれるらしい。 のでこれを実装することにした。

物件の追加クエリとかスキーマ定義はまだいいとして、初期化時に使う.sqlファイルを更新するのがだるい。 コンテスト後にgenerated columnsというのがあるというのを知ったが、このときは知らなかったので、Rubyでクエリ文をパースするスクリプトを書いて書き換えた。

途中で、「椅子を通せるドアかどうかを判定する方法」(椅子にはH,W,Dの情報、ドアにはH,Wの情報が与えられるので、椅子を直方体だと思ったときにうまく回転させることでドアを通せるかどうか)を計算するのに、すべての回転を調べるのは非効率なのでなんとかしたい、という相談をnanaから受けた。 ちょっと考えると椅子の大きさのうち、最大のものは考えなくて良い(その方向を奥行き方向に持ってくれば、残り2方向がドアを通せれば良く、それで通せなければ通らない)ことに気付いた。 ここでも競技プログラミングの経験が効いた気がする。

実装が終わってちゃんと動くようになると、ちゃんとスコアが跳ねて喜ぶ。(700店くらい?) そしてスロークエリログを眺めると自明にインデックスを張れる場所があるので張ると、さらにスコアが跳ねた。 この時点で20位ぐらいだったかな?

インフラまわりとかデプロイ周りとか

基本的にゆーさんとnanaに任せていたので詳しくはわかっていないけど、botを弾くとかが若干効果があったのかな? デプロイはmake deployとかを叩くと、Makefilessh hogehogeとか書いてあるのでそれでローカルのバイナリとかをサーバーに送って、アプリ等を再起動する、というあたたかみのある方法になった。 とはいえ、ISUCONの短時間という制約ではそんなに悪くない方法だと思う。終了後に知ったetckeeperとかは今後試してみたい。

物件・椅子の入稿

ここまで来て、原因不明の「critical error」でスコアが0になることが何度か起きた。 とくにエラーが起きるような変更は見当たらなかったのでだいぶ悩んだが、スロークエリログを眺めると、COMMITで5秒かかっていて、どうやらここでタイムアウトしているらしい。 アプリを眺めると明らかに物件・椅子の入稿がやばい(トランザクション内で、csvの行数だけINSERTが発行される)ので、これをどうにかすることを考える。 nanaが文字列結合等を駆使して巨大なINSERTを1回だけ発行する方法を、私がPrepareをつかって1クエリの負荷を低減する方法を実装した。 結果的に同じとこをいじることになったのは、短い時間の使い方としては失敗だったかも。 ちなみにどちらの実装でもタイムアウトは回避でき、failは回避できるようになった。

検索クエリの改善

ここまで来て、物件・椅子の検索が支配的になってきたので、これを考える。 うまく行きそうなインデックスを張ってみるが、範囲指定が2個出てきたりすると、普通に張ったのでは速くならないっぽいので困ってしまった。 実はMySQL8にすると行けるらしいが、知らなかったしかなり罠が多かったみたいなので、うっかり足を踏み入れなくてよかったかもしれない(?)

大きさに関するクエリは、範囲として指定できるのがそれぞれ4種類(+指定なし)しかない。 したがって、範囲に0〜3のIDを割り振れば、HeightRank = 2みたいなクエリになってインデックス使えそう、となって実装し始めるが、これは最終的には間に合わなかった。 ここもgenerated columnsを知っていればサクッと実装できた気がするので悲しい。

nanaは色や椅子の種類をIDに変換するコードを書いていた。けっこうバグってたけど最後にはちゃんと動いていた。

DBの負荷分散

mysqlがCPUの85〜95%程度を食っていたので、この負荷を分散したかったが、更新があるのでレプリケーションは実装間に合わなさそう(この時点で残り1時間程度)、と思って却下した。 しかし、終了後に教えてもらったこととして、このアプリは椅子と物件でJOINすることがないので、二つのデータベースを別マシンに分けることで、負荷分散が比較的簡単に可能という構造になっていた。 このあたりは、よくアプリの構造を観察することで見つけられたはず(こういうところも競技プログラミングみがある)で、かなり悔しいポイント。 物件検索と椅子検索でそれぞれ半分くらい時間がかかっていたので、もしDB分割をやっていれば、2倍程度のスコアになったと思われ、これは本戦出場ライン近辺になるので、取り組めていれば…と悔やむ。

終了後

終了後は高速に nanaとチーム「百万円ドリブン」の twitter.com と、偶然来ていた ten986 (@ten986) | Twitter とうしとらに打ち上げに行った(そのあとさらに2軒はしごした)。びーるうめえ。

良かった点

事前に練習したおかげで、Go言語の実装・コード読解で詰まることが少なかった。 チームメンバーと互いに相談して、より良い解決策に近づけた。 競技プログラミングの経験を役に立てられた。

反省点

DBに関する知見(generated columns)がまだまだ足りない。 アプリの構造をよく観察するべき。 決勝に進みたい!

試してみたい点

Go言語、静的型付け言語とは何だったのかというレベルで静的検査が弱くてつらいので、Rust使いたい(ほんまか?????)

オンラインBrainf*ckインタプリタ・デバッガを作った【Brainf*ck Advent Calendar 2019とその他のAdCの17日目】

はじめに

この記事はBrainf*ck Advent Calendar 17日目・KMC Advent Calendar 17日目・LeapMind Advent Calendar 17日目の記事です。

adventar.org

adventar.org

adventar.org

概要

難解プログラミング言語の一つであるBrainf*ckのオンラインデバッグ環境を作った話をします。

作ったものは……これ!!!👉👉👉👉👉Online Brainf*ck debugger👈👈👈👈👈

Brainf*ckデバッガについて

Brainf*ckはその仕様上、極めてバグを埋め込みやすいです。具体的には、

  • 変数名とかそういうものはなく、アドレスだけで値を参照・操作する
    • そのうえ、アドレス移動は相対移動(元の位置から+1/-1のみ)しかできないので、参照先を間違えやすい
  • 関数とかいう便利な機能もないので、重複したコードが登場しやすい
  • +, -, >, <命令はよく連続して使われて数え間違えやすく、しかも使う個数を1個でも間違えるとバグる

したがって、(特に大規模な)Brainf*ckプログラムを作成する上ではデバッガの存在はとても大切です。

ということで数年前に

moon.kmc.gr.jp

というデバッガを作ったのですが、如何せん古くなってきたので新しく作り直すことにした、というのが今回の内容です。

現在の機能

インタプリタ

  • Brainf*ckのコードを実際に実行することができます。標準入力を与えることもできます。
  • デバッグモードを有効にすると、100msごとなど指定した時間間隔で命令を実行させられます。
  • 入出力をUTF-8の文字列と解釈するか、16進数と解釈してバイナリを扱うかを選択できます。
  • Brainf*ckではEOFに達したときに入力命令を実行した場合の値は規定されていませんが、これを0と-1(255)で選択できます。

デバッグ機能

  • プログラムカウンタとデータポインタの位置を表示します。
  • @命令に達するとそこで実行を停止させることができます。停止させた後はステップ実行などで細かくプログラムの動作を追うことが可能です。
  • :命令に達すると標準エラー出力に今のポインタの指す値を出力します。.標準エラー出力版です。
  • 指定した範囲のメモリの内容を見ることができます。

その他

  • インタプリタをWebWorkerで動かすことで、重いプログラムを動かしてもUIが重くならず、無限ループに陥ってもページを再読込する必要がない
  • インタプリタjQueryで頑張って書いていたが、Vue.jsを使ってまともなコードになった

今後追加したい機能

旧デバッガにあった機能

  • 今のプログラムカウンタの位置やデータポインタの位置を視覚的に表示する
  • 命令実行ログを取得する
  • ログを遡って実行を逆再生できるようにする
    • ステップ実行などで通り過ぎると悲しいため

あると嬉しそう

  • デバッグ時のステップ実行より高度なデバッグ実行機能
  • デバッグ時のメモリ内容書き換え
  • コードスニペット(あるいはより強力なマクロ機構)
  • コードテスト機能
  • デザインをかっこよくしたい
  • @命令はプログラムカウンタに対してトリガを掛けるが、データポインタとかメモリ上の値に対してトリガを掛けられるようにする
  • コードに対してシンタックスハイライトとか自動インデントとか補完とかしたい(エディタとしての機能をつける)
  • デバッグOFF時の性能向上

ということで半分ぐらい実装できてないですが、便利ではあるのでぜひ使ってみてください! もし欲しい機能やバグがあれば、

github.com

このリポジトリにIssueを立てるか、自分で実装してPull Requestを投げてください!

ではよきBrainf*ckプログラミングライフを!

いろいろなBrainf*ck処理系における値の0初期化、ムーブ、コピー、便利なイディオム 【Brainf*ck Advent Calendar 2019 5日目】

この記事はBrainf*ck Advent Calendar 2019 5日目の記事です。

adventar.org

4日目の記事はmatsu7874さんによる「RustでBrainfuckインタプリタを実装した話を書けるだろうか?」の予定です。 6日目の記事はあんでぃ@量産型テ徒???? /-500/さんによる

unidentifiedexe.hatenablog.com

です。

この記事は

adventar.org

5日目の記事でもあります。空いていたので埋めました。 4日目の記事はnakarioさんによる

qiita.com

6日目の記事はdnek_さんによる

www.dnek.app

でした。

Brainf*ck処理系同士の非互換性

Brainf*ckの処理系(コンパイラおよびインタプリタ)にはもとの言語仕様の曖昧さ等から、様々な細かい仕様の違いが存在します。

例えば、EOFの扱いで、多くの処理系では、 . を実行したときにEOFに到達していた場合は0または-1が格納されます。

これについては、予め実行する処理系がわかっていれば、比較的簡単に対処することができる場合が多いです*1

他にも用意されるセルサイズや、負番地への進入・アクセスができるか、文字コードの扱いなどの違いもあります。

しかし、最も対処が大変な差異の一つが、一つのセルに格納できる値の範囲と、セルの値がオーバーフローした際の挙動です。

値の範囲とオーバーフローの扱いについてざっと上げられるだけでも、

  • セルサイズ: 1bit、8bit、16bit、32bit、多倍長など
  • 値は符号付きか符号なしか、符号付きの場合の表現方法
  • オーバーフロー時にwrap-aroundするか、saturateするか、多倍長整数によりオーバーフローが起こらないか、はたまた実行時エラーになるか
    • wrap-around: オーバーフロー時に反対側(最大値に1を足してでオーバーフローしたなら最小値、最小値から1を引いてオーバーフローしたなら最大値になる)
    • saturate: オーバーフロー時の結果を表現できる値に切り詰める(最大値に1足しても最大値のまま、最小値から1引いても最小値のまま)
    • bignum: 多倍長整数を使って値を格納するので、原理上オーバーフローは起こらず、(メモリの許す限り)任意の大きさの数を格納できる
    • runtime error: オーバーフローでランタイムエラーになる

といった違いがあります。 符号の有無とオーバーフローの挙動を表にするとこんな感じで少なくとも8通りが考えられるわけです。

符号 あり なし
wrap-around 1 2
saturate 3 4
bignum 5 6
runtime error 7 8

wrap-aroundの場合は符号の有無はあまり関係ない(符号付きで2の補数じゃないBrainf*ck処理系、ある…?) wrap-aroundが一番多く、例としてはUbuntuのaptで入るbfUbuntu – Details of package bf in bionicのデフォルト挙動とか。 bfはオプションでwrap-aroundではなくruntime errorにすることもできる。

0初期化とムーブ、コピー

ここで問題になるのが、あるセルに対して、その値を0にしたい、あるいはコピーやムーブといった基本操作がしたいというときです。

ムーブはあるセルの値を他のセルに代入し、元のセルの値は0にするという操作です。はたまた コピーはあるセルの値を他のセルに代入し、かつ元のセルの値はそのまま保持する操作です。

brainf*ckでは大抵の操作が破壊的操作なため、ムーブよりコピーのほうが複雑で、値のコピーはかなり重要なテクニックになります。

これらの処理はwrap-around環境では簡単で、0初期化なら[-]あるいは[+]で0初期化できます。 また、符号なしの場合はどの仕様でも(最適化がしょぼくて時間がかかるかもしれませんが)[-]で常に0初期化できます。 隣のセルへの値のムーブも[>+<-]で行うことができ、それを応用して[>+>+<<-]>>[<<+>>-]などで隣のセルへ値をコピーできます。

問題は符号ありでwrap-aroundでない場合で、たとえばセルの値が負の数の場合に[-]を実行すると永久に終わらないか実行時エラーになってしまいます。

これに対する対策はいくつかあります。まず簡単なものとして2つあり、

  1. セルに入っている値の符号がわかっている場合: 0初期化なら符号に応じて[-][+]を使い分ける。ムーブなら[>+<-][>-<+]を使い分ける。符号なしの場合は[-][>+<-]だけでできるのはこれの特殊な場合。
  2. セルに入っている値の範囲(a<=x<=b)がわかっている場合(runtime error環境の場合は、さらにb-aがオーバーフローしないこと): aを引くことで非負の値にすることができ、あとは0初期化なら[-]を実行し、ムーブなら[>+<-]を実行し、aを足せば良いです。これにより、saturate環境での0初期化が行えます(最小値の絶対値(あるいはそれ以上の値)を足す)。saturate環境では、aの減算でsaturateが起こる可能性があるので、このままではムーブはできませんが、そもそもsaturate環境で情報を失わずに値を更新することが不可能なため、これはあきらめて、自前で値の範囲を管理して、saturateが起こらない範囲で計算すべきです。

さて、問題はこのどちらの仮定も満たさない場合です。 Brainf*ckにはセルの値の符号を直接確認する方法がないため、1つめの方法に帰着するのは難しそうです。一方、bignum環境ではセルの値の範囲は全くわからないため、2つめの方法に帰着するのも難しそうです。

ちなみにruntime error環境やsaturateまたはwrap-aroundだが値の範囲が232とか264とかめちゃくちゃでかく、かつ値の0初期化やムーブ、コピーに対する最適化がない場合、saturateより更に厳しく、絶対値の大きい値をいじると死にうる*2ので、でかい値にしないように値の範囲の制御を常に頑張る以外の選択肢はないです。

3. 単調減少/増大列と大小比較による方法

特定の範囲内に値があるかを判定する

Brainf*ckではうまく工夫することによって、あるセルの値が指定した範囲内にあるか判定することができます。 いま、隣り合う2セルがあり、左側のセルの値が正であることがわかっているとしましょう。

0 1 2 3 4 5 6 7
0 1 1 x(>0) y 0 0 0

この例では3番地と4番地の値x,yについて、0<=y<xであるかを判定したく、3番地の値xが正であるとしましょう。 上の表のように値がセットされており、いまポインタが0番地にあるとすると、

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

これを実行すると最終的にポインタは6番地に移動し、もし0<=y<xであるならば6番地の値が正(x-y)になり、そうでなければ0になります。 本質は[->]で、「ポインタの指す先が0でないなら1を引き、ポインタを1進める」という処理になります。このループの開始直前はポインタは3番地にあり、その値は正(0<x'<=x)です(0になっていれば外側のループを抜けるため)。 そのため、まずx'から1を引き、ポインタは4番地に移動します。4番地の値y'が0ならそこでループが終了し、そうでないなら1を引いて5番地に進みます。

ここで、ループ終了時のアドレスがずれているのがポイントで、その後の+の足す先がずれます。これによりループ中で4番地の値y'が0になったかどうかを検出することが可能になります。 単純なBrainf*ckプログラミングでは、ループ内でポインタが徐々に移動させるとループ終了時にポインタの指す先がずれて、この後のプログラムの実行が大変になるので、そのようなコーディングは避けられがちですが、こういう場面では非常に役に立ちます。 その後、[<]の直前ではポインタは1番地または2番地を指しており、1,2番地が1で0番地が0なので[<]の直後ではポインタはどちらの場合でも0番地になり、分岐していたアドレスが統一されます。 これにより外側のループの中身の終了時に3番地にいることが保証され、0<x'<=xの間ループを回すことが可能になります。

ということで、任意の値yが範囲0<=y<xにあるかどうかを判定することができました。これを任意の範囲a<=y<bにしたいときは、式変形をして0<=(y-a)<(b-a)、つまりyからaをひき、かつx=b-aとすればよいです。

bignum環境における0初期化

もし仮にyがa<=y<bを満たすなら、2番目の方法の通り、y-aは非負なので、[-]によって0初期化できます。しかし、bignum環境では値の範囲がわからないので予めa,bを決めてしまうと、もし範囲内になかったときにどうしようもなくなってしまいます。

そこで、次のように考えます。a,bを決め打つのではなく、a_0<=y<b_0, a_1<=y<b_1, a_2<=y<b_2, ...のような条件式を無限に作り、もしこれを満たすa_n,b_nがあればy-anに対して[-]をすれば0初期化できます。 このようなnが常にするためには、a_0>a_1>a_2>..., b_0<b_1<b_2<...かつa_nは負の無限大に発散し、b_nは正の無限大に発散すれば良いです*3

Brainf*ckでこのような列を作る方法として簡単な方法として、値に1を引く/足す、あるいは定数倍するという方法があります。1回の比較にO(b-a)かかることを考えると、毎回定数倍してa_n, b_nを指数的に変化させる方が良いでしょう。

これを踏まえた実装は次のとおりです。4番地を0初期化したいとします。

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

1回ループを実行するとyがy-a-(b-a)=y-bに変化しますが、aやbを毎回4倍しているので、判定範囲は正と負の両方に単調増大し、結果的にyがどんな値でも0初期化が可能です。また、yが0になった瞬間にループを抜けられるような作りになっています。

ムーブやコピーもこのテクニックを応用することで可能です。ぜひ考えてみてください。

非負整数ペアによる整数表現

ここまで符号も範囲もわからない数を相手になんとかプログラムする方法を扱ってきましたが、整数を扱う方法は直接セルに値を格納するだけではありません。 ここでは非負整数のペア(二つ組)によって整数を扱う方法を紹介します。

具体的には、非負整数のペア(a, b)は整数a-bを表すことにします。このようにすることによって、整数演算を非負整数の演算に帰着することができます。

  • 足し算: (a, b) + (c, d) = (a+c, b+d)
  • 引き算: (a, b) - (c, d) = (a+d, b+c)
  • 掛け算: (a, b) * (c, d) = (ac+bd, ad+bc)
  • 等号比較: (a, b) = (c, d) ⇔ a+d = b+c
  • 大小比較: (a, b) < (c, d) ⇔ a+d < b+c
  • 割り算: 上5つの演算を組みあわせることによって実現可能 ここで、a,b,c,d同士の演算として足し算と掛け算しか出てきていないことに着目すると、(オーバーフローがなければ)これらの計算によってペアの中身が負になることはなく、非負整数で演算が閉じている、つまりちゃんと整数演算を非負整数の演算に帰着できていることがわかります。 非負整数同士の演算はBrainf*ck界でもよく知られているように、そんなに大変ではないので、だいぶ楽になると思います。

この方法により負の数を登場させなければ、符号なし環境のように単純なコードでプログラミングすることができます。

ただし、足し算と掛け算しか出てこないため、演算のたびに数値はどんどん大きくなります。したがって、オーバーフローのある環境では演算を繰り返すうちに(たとえ真の値a-bの絶対値が小さくても)オーバーフローが起こる可能性があります。これは、オーバーフローする前にaとbの大小比較を行い、a>=bなら(a-b, 0)、a<bなら(0, b-a)と"標準化"することで回避できます(そのぶんコードは増えますが、生の整数を扱うよりは楽ではないでしょうか)。

このへんはコード長やメモリ消費量、プログラミングのしやすさなどを見極めながら適宜選択していくことになるでしょう。

Q: bignum環境って見たことないんだけど

A: 私がさっき作った

github.com

ゆっくりしていってね

まとめ

  • Brainf*ckの処理系には非互換性がある
  • 特にオーバーフローまわりはいろいろある
  • それにより0初期化・ムーブ・コピーといった基本操作に困難が発生する場合がある
  • ちょっとしたテクニックで対策は可能
  • 整数を直接扱わず、非負整数操作に帰着することも可能
  • bignum環境を作ったので遊んでみてね!

*1:バイナリ入力でEOFが0あるいは符号なしで255だと普通のデータと区別付かなくて困りますが

*2:runtime errorになったり非現実的な時間がかかったりする

*3:a_n, b_nが整数列なので発散することは単調減少/増大列であることから従います

メタプログラミング可能なBrainf*ck派生言語BFmeta 【Brainf*ck Advent Calendar 2019 3日目】

この記事はBrainf*ck Advent Calendar 2019 3日目の記事です。

adventar.org

2日目はみみねこさんによる

mmnkblog.hatenablog.com

でした。4日目はmatsu7874さんによる「RustでBrainfuckインタプリタを実装した話を書けるだろうか?」の予定です。

今回はBrainf*ckの素直な派生言語で、かつメタプログラミングが可能な自作言語、BFmetaの紹介をします。

Brainf*ck派生言語の惨状

Brainf*ckは言語仕様が単純で、コンパイラインタプリタが作りやすいという特徴があります。 そのため、巷にはBrainf*ckの仕様をちょっといじった派生言語がいっぱいあります。

特に多いのが8種類の命令を別の文字列に置き換えただけの派生言語で、Ook!ジョジョ言語などがあります。 しかし、これらの言語は単なる文字列の置き換えに過ぎないため、ソースコードの見栄えが異なる以上の違いはなく、プログラミングする上ではあまり面白くないです。

ほかにも、命令の追加でプログラミングの難易度を下げた言語もあり、ビット演算命令を追加するなどしたBrainCrashが代表的な例です。 しかし、普通に命令を追加しただけでは多少プログラミングが簡単になるだけであまり面白くありません。 また、命令数を増やした分Brainf*ckのシンプルさから来る美しさが失われてしまいます。

かくして、ほとんどのBrainf*ck派生言語はプログラミング言語としてはちっともおもしろくないわけで、その惨状にひどくうなされた私は、夜しか眠れない日々が続きました。

なんとかBrainf*ckの美しさを継承しつつ、本質的な差異をもつ言語が作れないか考えた結果、ついに生み出されたのが、Brainf*ckでメタプログラミング*1を可能にする派生言語、BFmetaです。

BFmeta言語仕様

命令数はBrainf*ckと同じ8種類です。(プログラムの停止を表すヌル文字を9種類目と見ることもできるでしょう) しかし、Brainf*ckとBFmetaの最も大きな違いはプログラム空間とデータ空間が統合されていることです。これにより柔軟なメタプログラミングが可能になります。

まず、8bit(1Byte)*2符号なし整数*3の双方向に無限長*4の配列が用意され*5、0番地からプログラムのソースコードが順に格納され、配列のそれ以外の領域は0で初期化される。 データポインタとプログラムポインタという二つのポインタがあり、どちらも最初は0番地を指している。

命令の意味は次の通り、オリジナルのBrainf*ckとほとんど変更されていません。 プログラムポインタは毎ステップの最後に1進められ、プログラムポインタの指す値が次の9種類の文字のいずれかのASCIIコードに等しい場合、それに対応する処理が行われます。 それ以外の場合、何も行わず(単にプログラムポインタを1進めて)そのステップを終了します。

  • + データポインタの指す値を1増やす
  • - データポインタの指す値を1減らす
  • > データポインタの値を1増やす
  • < データポインタの値を1減らす
  • . データポインタの指す値を標準出力に出力する
  • , 標準入力から1Byte読み、データポインタの指す先に格納する
  • [ データポインタの指す値が0なら、プログラムポインタをこの[に対応する]の位置まで進める(今のプログラムポインタの位置から正方向に配列を舐めていき、[の数と]の数が等しくなったら停止)
  • ] データポインタの指す値が0以外なら、プログラムポインタをこの]に対応する[の位置まで進める(今のプログラムポインタの位置から負方向に配列を舐めていき、[の数と]の数が等しくなったら停止)
  • \0(ヌル文字) プログラムを終了する

Brainf*ckの仕様をご存じの方なら、Brainf*ckとほとんど同じ仕様であることがわかると思います。 しかしながら、実際のBFmetaはBrainf*ckよりかなり表現力に長けた*6プログラミング言語になっています。 次節ではその表現力の一部をお見せいたします。

BFmetaプログラミング

Hello World

ソースコード中に書いたデータを実行中に読むことができるので、ソースコード中に文字列を埋め込んでそれを表示するだけです。

[>]<<<<<<<<<<<<<[.>]Hello World!

一旦データの末尾まで移動した後、Hello World!の文字数分だけ戻って、そこから1文字ずつ出力しています。 ソースコードにヌル文字を許せば*7、次のように更に短く書けます。

[>]>[.>]\0Hello World!

Brainf*ck インタプリタ

標準入力から最初にヌル文字に到達するまでをソースコード、それ以降を標準入力とみなすことにします。

[>],[>,]>

まずBFmetaソースコードの末尾まで移動し、そこからBrainf*ckのソースコードを読み込み、1Byteデータポインタを進めます(これがないとBrainfckプログラムの終了時にBrainfckプログラムの配列の先頭が0でないときに誤作動してしまう)。 最初のソースコードはここまでですが、連続してさっき読み込んだBrainf*ckプログラムが格納してあり、データポインタはここからそれ以降はすべて0で初期化されているため、このままプログラムを実行し続ければ、読み込んだBrainf*ckプログラムをBrainf*ckプログラムとして実行したときの実行結果が得られます。

Brainf*ck自身でBrainf*ckインタプリタを書くと短いものでも https://arxiv.org/html/cs/0311032 これくらいありますが、それより遥かに短く書けました。

BFmetaでBFmeta自身のインタプリタを書くのはもう少し難しいです。(配列が負の方向に伸びないと仮定するなら、Brainf*ckインタプリタとほぼ同じにはなるのですが…)

Quine

空のソースコードをQuineと言い張ればBFmeta以外にもBrainf*ckやRubyでも0ByteのQuineが書けたことになりますが、それでは面白くないので、大抵は正の長さのソースコードであることが求められます。

keisukenakano.hatenablog.com

では404BytesのBrainf*ckのQuineが紹介されています。これでも十分短いのですが、BFmetaではなんと1文字のQuineが存在します。

.

まあソースコードをデータとして保持しているので、当たり前ではあります。

このソースコードには改行を含んではいけないことに注意してください。そのため、環境によってはうまく表示されないことがあります。

改行を含めたソースコードをQuineしたい場合は次のようにしてください。

[.>]

これでもBrainf*ckに比べてコード長が1/80です。

BFmeta処理系

こんなに表現力が向上したプログラミング言語、書いてみたい、実行してみたいですよね! そう思って予めインタプリタ(及びデバッガ)をRubyで書いたものがこちらになります。

github.com

実行速度があまり速くないので、今度C++かRustで速いインタプリタを書きたいと思っていますが、それはまた別の記事にしたいと思います。 そして、その速いインタプリタによって、Brainf*ckに対して本質的な計算量の改善ができる可能性についても、また別の記事にしたいと思います。乞うご期待。

*1:より正確にはリフレクション

*2:2008年になってようやく、IEC 80000-13により1Byte=8bitと定義されました

*3:オーバーフロー時にビットレベルで同じ挙動をするなら、符号付き整数でも良い

*4:初期は正の方向にのみ無限長だったが、メタプログラミングしやすくするためには、負の方向にも進めるようにしたほうが良い

*5:本当に用意する必要はなく、遅延評価をすることで有限のメモリでインタプリタを実現可能

*6:どちらもチューリング完全なので、計算可能なクラスは同一です

*7:POSIXによるテキストファイルの定義を満たさなくなってしまいますが…

「サイゼリヤで1000円あれば最大何kcal摂れるのか」を全探索で解いてみた

概要

qiita.com

この記事や後述の先行研究に触発されて、「サイゼリヤで1000円あれば最大何kcal摂れるのか」を最も単純に全探索で解いてみました。

先行研究

先人たちがいろいろな方法で解決を試みています。

qiita.com

qiita.com

qiita.com

qiita.com

qiita.com

qiita.com

qiita.com

anqou.net

実装

あらかじめ実装したものがこちらになります。

github.com

メニューデータは

github.com

にあるmenu.csvをダウンロードしてきました(make時に自動でダウンロードされます)

実装の注意点としては、探索の途中で合計金額があらかじめ指定した金額(1000円)を超えるような組み合わせは調べないようにしています。*1

実際に計算してみます。

$ ./solve 1000
Loading menu...
Solving...
Solved!
ラージライス: 219 yen, 454 kcal
アーリオ・オーリオ(Wサイズ): 574 yen, 1120 kcal
ポテトのグリル: 199 yen, 366 kcal
Price: 992 yen
Calorie: 1940 kcal

先行研究の結果と一致しているので正しく計算できているようです。

私の手元のPCでは0.4秒弱で計算が終わりました。全探索しても大したことなかったですね。

つまり数々のアルゴリズムはすべて無駄だったわけです。

…というわけではなく、この方法だと上限金額を大きくするとあっという間に計算時間が爆発します。

試しに1500円で計算させたところ、30秒弱かかりました。1000円から1700円程度までの実行時間を元に予測すると、おおよそ指数的に計算時間が増えて、2000円だと30分程度、3000円だと100日程度かかってしまう計算になります。

手法によっては10000円でも現実的な時間で解くことができているので、サイゼリヤで豪遊したい場合はアルゴリズムを学ぶことが必須なことがわかります。

感想

もっと計算時間がかかるかと思っていたので拍子抜けしています。本当はGPGPUで殴って楽しい高速化ライフ!という記事にしたかったのですが…

*1:この工夫を入れないと2115通り調べることになり計算が終わりません、合法な組み合わせすべてを試すので全探索と主張することは許して…