K.Maebashi's BBS

お久しぶりです、マスタングです。もし分かれば教えて欲しいです。 最近Pythonを覚えて、Code Golf(http://codegolf.com/) というコンペにはまっているのですが、Brainfuck問題というのがあり、(ぱ)さんのソースを参考にさせて頂いたのですが、最後の問題が４秒以内という制限にTime outでパスしません。恐らくあと1秒くらい短縮しないとダメみたいです。 ネックは、入力の1文字1文字をループで回しているところだと思うのですが、3百万回のループが問題になっていそうです。スクリプトはループに弱いので。 何か一般的に早くアウトプットを得る方法はあるのですか？とりあえず、'++++'などを'+4'のようにすればループ回数が劇的に減るかなと思っているのですが、まだ試していません。うまい文字列変換が思いつかないので。他に何かうまい方法ありますか？ あと(ぱ)さんはスクリプトは勉強とかされていますか？

Code Golf自体は以前「Matzにっき」からリンクを辿って、ページの構成が わかりにくいのもあってちょっと眺めただけでしたが。 >最近Pythonを覚えて、Code Golf(http://codegolf.com/) >というコンペにはまっているのですが、Brainfuck問題というのがあり、(ぱ)さんのソースを参考にさせて頂いたのですが、最後の問題が４秒以内という制限にTime outでパスしません。恐らくあと1秒くらい短縮しないとダメみたいです。 ええと、Brainfuck問題というのは http://codegolf.com/brainfuck ここのことで、「最後の問題」というのは、このページの一番下のところにある Rot-13の問題のことですか? WikipediaのRot-13のページ： http://ja.wikipedia.org/wiki/ROT13 で、課題は、 ・マスタングさんがPythonで書いたBrainfuckの処理系に、 ・課題のページで与えられているBrainfuckのコードを食わせて、 ・正しい解答が、4秒以内に得られること ですよね? (「4秒以内」という制限がどこに書いてあるのか、見つけられていませんが) >ネックは、入力の1文字1文字をループで回しているところだと思うのですが、3百万回のループが問題になっていそうです。スクリプトはループに弱いので。 うちの処理系をベースにしたのであれば、実行部分は、アルゴリズム的に小手先で 最適化できる余地はあんまりないのではないでしょうか(Brainfuck処理系には、 「]」が来たとき実行時に「[」を検索しているようなものもありますが、うちの 処理系はそのへんは読み込み時に済ませていますし)。 Pythonの実装に依存するチューニングの余地はあるかもしれません。読み込んだ Brainfuckプログラムをどのような内部形式で保持するか、とか。 >何か一般的に早くアウトプットを得る方法はあるのですか？とりあえず、'++++'などを'+4'のようにすればループ回数が劇的に減るかなと思っているのですが、まだ試していません。うまい文字列変換が思いつかないので。 5秒を4秒にする程度のことであれば、「++++」を「+4」のようなひとつのコードに するというアイディアで十分かとは思いますが、それをすべきタイミングは Brainfuckソースを読み込んで内部形式に変換するところでしょうから、 「文字列変換」ではないですよね。 >あと(ぱ)さんはスクリプトは勉強とかされていますか？ (「スクリプト」が何なのかが不明ですが)いろいろな言語の本やら解説ページやら 読んではいますが、簡単なチュートリアルの例題とかではなく、実際に日頃から 自分の問題を解くために使っていないと、「身に付く」ことにはならないようですね。

ご回答ありがとうございます。 >Code Golf自体は以前「Matzにっき」からリンクを辿って、ページの構成が >わかりにくいのもあってちょっと眺めただけでしたが。 ルールがどこに明記されているのか分かりにくいのは私も感じました。 >ええと、Brainfuck問題というのは > > ... > >で、課題は、 >・マスタングさんがPythonで書いたBrainfuckの処理系に、 >・課題のページで与えられているBrainfuckのコードを食わせて、 >・正しい解答が、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しておくことにしました。ありがとうございます。

すいません(汗)。先ほどの返信で、 >さすがに(ぱ)も手を出しているのかなと思いました。 「(ぱ)さんも」と書こうとして、「(ぱ)も」と書いてしまいました…。大変失礼致しました…<_O_>

>>それをすべきタイミングは >>Brainfuckソースを読み込んで内部形式に変換するところでしょうから、 >>「文字列変換」ではないですよね。 > >リスト(内部形式)に変換してから別のリスト(内部形式)に変換しても >良いかもしれません。 うーん、私が想定していたのは、内部形式をふたつ作るのではなく、 「読み込んで内部形式に変換するところ」でまとめて変換する、というものでした。 内部形式をふたつ作ってもよいでしょうが、ストロークを少なくするという code golfの趣旨に反するような気がします。 >Perl、PHP、Ruby、Pythonなどを想定していました。 Perlはたまに使いますがたまにしか使わないので身に付かず、 PHPはここの掲示板を作った程度、 Rubyはちょこちょこ見ては試しにプログラムを動かしたりはしてますが、 Rubyのソースを書くのに費やした時間よりRubyの実装のソースを読んだ時間の方が 長いくらい、 PythonはRubyについてよりも浅学ですねえ。 「Rubyソースコード完全解説」をWebで読んじゃって本を購入しなかったので、 罪滅ぼしに「ふつうのHaskellプログラミング」を読んでたり。

>うーん、私が想定していたのは、内部形式をふたつ作るのではなく、 >「読み込んで内部形式に変換するところ」でまとめて変換する、というものでした。 >内部形式をふたつ作ってもよいでしょうが、ストロークを少なくするという >code golfの趣旨に反するような気がします。 ここでおっしゃっている内部形式が私の考えているものとずれているかもしれないですが、例えば、入力(文字列)を内部形式(メモリ上の変数)、例えば、リストなどに変換するのは、Pythonでは、sが入力文字列だとすると、list(s)とするだけですし、forなどに文字列(シーケンス)を直接渡しても、1文字ずつ処理してくれるので文字列が内部形式としても良いですし、どのタイミングで変換するかは問題ではないように思えますがどうでしょう？ 文字列を1文字ずつ処理するのは、例えば、以下のような感じ。 >>> s = 'test' >>> for c in s: ... print c, ... t e s t >Perlはたまに使いますがたまにしか使わないので身に付かず、 >PHPはここの掲示板を作った程度、 >Rubyはちょこちょこ見ては試しにプログラムを動かしたりはしてますが、 >Rubyのソースを書くのに費やした時間よりRubyの実装のソースを読んだ時間の方が >長いくらい、 >PythonはRubyについてよりも浅学ですねえ。 なるほどです。しかし、crowbarみたいなスクリプト言語を作れるというのはすごいと思います。PythonがRubyよりも浅学というのはPythonファンの私としては残念です。 >「Rubyソースコード完全解説」をWebで読んじゃって本を購入しなかったので、 >罪滅ぼしに「ふつうのHaskellプログラミング」を読んでたり。 私も「ふつける」は購入しましたが、最近、MYCOMから出た「入門Common Lisp」という本も買ってしまいました。最近、(ぱ)さんが本を出さないのは残念です。何か書く予定があったら教えてください。