パズドラ問題
ちょっと前のことですが
友達がパズドラのサポートをするようなアプリを作っていたので
僕も楽しげなところだけ作らせてもらいました。
公開する気はないようなのですが
GUIまでわりとちゃんとつくっていました。
よくある大学の課題みたいなものなので
思ったよりよくできたので解き方を紹介。
まじめにやるとすごく難しくて時間がかかるので
簡単にできるところだけ作ってみた感じです。
もっとよい方法があったら意見いただけるとうれしいです。
解の可視化
なにはともあれ見えるようにします。
これはもう最終形態なので作っていく過程はないのですが
盤面を貰ってpath( 座標の配列 )を返す感じ。
乱数で盤面を作って結果を表示します。
方針
基本は木構造の探索と盤面評価
来た方向にもどらないとすると1手は3種類
最初は30種類なので
10マス動かすのに30*3^10=177万通り
枝狩りしない全数探索だとこれくらいが限界
ただ10マス動かしただけだとちょっと短すぎます。
外周2週で20マスくらいなので40マスくらい動かしたいところ。
横型探索すると枝狩りしやすいのですが
メモリを食うので縦型探索で掘っていきます。
一手を曲がらずに動かせる直線とみなして
1マス動かすごとに盤面評価して終わったら元に戻します。
ただこのやり方ではPCで10秒くらいを目安とすると
ざっくり8手の探索が限界です。
直線で進めるのが平均2.5マスとすると20マスくらい。
まだちょっと足りないのでやっぱり枝狩りは必須。
ここらで携帯に入れたところ処理時間がPCの10倍かかることが判明
1秒以内で解を出すのを目安にしました。
1手ごとに一定の深さで探索して最適解以外を全て削除。
探索のコストをO(n)に絞ります。
結果として毎回深さ6で探索して20手くらい掘ることにしました。
盤面評価
とりあえず簡単に隣り合う二つの石が自分の隣だったら加点
あとは同じ色が一箇所に集まるように
色ごとに重心を出してそこからの距離の総和が遠いと減点することにしました。
開始位置
これが重要なのですが全部の点で同じ事をやると30倍時間がかかるので
同じ色が3つ以上合ってそれが重心から遠くにあるものを動かすようにしました。
チューニング
corei7のPCに比べてexperiaの最新版は約30倍遅い。
最終的にPCで3秒くらいの探索が携帯で90秒かかりました。
探索の葉の部分と評価関数で配列の初期化を全部なくしたら
それだけで10倍くらい早くなりました。
配列をnewするとすごく遅いんですね。
雑感
携帯が高機能になったといってもやっぱりPCに比べると遅い
newはすごく遅い
市場に同じようなアプリはあるんですが
やっぱり作ってる人はすごいですね。
あと意外と人間は賢くて状況に応じた解を出すのは
すごーくめんどくさそうです。
友達がもう少しやる気になったら改良しようと思います。
中国
中国に行ってきました。
場所は合肥上海から内陸に行ったあたりです。
僕の印象は三国志で魏と呉が戦った場所で
合肥の戦いで有名な場所です。
PM2.5
やっぱり多少の影響はあるようで
微妙に曇っています。
微妙に喉というか胸が痛い気がするのは思い込みがあるのかも知れませんが
も思っていたよりひどくないようで
マスクをしている人もあまりいませんでした。
長期滞在じゃなければそれほど気にするほどでもないのかも？
どちらかというと砂っぽい感じで
きれいな車もちょっと白っぽくなっています。
これはたぶん黄砂の影響なんじゃないかなーと。
街の雰囲気
言葉よりはとにかく写真。
思っていたよりはものすごく都会。
大きな公園があったり高層ビルが立ち並んでいたり。
これが仙台や広島に比べるとかなり広いエリアで広がっています。
道も片側3車線になっていたりとかなり広くて
土地の使い方がヨーロッパよりはアメリカに近い印象。
すごく大きなマンションを何十棟も建設中で
こんなに作ってどこから人が来るのか不思議ですが
中国はちょっとバブルらしいのでそれもあるのかもしれません。
コミュニケーション
ほとんど英語が通じません。
空港でさえ飲食店の店員とかだと怪しい感じ。
市内の飲食店に至っては英語が誰にも通じません。
写真のあるメニューがないとなにも食べられない状況。
ただ日本語の漢字の意味から書いてあることはなんとなくわかります。
反日感情
間違いなくあるとは思いますが
嫌な思いはしませんでした。
滞在中の新聞でも日本との領土問題が一面になっていたり
注目度は高いはずですが
日本から来たといっても店員がみんなで協力して話を聞いてくれ
オーダーを取ることができました。
現時で打ち合わせたエンジニアも我々には気持ちよく接してくれて
みんなが悪意をむき出しにするような心配は僕の偏見だというのがよくわかりました。
支払い
現金両替必須です。
VISA MASTER JCB 全部ダメ。
中国国内カードじゃないとほとんど支払えません。
ホテルは大丈夫でしたがご飯は現金がないと危ないです。
中華料理は日本より安いけどせいぜい半分くらい。
空港とかだとあまり値差を感じません。
雑感
他国の優秀なエンジニアと議論できたのは非常に刺激になりました。
やっぱり実際に会わないとダメですね。
若い人はこちらと同じで考え方がニュートラルで
よくも悪くも伝統的なやり方から少し距離があるように感じました。
あと日本に来た海外の方を見ればよくわかりますが
こんにちは、ありがとう、YES/NO、１～１０くらいは覚えていくと
現地の人が非常に良い顔で対応してくれます。
初めて出張に行く人はお勧めです。
エンジニアと英語
自分が非常に困ったので誰かの参考になれば。
学生の方向けに。
私は英語がかなり苦手です
就職活動で初めて受けたTOEICが４５０くらい。
大学受験くらいまで
英語はどっちかっていうと文系科目だろーくらいに思ってました。
実際は全くそんなことなくて
研究室に入っていきなり読めって言われる論文は
当たり前のように全部英語。
運が悪いと（？）教科書が英語だったりします。
日本語で読んでもわからないのに
英語で読んでわかるはずがありません。
技術用語は辞書引いても意味が載ってないことが多いので
アルク先生にはすごくお世話になりました。
それでもなんとか卒業して就職したところ
仕事の相手がたまに外国人だったりします。
メールは英語。
電話がかかってきたりもします。
今なんとなーく3割くらいが英語のメールです。
ものすごく大変です。
ネイティブの人が言ってることはほとんどわかりません。
でもエンジニアの人と技術的な話は通じます。
目的が同じなので。
会議で何話してるかわからないだけじゃなくて
出張先で雑談中 私だけ冗談が聞き取れず
自分以外が笑っているなんてよくあります。
何が言いたいかっていうと
英語はやっておいた方がいいです。
必要なものは嫌でもできるようになるので
今出来なくても気にしなくていいと思いますが
できて損はないと思います。
なにより習ってきたものが使えるのはちょっと感動します。
数学とか理科っていうのは世界共通なので
あんまり日本でやる理由がないんですよね。
法律とか金融だったら日本人が日本語でやることに意味があるけど
物を作るのは世界中どこでもいいわけで
海外には日本人よりすごく給料安いけどすごく優秀な人がいっぱいいます。
今日本はある程度お金があるので周りに比べて給料も高いですが
なにもしなければ給料が一番安いところに仕事が行きます。
日本は生活コストが高いので同じ給料じゃ生きていけません。
なにか工夫して他の人に出来ないことをやらないと
日本のエンジニアは意味なくなっちゃいますよね。
逆に考えると日本がどんなに貧しくなっても
給料高い国に行って仕事ができるわけで
それはそれでいいのかもしれません。
というわけで理系の人は
必ず海外の人と仕事をすることになるので
英語をやっておくといろいろ良いことがありますよ。
海外の人と話すのも楽しいです。
FFTとフィルタリング2
内容は以前書いたものと同じですが
前回LPFだけだったのでちょっとまとめます。
条件
入力はFs=48kHz f=1kHzの矩形波
逆フーリエ変換をかけて波形の確認をします。
f0を振って波形を確認。
LPF
f0=1000のとき
緑がFFT結果
青い部分だけ残して値を0にします。
対数軸だと
これを逆変換すると
だいたい１ｋが残ってますね。
というわけでE3系列っぽく
100,220,440,1000,2200,4400,10kHzという感じで波形を出してみます
だいたいフィルターっぽくなっていますが
インパルスが全周波数を含んでいるのと同じように
矩形波もかなり高い周波数を含んでいるので
ほんとに上の方だけカットすると逆に高い周波数が見えてきます。
HPF
続いてHPF
グラフが多いので1kだけ最初に出します
緑から低周波を削除して青い部分だけ残します。
そうすると
こんな感じ。
値が極端に変化するところで正負が入れ替わって
FFT結果も極端に変化するので
これもフィルターとして使えそう。
前回画像でやったものがどう動いてたのかちょっとわかるかも？？
というわけで同様に遮断周波数を
100,220,440,1000,2200,4400,10kHzにしてみます
雑感
ほぼグラフを並べただけですが
こんな風になるようです。
これだけ見るとだからなんだって感じですが
画像にフィルタをかけた時の参考にひたすらグラフを残しました。
自然界にあまりない特性なので直感的にわからない感じがします。
これだけ見るとエッジ検出には使えそう。
IIRより確実によさそうなところは
FFTだと二次元で斜め成分も取れるっぽいので
縦横というより空間的にフィルタリングできるところな気がします。
位相ずれがないのがいいですがIIRも両側からかければ
位相ずれがないのでそこはあまり差がないように思えます。
音声のフィルタリングでは人間はあまり位相差を感じないようなので
IIRだけでフィルタリングしてそれほど違和感がないのですが
画像だと少しでもずれると非常に違和感があります。
恐らく時間的な位相ずれは感じにくい気もするので
動画などの時間軸で使う分にはまた違うのかもしれません。
だいぶ時間がたちましたが
昔全然理解せずに授業を受けていた
大学1、２年生くらいのレポートができそうです。
義務的にやらない勉強は結構楽しい。
追記
E3系列は22と47でした・・・
電気屋としてはものすごく恥ずかしいミスですが
グラフ置きなおすのがめんどいのでそのままにします。
2次元FFTとエッジ検出
どうもエッジを検出するには
逆変換して隣のピクセルと正負が反転しているところが
エッジにみなせるように思えてきた。
理論を調べるのはつまらないのであとでやるとして
といあえず実験してみます。
元画像
いつもどおりこれ。
周波数軸での操作
FFTしてこうなったものを
以下のように四隅の値を０にします。
四隅は電気屋さんっぽく言うと直流成分
低周波数を削除してあります。
中心から四隅の距離を100としたとき95以上を削除しています。
結果
逆変換したあと正負がわかるように各画素で+128します
そして隣の画素と正負が反転しているところは
その差を値とした画像にすると
こうなります。
かなり精度よく出来ている感じ。
グレーでこれならRGB別々にやったらかなりきれいに出来そう。
周波数カットの仕方
いろいろ試したり他の方の文献を読むと
周波数軸の操作は中心からの距離で丸く操作していることが多いのですが
同じ事を四角くやってみます
同じ方法でエッジをとると
ちょっとノイジー。
なんですかねこれは。
謎。
今後の課題にしましょう。
二次元FFTとフィルタリング
二次元FFTは画像を画素の行列にして
これで元にもどりそうだということは前回できたので
周波数軸で操作して遊んでみます。
元画像
例によってこれ。
LPF
中心付近が高周波なのでまずは高域を削除して低域通過フィルタをかけてみます
高周波がいなくなるのでぼかしフィルタみたいになる予定。
FFT後の状態でこうすると
こうなる
いまいちわかりにくいので
もうちょっとやってみる。
こうすると
こうなる
だいぶぼやけてきたのがわかります。
そしてこうすると
こうなる
ほとんどの情報がないにもかかわらず
意外と原型を保っています。
知識としては知っていたものの今回ちょっと実感した感じ。
HPF
今度は低域を消して高域通過フィルタにしてみます。
こうすると
こうなる
ぼんやり見えるけどほぼ何も見えません。
もうちょっとやってみます。
こうすると
こうなる
なんとなく見えてきました。
もう一回
これはこうなる
なんかちょっと違う気がする。
前IIRフィルタでエッジ検出したときは
正負が逆転したところをエッジとしていましたが
これももしかしてそうした方がいいのかもしれない。
納得いかないが結果は結果。
バグかもしれない。
画像のアップロード
いまさらながら画像を載せたいときは
編集画面に画像をドロップするんじゃないということに気づきました。
重い理由はこれだったんですね。
解決。
