最短経路と粘菌とプログラム
最短経路を出力するプログラムを３時間で書けとか言う入社試験があるそうだ。
ちょっと問題をみてやってみたが、こんなの３時間どころか、一晩やっても解けねぇわ。
人材獲得作戦・４ 試験問題ほか
http://okajima.air-nifty.com/b/2010/01/post-abc6.html
●入出力はテキストデータを用いる
●一度に動けるのは上下左右のみ。斜めは不可
●最短経路が複数あるときはそのうちの１つが出力されていればOK
●入力データのバリデーション（長方形になっているか、スタート・ゴールが１つずつあるかどうか、等）は不要
●制限時間は３時間
●プログラム言語・OSは自由
３時間というと、問題をみて解こうかなって思ってから晩御飯食べてる間に終了した。
まあ、その後にやってみたんだけど、、、思ったように動かない、動かない。
何が悪いのかわからないから寝ちゃった。
おきてから仕事して合間に続き書いてみたんだけど、こりゃあと何時間かやっても難しそうだなとおもったのでギブアップ。
俺のレベルは０！ あ、３時間の時点で時間が終わってるので、判定不能か。さらに残念だなこりゃ。
つくりかけだけど。こんな感じでつくってみた。
粘菌をつくって粘菌くんにといてもらおうと思ったんだけどね、、粘菌くんの挙動を再現するの難しい…。
基本的に粘菌は脳がないので、局所的な判断が全体の合理的な判断となるように組み上げたかったんだけど。。。
↓フラッシュだから動かせるよ！
※使い方：
MAPを書き換えてボタンを押してね。
スライドバーを動かすと餌場からもらえる餌の量が増えて粘菌が増えやすくなるよ。
SもGも複数おけますが、粘菌が置かれるのはSの最後のやつです。
例外処理とか終了処理とか書いてないので、MAP再読み込みしたいときとかは画面をリロードとかしてね。
粘菌くんはぜんぶ個別に挙動するおぶじぇくとなので多分でかいマップとか読み込ませると死にます。ブラウザ的な意味で。
基本的なロジックとしては下記のとおり。
・S、Gの地点から粘菌はエサを得ることができる
・粘菌は活動するのにエネルギーを消費する
・隣り合ったマスに余剰な栄養をわける
・隣り合ったマスに粘菌がいなければ増殖する
粘菌についてご存知ない方も結構いたのでフォロー。
粘菌は最近イグ・ノーベル賞もとったなにかです。
栄えある？「イグ・ノーベル賞」受賞 「迷路を解く粘菌」って？！ 中垣俊之・北大准教授ら研究
http://www.hokkaido-np.co.jp/cont/kawaraban/39680.html
粘菌が迷路を最短ルートで解く能力があることを世界で初めて発見
http://www.riken.go.jp/r-world/info/release/press/2000/000926/index.html
これでゴールにたどり着いたところで栄養を絞れば粘菌の最短経路を再現できるかなみたいに思ったんだけど、まだロジックが足りないみたい。もうちょっと利己的な排他性とか境界面の自己認識とかも組み込まないと最短経路選択の経路再現はできないのかも。
アポトーシス(枯れる)関係のロジックがまだ不十分なのでそこらへんをもうちょっとやらないとダメかな。
ここらへん再現できれば面白いんだけどなぁ…。
最初３時間もあればできるんじゃないだろうかとか思ってたんだけど、Flexの多次元配列の書き方がわからないとかググってるところでこりゃ無理だと悟ったよ。
無理だってわかるところまでだったら俺も２５分だ！
・・・なんにも使えないだろうけど、ソースも上げておくよ。Flexの勉強したい人はどうぞ。
http://kuippa.s188.xrea.com/jinsama/nenkin.lzh
Flex、さっぱり意味わからん。ActionScriptの一種なんだけど、自分がイメージして書いた内容と挙動がここまでずれる言語も珍しい。もう泣きたくなるね。粘菌くん大増殖でなんど泣いたか。
全マップ栄養マップとかにかえて粘菌が暴走しながら食い尽くしていく様は恐ろしいよ。
Gをあちこちに配置してから粘菌読み込めば再現できるかもね。
それにしても、投機家らしい問題ですねぇ…。ある意味で合理的。。
業務に沿ってれば面白い就職試験なのではないでしょうか。
入社する側の立場だったらどうだろう。
「君ならこの仕事は３時間もあれば十分だとおもうから今日中にやっておいて！」
なんて仕事の振られかたをするのかと思うとびびってしまいますね。
一週間の仕事の生産性とか突き詰められそうだ。
「この問題は確かに２５分で終わるかもしれませんが、十数年と２５分掛かってるんです！」
と戯言いったところで・・・。求められているのが技能効率っぽそうだし。
ドライなわりきりがいい人にはいい職場なのかもしれませんね。
おれが問題を出すなら・・・、
Q.粘菌が最短経路をとるようになるには上記以外にどのようなロジックが必要だとおもうか、その理由も答えなさい。
みたいなロジック問題かもしれない。
コーディングによる組み上げ力を優先するか、問題解決力を優先するかの違いかな。
組み上げ力をみるにしては、ちょっと問題が偏ってるかなとも思わなくも無い。
投資関係のデータをうりうりするのに最適化は避けて通れない道なのかな・・・？
俺にはよくわからないけど。
つか、この人のブログみたら変な汗かいたんだけども。。。
( ´ﾉ日`) ｽﾞｽﾞｽﾞ。みなかったことにしよう。
