Brainfuckという難解言語で文字列を表示するコードを作成するプログラムを書く

{{{{Brainfuckという難解言語}で文字列を表示する}コード}を作成する}プログラムを書く。


Brainfuckを導入してずっと放置していたので、流石になにか触ろうと思った。が、書く気力が起きないような文法なので、別言語のプログラムでBrainfuckコードを生成しましょう、という記事です。


Brainfuckってどういう言語なの?という話は別サイトを参照してください
(詳しく知らなくてもこの記事は理解できると思います)。

ちなみに僕は記事執筆時点でWikipediaに載っている情報程度しか知識が無いです。
基本的なテクも知らないので、識者からすれば突っ込み所が多いかと思います。


前提


Brainfuckの各命令は次のC言語に対応します。
>p++;
<p--;
+(*p)++;
-(*p)--;
.putchar(*p);
,*p = getchar();
[while(*p) {
]}


素直に


まずはRubyで素直に書いてみます。

gets.chomp.bytes.inject(0){|s,e| print "#{s<e ? '+'*(e-s) : '-'*(s-e)}." ; s=e}

1行で書けた。
array.inject(0){|s,e| proc}というのは、「s=0で初期化し、eにarrayの各要素を入れながらループする」。

例えば、このコードに標準入力として「HelloWorld」を与えると、
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++.+++++++..+++.------------------------.++++++++++++++++++++++++.+++.------.--------.

を得る。これをBrainfuckのインタプリタに渡すと、
HelloWorld

と表示してくれました。めでたし。





しかしWikipediaのHelloWorldはもっと短い!


厳密にはWikipediaに掲載されているコードは「Hello, world!」ですが、上で作成したコードと比較すると明らかに短い。

括弧で括られている部分にループが組み込まれています。ループを使って、+の記述を減らそうというテクですね。


例えば、
*p=70 ;

を次のように変形していく。
*p=7*10 ;

*p1=7 ; while(*p1){ *p+=10 ; *p1--; }

p++ ; *p=7 ; while(*p){ p--; *p+=10 ; p++ ; (*p)-- } p-- ;


初めは「.」が70個なので70文字でしたが、「'p++'+'*p=7'+'{'+'p--'+'*p=10'+'p++'+'*p++'+'}'+'p--'」→「1+7+1+1+10+1+1+1+1」なので、
24文字になりました。


要は、この部分の作業を機械的に実装したいです。

最適なパラメータの組み合わせは?


上で書いたことを一般化すると、
  • 変数*pに%$n$%を加算したい。Brainfuckで素朴に書くと、%$n$%文字必要である。
  • %$n = p \times q + r$%ただし%$p,q,r \in 非負整数$%とする。このとき、%$7 + p + q + r$%文字で済む。

パラメータが3つありますが、%$p$%が決まれば最適な%$q$%と%$r$%が定まるので、%$O(n)$%で全探索できます。


最適なbrainfuckコードの長さと%$p$%,%$q$%,%$r$%、得られるコードを求めるrubyを示します。
n = gets.to_i

min = [4*n]
1.upto(n){|p_|
q_ = n/p_
r_ = n%p_

k = 6 + p_+q_+r_
if k<min[0]
min = [k,p_,q_,r_]
end
}
p min

k,p_,q_,r_ = min
puts ">#{'+'*p_}[<#{'+'*q_}>-]<#{'+'*r_}"
え?もっと高速なプログラムが組めるって?%$n \le 255$%だから十分でしょう。


このプログラムに、標準入力79を与えると、
[26, 6, 13, 1]
>++++++[<+++++++++++++>-]<+
「最短は26文字、p=6,q=13,r=1で、そのコードは次の通り」という意味。

得られたコードに'.'を加えて、実行すると、'O'と出力する。


これを用いて、素直に書いた「文字列を表示するコードを出力する」プログラムを書き直すプログラムを書いた。


実行結果。
>++++++++[<+++++++++>-]<.>++++[<+++++++>-]<+.+++++++..+++.>++++[<------>-]<.>++++[<++++++>-]<.+++.------.--------.

短くなりました。

コードゴルフには全く使えませんが、マシになったような気がします。

スポンサーサイト

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

tag : brainfuck

コメントの投稿

非公開コメント

プロフィール

舞葉(ぶよう)

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

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

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

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

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

この人とブロともになる

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

[サブジャンルランキング]
プログラミング
265位
アクセスランキングを見る>>