[891] Re:Brainfuck
投稿者:マスタング
2007/02/20 02:13:25
ご回答ありがとうございます。
>Code Golf自体は以前「Matzにっき」からリンクを辿って、ページの構成が
>わかりにくいのもあってちょっと眺めただけでしたが。
ルールがどこに明記されているのか分かりにくいのは私も感じました。
>ええと、Brainfuck問題というのは
>
> ...
>
>で、課題は、
>・マスタングさんがPythonで書いたBrainfuckの処理系に、
>・課題のページで与えられているBrainfuckのコードを食わせて、
>・正しい解答が、4秒以内に得られること
>
>ですよね? (「4秒以内」という制限がどこに書いてあるのか、見つけられていませんが)
その通りです。4秒以内というのは問題によってたまに書いてるのですが、Code Golfでのルールみたいです。
>うちの処理系をベースにしたのであれば、実行部分は、アルゴリズム的に小手先で
>最適化できる余地はあんまりないのではないでしょうか(Brainfuck処理系には、
>「]」が来たとき実行時に「[」を検索しているようなものもありますが、うちの
>処理系はそのへんは読み込み時に済ませていますし)。
>Pythonの実装に依存するチューニングの余地はあるかもしれません。読み込んだ
>Brainfuckプログラムをどのような内部形式で保持するか、とか。
Pythonの実装に依存するチューニングは確かにありそうですが、残念ながら思いつきません。内部形式もリストを使用しているのですが、dict(辞書)も値として式しか書けないので使えなさそうですし他には分かっていません。
>5秒を4秒にする程度のことであれば、「++++」を「+4」のようなひとつのコードに
>するというアイディアで十分かとは思いますが、それをすべきタイミングは
>Brainfuckソースを読み込んで内部形式に変換するところでしょうから、
>「文字列変換」ではないですよね。
6秒を4秒かもしれません。文字列変換というのは、例えば、'>+++++[<+++]<.'という入力(文字列)が与えられたときに、'>+5[<+3]<.'という文字列に変換してからリスト(内部形式)に変換することを想定していました。リスト(内部形式)に変換してから別のリスト(内部形式)に変換しても良いかもしれません。
文字列変換を考えていたのは、正規表現で簡単にできないかなと考えていました。
>(「スクリプト」が何なのかが不明ですが)いろいろな言語の本やら解説ページやら
>読んではいますが、簡単なチュートリアルの例題とかではなく、実際に日頃から
>自分の問題を解くために使っていないと、「身に付く」ことにはならないようですね。
スクリプトは、最近、LL言語と言われているもの、例えば、Perl、PHP、Ruby、Pythonなどを想定していました。普段使ってないと身に付くことにならないというのは同感です。私もC++やJavaは本読んでいただけなので全く身についていません。
Ruby、Pythonは世間で今流行っているというイメージがあったので、さすがに(ぱ)も手を出しているのかなと思いました。Haskellとか関数型言語などを勉強しているのかなとか。
悩んでいても進まないのでとりあえず、Brainfuck問題はPendingしておくことにしました。ありがとうございます。