スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Brainfuckのメモリに複数の数値をスタックする

ブロク編集のリソースを某プロコンに費やしているので記事を全然書いていなかったのですが、
1ヶ月制限広告が出そうなので何か書く。

ちょっと前の記事の通り、brainfuckについてはあまり良く知らないです。


省略のため、この記事では次のような表現をします。
  • 初期ポインタ位置をメモリ0番地とする。つまり、初期状態から「>」でメモリ1番地に移動する。
    メモリ%$i$%番地を%$M_i$%と表記する。


brainfuckで、次のようなことをしたいです。

%$n$%個の要素から成る数列%$a_1,a_2,...,a_n$%が与えられる。各要素の値は1byteに収まる。
各数列の要素%$a_i$%を%$M_i$%にセットしたい。%$M_0$%は作業領域として使用しても良い。


いや、もう少し難しくしたかったんですが。



基本形


初めに、%$a=(4,6,11)$%としたときのbrainfuckを
+++[>+>++>++++<<<-]>+>>-
という感じで。前半で1つのループを回し、後半で少しだけ加減算するこのようなコードを見ていきます。

このケースでは、
1つめの4を%$3 \times 1 + 1$%
2つめの6を%$3 \times 2 + 0$%
2つめの11を%$3 \times 4 - 1$%
と計算しています。


この基本形では、1とか255とかをセットせよ、という入力になると全然最適化できないのですが、
その部分については今日はやらない。


定式化


変数%$r,p_1,p_2,...,p_n,q_1,q_2,...,q_n$%を定義します。すべて整数です。
%$r$%はループを回す回数。
%$p_i$%はループ内部で%$M_i$%に加算する値。
%$q_i$%はループ外で%$M_i$%に加減算する値。

定義された変数からbrainfuckのコードを書いたとき、そのコードの長さ%$L$%は、
%$L = r + 1 + n \times 2 + \sum p_i + 2 + n + \sum |q_i|$%


まとめると、次のような整数計画問題に持っていくことが出来ます。

最小化
%$r + \sum p_i + \sum |q_i|$%

条件(それぞれの%$i$%について。)
%$a_i = r \times p_i + q_i$%
%$1 \le r \le 255$%
%$0 \le p_i \le 255$%
%$-255 \le q_i \le 255$%
%$0 \le r \times p_i \le 255$%

ソルバーがあるならば、それを使っても楽しいかも。


導出


今回もかなり手抜き。線形計画法は忘れてください。


まず%$r$%を固定します。
すると、%$a_i = r \times p_i + q_i$% より、固定した%$r$%での最適な%$p_i$%と%$q_i$%を定数時間で求めることが出来ます。

なぜならば、%$|q_i|$%を小さくすれば良いので、%$\lfloor a_i/r \rfloor$%と%$\lceil a_i/r \rceil$%の2つを%$p_i$%の候補とし、式に代入して%$q_i$%を求めて、%$|q_i|$%が小さい方を答えとすれば良いです。


%$r$%は所詮多くても255パターンなので、全探索して最小解を求めます。
これで最適な解を求めることができます。


プログラミング


実際に実行して結果を確認するには、メモリの値を出力する必要があるのですが、
入力を文字コードにすることで、putcharして確認できるようにします。


与える数列%$a$%はこちら。
72 101 108 108 111 44 87 111 114 108 100 46


コメントは無いけれど、上で示した手順を実装。

実装していない制約があるとか言わないように。


出力結果。
++++++++++++++++++++++[>+++>+++++>+++++>+++++>+++++>++>++++>+++++>+++++>+++++>+++++>++<<<<<<<<<<<<-]>++++++.>---------.>--.>--.>+.>.>-.>+.>++++.>--.>----------.>++.


Brainfuckに渡して実行。
Hello,World.


スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

ブログ移転のお知らせ
ブログをshonen.hateblo.jpに移転します. 新規の記事はこちらに投稿します.
プロフィール

舞葉(ぶよう)

Author:舞葉(ぶよう)
github.io
はてなブログ(競プロ)

古い記事のソースコードは色分けしていないので、高機能テキストエディタに貼り付けたほうが見やすいかも。

検索フォーム
このブログについて
自分がつまづいた話題、なんとなく書きたいと思ったこと、ググったけど殆ど資料なかったぞオイ な話等をアップする予定。通りすがりでも、参考になっていただければと。プログラムの例外入力、メモリリークは責任負いません。投稿された記事は修正・削除する場合があります。
カテゴリ
タグ

HSP3アルゴリズムとデータ構造c++RubyJavaUnity画像解析C機械学習C#LinuxcodeIQKinectMinecraftTonyuSystemraspberrypiPythonHTML5音声制御Simulinkruby俺ルール通信制御Javascriptシミュレーション

counter-shinobi
固定記事
最新記事
最新コメント
月別アーカイブ
ブロとも申請フォーム

この人とブロともになる

アクセスランキング
[ジャンルランキング]
コンピュータ
635位
アクセスランキングを見る>>

[サブジャンルランキング]
プログラミング
94位
アクセスランキングを見る>>
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。