ange1のブログスマートフォン用の表示で見るange1のブログこの広告は、90日以上更新していないブログに表示しています。2016、9日目の記事です。はじめに久しぶりに、以前のBrainf**k講座(最終の第8回はこちら)の番外編です。golfが一部?盛り上がりを見せたこともあり、今回は趣向を変えて、コードを縮めていく過程を紹介したいと思います。次のような問題でした。標準入力から、4つのプログラム言語名がカンマ区切りで、最後に改行も込みで入力される。入力に従い、次の2行からなる出力を行う。)例えば、ruby,java_script,python,cという入力に対しては、RJPCとRubyJavaScriptPythonCを出力します。Brainf**k以外の言語であれば、例えば次のPerl(51)が解となります。>>>+[-[.,+]>>>>>+]全体的な流れとしては、全部の文字を読んで保存後、先頭に戻って文字列を出力する、というものになります。カンマ・アンダースコアだけは次のように扱いが変わります。)そのため、割り算により文字種を判別し、かつ1文字前の情報を残しておく必要があります。その際、元の文字を残しておかないと後で出力できませんから、アルゴリズム集にあるdivmodの最初のバージョンを使います。逆に言うと、文字コード95のアンダースコアと97の小文字aが近接していることから32以外では難しい所です。ダミーで入れておくことで吸収します。上の実装は綺麗ですが、どうしても見逃せない点があります。それは、割り算に使う32、大文字化のために引く32を個別に作っている点です。それぞれ20文字程度消費しますから結構馬鹿になりません。そこで、共通で1度だけ作ってどちらにも使おうとするわけですが、少し困ったことが起ります。それは、割り算と大文字化を同時に行えないということです。ラッキーなことに、カンマやアンダースコアは2連続しないことが問題文から読み取れますから、大文字化の時には文字種の判別が要らない、つまり割り算が省けます。いうことで、次の135文字の実装が出来ます。橋掛けした中で元非0の所だけ出力>[-[.,+]>]なお、もはや読み込む文字を等間隔には保持していないので、最後は開き直って全部スキャンします。途中の割り算で出る不要な余り等をクリアする必要がありますが、一度に大きな移動をしなくなるため、出力部分を大幅に省力化することができます。思い切って構成変更しかし、実装を考えていた当時、既に133文字が記録されていました。PPSP、BF(133)久しぶりに覗いてみたら、いい感じの問題があったので挑戦してみました。2016年11月26日ということで上の実装では叶いません。何となく無駄に思えるのが、カンマ、アンダースコアを前に戻ってクリアしているところ、ここを次の文字による上書きで兼ねられないか、という考えたのです。すると、カンマ、アンダースコアの判定は直ぐに行わなければなりません。そこで判定と大文字化を分離します。それによりできたのが次の129文字です。ずれた場合はcが上書きされる>>>,+]<<.+[<+]>[-[.,+]>]カンマ、アンダースコアの場合に位置をずらしてクリアと入力を兼ねている所もそうですが、次のループでq,cの位置が隣接するように割り算を変形しています。[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]と[->-[>+>>>]>[+[-<+>]>->>>]<<+<<<<]を見比べてみて下さい。被除数のバックアップは何も元の位置の隣でなくても良いのです。商は敢えて負にしています。次の+++で正に持っていくためです。Brainf**kの場合、システム的な制約が無ければ、入出力の時を除いて、正負どちらの値にするのも自由なのです。上で129文字版ができました。提出したのは次の125文字でした。>[+++[<<]]>>>,+]<<.+[<+]>[-.>]これは最後の出力を[-[.,+]>]から[-.>]に替えたものです。全て出力することになってしまうのですが、ideoneをバックエンドにしているCodeIQの場合NUL文字はなかったことにされるようなのです。そのことに気付いて4文字縮めることができたのでした。「短いは正義!」です。...とは言え、これ良いんだ...、という感じではありました。遅ればせながらBFで提出。2016年11月28日もっと短いコードを!しかし、その後あっさり120文字で抜き返されます。無駄は省かねばなりません!!で、実はもやもやしていたのは、32を予め作って置くところ。確かに一度で済んではいるのですが、大文字化の際に作った32を引き算で移しています。実質コピー分の無駄ができているのです。これならコピーの分の無駄は生じません。この工夫により、一気に次の118文字に縮めることができました。残っている状況と、ずらしがない状況はすぐには区別できません。いずれも右隣に非0マスが2個連なっている状態だからです。そこで、ワンクッション挟みます。qに1残りの状況であれば、マイナス1することでふるい分けられるからです。問題はカンマの場合の大文字出力ですが、if-elseの制御を行わず構わず行います。割り算をした場合残っているのはNUL文字なので、先ほどと同じく問題にならないのです。先ほどの118文字で既に大幅に縮んではいるのですが、細かく無駄があるところを縮めて115文字が最終形となりました。]>>>,+]<<.+[<+]>[-.>]一つは、割り算の余りのクリア等の処理を、カンマ・割り算の分岐にまとめてしまうことです。これにより出力の前後で往復していた2文字分が縮みます。一つは細かい所ですが、入力ループの最初の-1の省略です。これはどうせ割り算に入る直前で-1が入るからそちらで兼ねてしまおうということです。すると、32の代わりに33を作る必要があり、ここで2文字増えてしまいトントンに見えます。割り算の所で1文字縮めることができるのです。[->+[>+>>>]>[+[-<->]>->>>]<<+<<<<]が[->+[>+>>>]>[[-<->]>->>>]<<+<<<<]と、+が1文字減っています。実は、÷32が÷33に変わったことでそのままでは商の値が狂ってしまうのですが、割り算のループにおける除数の回復を手抜きすることで調整することができるのです。アンダースコア95が被除数の場合、通常であれば、95と32を比較→63と32を比較→31と32を比較と進む所、95と33を比較→62と32を比較→30と31を比較、というように、除数の所を1ずつ減らすようにして辻褄を合わせているということです。いやもう、流石にこれ以上縮めるネタは思い浮かびませんでした。これが一番短いと思います。終わりに最後まで読んで頂き有難うございます。かなりのボリュームになりましたが如何でしょうか。普段、公開される最終形だけでは見え辛い、途中でどこら辺に着目しどのような発想で縮めたかという点、参考になれば、そしてBrainf**kのgolfを楽しんで頂ければ幸いです。2016、10日目の記事です。)月別アーカイブはてなブログをはじめよう!ange1さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。