まず最初に断っておきますが,このページの筆者(mas)は
プログラミングのかなり素人です. この方向性の記事なら多分もっと適切なものを書ける人が山ほど居そう….


プログラムの利用については賛否両論あると思いますが,ルールの定まった正式なコンテスト
でもないのであくまで個々人の判断であって,使用者を責めるべきではないと考えています.
そして,かなり人間の理解を超えた解け方をする問題も(多くではないけど)存在するので,
上位を目指すならある程度のプログラムの利用は必須になってくると思います.

「パズルゲームをプログラムで解く」ことに対する価値観は色々かもしれませんが,
まぁ「プログラムを利用して問題解決する」という姿勢・能力は,色んなプログラムコンテストなどでも
評価されているようだし,個人的にはこの方向のアプローチも1つのスキルと思っています.
特にこのゲームはオンラインゲームの中でも,プログラマーが多く集っているようだし,
あまり遠慮しても仕方が無いかなと思って自分も使い始めました.
使い始めると,この方面でもある程度"実力"は存在するんじゃないかなという気もしています.


さて,私の経験上,プログラムが利用出来そうな場面としては次のようなものがあります.

第3,第4の目的は少し特別ですね.(ちなみに第3の目的ではいまのところ使ったことがないです).
第3の目的では,一番たくさん現れる2byteの文字列を探索したり,「a(X):pXq」型の関数で
圧縮効率が良いものを探索するなどの目的がありそうです.ただどういう手順で圧縮するのが
効率が良いのかよく分からないので,上手に使わないと最善にはならなさそう?
いまのところ手作業で間に合ってしまっているので使ったことはないですが,
ある程度良さそうなアルゴリズムのアイデアがあるならプログラム化しても面白いかも.
第4の目的では,数式の形は分かるけど細かい数値設定が分からない場合などに使ったことがあります.
解法のネタバレにはあまりならないと思うので具体的な問題を書きますと,例えば
soukyokusenという問題でどうしても数値調整が上手くいかずプログラムで探索した経験があります.

第1の目的では,たいていは実際にブラウザ上で動かせばいいのですが,
実行が万単位のstep数になると非常に時間がかかります.
私の環境では問題によっては最高速でも2時間とかかかりますww
実行が何十分という単位になってくると,「最後の最後」というところでの
回収が上手くいかずやり直す,なんていうのは嫌ですよね.
恐らく普通にプログラムすると,ブラウザ上での実行に比べて自作のシミュレーターの方が何千倍と速いです.
描画をしないこと,1~3変数の再帰などに照準を合わせて書けば「型判定」を必要としないことなどが
理由に上げられるのでしょうか…?全然くわしくない人が推測で書かない方がいいですね….
とにもかくにも,シミュレーターを自作しておくと,育てるのに時間がかかりそうなパターンで
「上手くいかなかったらどうしよう!」という不安に怯える必要がないのが利点ですね.
他に,「こんな感じの再帰で上手くいかないかな?」というのを10パターンほどに絞って
試したりとかいう使い方をしています.


最後はいよいよ解の探索ですね.当然byte数を指定すると,
ありうるコードは有限通りしかないので全部調べれば解が求まるはずです.
しかし,本当に全部の文字列を対象にするのはヤバいので,ある程度型を
絞ることが必須になってくると思います.
自分は「1変数の再帰」「2変数の再帰」「3変数の再帰」「繰り返し」の3種のプログラムを用意しています.

解の探索方法は,全部のパターンをそれぞれ適当なステップずつ動かして,
Clear!できるかを調べるのが普通でしょうか.もっと良い方法もあるかも.
ステップ数は,Ruleには「1000000ステップに制限されている」と書いてありますが,
全部のパターンを1000000ステップ動かすのはかなり時間がかかりますし,また実際の仕様としても
1000000ステップよりもかなり早い段階でフリーズして動かなくなってしまいます.
恐らくメモリ使用量が特定の値を超えると動かなくなるんじゃないかと….
スペック依存かどうかは知りません.
というわけで,実質1000000ステップ動かしても無意味ですね.現実的には大半の問題は
5000ステップもあれば解けますし,長めの問題でも40000ステップもあればたいてい足ります.
(例外的に70000ステップ以上でSolveしたものもありますが.)
動かすステップ数はこのあたりの数値を参考にしてみてください.

全部のパターンを例えば20000ステップずつ動かすとすると, 15byteくらいになると,自分のプログラム・PCスペックではまともな時間では探索しきれません.
何時間,何日間単位であれば探索し終えるかも?くらい.14B以下なら
割と現実的な時間で全探索できるでしょうか?

効率よく解を探索する方法として,自分が使っているアイデアを列挙しておきます.


戻る inserted by FC2 system