Processingでライフゲームつくった。
バイトで暇だったので、Processingでライフゲームつくった。
Processingとは、
かんたんに、ちゃんとしたプログラムを作れる言語/開発環境。
メディアアーティストとかが使う印象。グラフィック描写が簡単。
つくったもの
final int SIZE_OF_CELL = 10; final int FRAME_SIZE_OF_X = 800; final int FRAME_SIZE_OF_Y = 800; int num_of_row = FRAME_SIZE_OF_Y / SIZE_OF_CELL; //gyou int num_of_col = FRAME_SIZE_OF_X / SIZE_OF_CELL; //retsu int num_of_cell = num_of_row * num_of_col; Cell[][] cells = new Cell[num_of_row][num_of_col]; boolean game_state = false; class Point{ int row, col; Point(int my_row, int my_col){ row = my_row; col = my_col; } int getRow(){ return row; } int getCol(){ return col; } } class Cell{ int x, y; boolean state; Cell(int my_x, int my_y, boolean s){ x = my_x; y = my_y; state = s; } void changeState(){ state = !state; } void appear(){ if(state){ fill(255, 255, 255); //fill(50, 50, 50); }else{ fill(50, 50, 50); //fill(255, 255, 255); } rect(x, y, SIZE_OF_CELL, SIZE_OF_CELL); } } void check_life_and_death(){ ArrayList<Point> points = new ArrayList<Point>(); for(int row=0; row<num_of_row; row++){ for(int col=0; col<num_of_col; col++){ //jibun no mawari check int num_of_alivers = 0; for(int r=-1; r<=1; r++){ for(int c=-1; c<=1; c++){ if(row+r<0 || row+r>=num_of_row || col+c<0 || col+c>=num_of_col){ continue; } if(cells[row+r][col+c].state){ num_of_alivers++; } } } if(cells[row][col].state){ //jibun no bun wo hiku num_of_alivers--; } //joutai change no note if(cells[row][col].state){ if(num_of_alivers<=1 || num_of_alivers>=4){ points.add(new Point(row, col)); } }else{ if(num_of_alivers==3){ points.add(new Point(row, col)); } } } } for(int i=0; i<points.size(); i++){ Point point = points.get(i); int point_row = point.getRow(); int point_col = point.getCol(); cells[point_row][point_col].changeState(); } } //random setup void randomSetup(){ size(FRAME_SIZE_OF_X, FRAME_SIZE_OF_Y); frameRate(20); for(int row=0; row<num_of_row; row++){ for(int col=0; col<num_of_col; col++){ int position_x = col * SIZE_OF_CELL; int position_y = row * SIZE_OF_CELL; float coin_seed = random(1); boolean coin; if(coin_seed>0.8){ coin = true; }else{ coin = false; } cells[row][col] = new Cell(position_x, position_y, coin); } } } void keyPressed(){ print("Key"); game_state = !game_state; if(key=='r' || key=='R'){ randomSetup(); }else if(key=='c' || key=='C'){ setup(); } } void mouseClicked(){ int cell_col = mouseX/SIZE_OF_CELL; int cell_row = mouseY/SIZE_OF_CELL; cells[cell_row][cell_col].changeState(); print("Clicked"); print(cell_col); print(cell_row); } void setup(){ size(FRAME_SIZE_OF_X, FRAME_SIZE_OF_Y); frameRate(20); for(int row=0; row<num_of_row; row++){ for(int col=0; col<num_of_col; col++){ int position_x = col * SIZE_OF_CELL; int position_y = row * SIZE_OF_CELL; cells[row][col] = new Cell(position_x, position_y, false); } } } void draw() { if(!game_state){ }else{ check_life_and_death(); } for(int row=0; row<num_of_row; row++){ for(int col=0; col<num_of_col; col++){ cells[row][col].appear(); } } //delay(500); }
github
t11378rs/lifegame · GitHub
思ったこと
多次元配列、クラスの入門なんかが学べるし。大学の授業でやってもおかしくないテーマだなあとおもった。教材にぜひどうぞ。
GoogleFinance()がめっちゃ使える話
最近株始めようと思ってるんですが、そのデータ管理にGoogleSpreadsheetが便利。
Excelなど他のソフトで資産管理をしている方も必読です。
GoogleSpreadsheetだけの圧倒的な差別化があります。それが
GoogleFinance()
という関数です。
=GoogleFinance("GOOG", "price")
とやると現在のGoogleの株価が出ます。
国内株の場合は、
=GoogleFinance("TYO:1234", "price")
のようにしてください。1234は証券コードです。
日本以外の株もこの要領で表示できると思います。
ちなみにこれを応用すると、A1に証券コードが入っているとして、
=GoogleFinance(CONCAT("TYO:", A1), "price")
のような事も出来ます。
今、"price"となっている引数は色々変えることができ、例えば以下のように"name"とすれば社名が出ます。
=GoogleFinance(CONCAT("TYO:", A1), "name")
しかし、これだと返ってくる表示は英語社名なので非常に不便です。そこで、GoogleTranslate()と組み合わせて、自動翻訳したいと思います。
=GoogleTranslate(GoogleFinance(CONCAT("TYO:", A1), "Name"), "en", "ja")
ちょっと違和感のある日本語になるかも知れませんが、そこはご愛嬌。
他にも様々な使い方、引数があるので気になる方は試してください。
GOOGLEFINANCE - ドキュメント エディタ ヘルプ
これが公式リファレンスです。
以上、知っていると幸せになれる投稿でした。
ポケモンスタンプラリー2014を最適ルートで回ってみた (回ってみた編)
ポケモンスタンプラリー2014を最適ルートで回ってみた (コーディング編) - 新米コンサルの日常のつづき
理論構築と実証は2つで一つです。
今回に関しても、プログラムを作って最適ルートを出すだけでは意味がありません。
ポケモンスタンプラリー、回ってきました。
おさらい
- ポケモンスタンプラリーとは、30駅を9:30~16:00で回るスタンプラリー
- これを最短最速で回ろうとすると、巡回セールスマン問題になる
- それを貪欲法で解くプログラムを作り、最適ルートを作成した
ルート説明
実はあの後、乗り換え/スタンプ時間を5分と仮定して、より具体的な乗換検索をしました。
それによると、
吉祥寺→立川→八王子→高田馬場→池袋→赤羽→浦和→大宮→武蔵浦和→渋谷→大崎→品川→浜松町→東京→秋葉原→四ツ谷→日暮里→北千住→松戸→柏→南船橋→津田沼→千葉
の23駅回る事ができるようです。
ぱっと見でも良さげのルートですね。
実際に回ってみた
ここからは当日の僕のツイートと共にお楽しみください。
スタンプラリー開始 (@ 吉祥寺駅 (Kichijōji Sta.) in 武蔵野市, 東京都 w/ 5 others) https://t.co/9YYpcmw0eg
— ポケモン(スタンプラリー)マスター (@YM_Ryo) 2014, 8月 5
俺の前におっさん並んでたから勇気を持ってスタンプ押せた
— だるいねむいさかい (@YM_Ryo) August 5, 2014
最初スタンプ押すの結構勇気が要りました。
ありがとう、前のリーマン風のおっさん…
巻いてる。順調。 (@ 立川駅 (Tachikawa Sta.) in 立川市, 東京都 w/ 9 others) https://t.co/b13cw5HTdP
— だるいねむいさかい (@YM_Ryo) August 5, 2014
ここで痛恨、10分の乗り換えロス… (@ 八王子駅 (Hachiōji Sta.) in 八王子市, 東京都 w/ 6 others) https://t.co/N1IRD49Lb1
— ポケモン(スタンプラリー)マスター (@YM_Ryo) 2014, 8月 5
東西線使ったせいで清算に時間がかかってしまった… (@ 高田馬場駅 (Takadanobaba Sta.) in Shinjuku, 東京都 w/ 4 others) https://t.co/xjYiEit0fB
— ポケモン(スタンプラリー)マスター (@YM_Ryo) 2014, 8月 5
巻いてたのはほんの数分。ここらへんで、どんどん押しだします。
このタイミングで埼京線運転見合わせ… (@ 池袋駅 (Ikebukuro Sta.) in としまく, 東京都 w/ 36 others) https://t.co/wx9ogcZmf0 pic.twitter.com/0gw1xDDc9o
— ポケモン(スタンプラリー)マスター (@YM_Ryo) 2014, 8月 5
池袋にて埼京線が止まります。以後、埼京線に苦しめられることに。
30分押し… (@ 赤羽駅 (Akabane Sta.) in 北区, 東京都 w/ 3 others) https://t.co/QFuy3PePQo
— ポケモン(スタンプラリー)マスター (@YM_Ryo) August 5, 2014
あえて遅延した湘南新宿ライン使うことで巻いてゆく (@ 浦和駅 (Urawa Sta.) in さいたま市, 埼玉県) https://t.co/J1Jh3KGViX
— ポケモン(スタンプラリー)マスター (@YM_Ryo) 2014, 8月 5
埼京線の遅れがエグい (@ 大宮駅 (Ōmiya Sta.) in さいたま市, Saitama Prefecture w/ 7 others) https://t.co/S5HcUK7BD7 pic.twitter.com/CjKVRhxVry
— ポケモン(スタンプラリー)マスター (@YM_Ryo) 2014, 8月 5
なーにがさいきょうじゃ
— だるいねむいさかい (@YM_Ryo) August 5, 2014
埼京線が遅延した時点で、ルートを再計算すべきでした。
来年以降、当日用のプログラムも作らねばいけないと痛感。
乗り換えロス18分www (@ 武蔵浦和駅 (Musashi-Urawa Sta.) in さいたま市, 埼玉県) https://t.co/QsAJuk4O06
— ポケモン(スタンプラリー)マスター (@YM_Ryo) 2014, 8月 5
ここらへんから23駅諦めだします。目標20駅
ポケモンスタンプラリーに関する最短経路について、家で1日くらいかけた厳密解も大事だけど、その場その場で構築するヒューリスティック解も重要であると知った2014年夏
— だるいねむいさかい (@YM_Ryo) August 5, 2014
マジこれ
10駅達成!!! (@ 渋谷駅 (Shibuya Sta.) in 渋谷区, 東京都 w/ 13 others) https://t.co/GxjIiX5H5Z pic.twitter.com/5665vHeVUd
— だるいねむいさかい (@YM_Ryo) August 5, 2014
13:17、開始から3時間47分でようやく10駅達成。しかし残り3時間を切っています。
山手線駅は駅間隔も電車間隔も短いから良い。 (@ 大崎駅 (Osaki Sta.) in 品川区, 東京都 w/ 2 others) https://t.co/FHUBoYf8Fr
— ポケモン(スタンプラリー)マスター (@YM_Ryo) 2014, 8月 5
12駅 (@ JR 品川駅 in 港区, 東京都 w/ 7 others) https://t.co/YjLN0eP47d
— だるいねむいさかい (@YM_Ryo) August 5, 2014
13駅。乗降多くてしんどい。 (@ 浜松町駅 (Hamamatsuchō Sta.) in 港区, 東京都 w/ 11 others) https://t.co/qy9QyMEdV9
— ポケモン(スタンプラリー)マスター (@YM_Ryo) 2014, 8月 5
山手線は順調。
何駅だっけ…。普通にしんどくなってきた… (@ 東京駅 (Tokyo Sta.) in 千代田区, 東京都 w/ 19 others) https://t.co/RtssEGmjQl
— ポケモン(スタンプラリー)マスター (@YM_Ryo) 2014, 8月 5
ピカチュウ (@ 秋葉原駅 (Akihabara Sta.) in 千代田区, 東京都 w/ 50 others) https://t.co/6blkG2I1YA pic.twitter.com/JrrQqh4dtx
— ポケモン(スタンプラリー)マスター (@YM_Ryo) 2014, 8月 5
16駅。感情が消えそう。 (@ 四ツ谷駅 (Yotsuya Sta.) in Shinjuku, 東京都 w/ 2 others) https://t.co/sFXs4ETHxu
— ポケモン(スタンプラリー)マスター (@YM_Ryo) 2014, 8月 5
マヤ「スタンプ数19!」リツコ「だめ!人間に戻れなくなる!」 (@ 日暮里駅 (Nippori Sta.) in 荒川区, 東京都 w/ 2 others) https://t.co/7PUgUak7DY pic.twitter.com/gr7jBbsVYu
— だるいねむいさかい (@YM_Ryo) August 5, 2014
お分かりでしょうか?
ここらへんから、ちょっと頭がおかしくなってきています。
最後なんてネタツイートで駅数間違える痛恨のミス。
18駅。常磐線難しい。 (@ 北千住駅 (Kita-Senju Sta.) in 足立区, 東京都 w/ 3 others) https://t.co/Ndny3mKfpf
— ポケモン(スタンプラリー)マスター (@YM_Ryo) 2014, 8月 5
19駅!あと35分 (@ 松戸駅 (Matsudo Sta.) in 松戸市, 千葉県) https://t.co/C5L2PbqJPt
— だるいねむいさかい (@YM_Ryo) August 5, 2014
そして
20駅達成!!!!!!! (@ 柏駅 (Kashiwa Sta.) in 柏市, 千葉県) https://t.co/XxcVPOTLKD pic.twitter.com/JAz3mG542m
— だるいねむいさかい (@YM_Ryo) August 5, 2014
なんとか20駅を達成することが出きました。
行ける場所全部行くと16時越えちゃうので、20駅ちょうどで投了ですね。最後上野で景品交換はできそうなのでそれ行きます。 pic.twitter.com/qENYkYC6LL
— だるいねむいさかい (@YM_Ryo) August 5, 2014
俺の夏は終わった… (@ 上野駅 (Ueno Sta.) in 台東区, 東京都 w/ 7 others) https://t.co/0bjbOsv81h pic.twitter.com/0vuURER05h
— だるいねむいさかい (@YM_Ryo) August 5, 2014
終了時点で余裕があったので、最後は景品交換もできました。
そういう意味では21駅ですね。
もちもの
あと、必ず買え、というものを挙げておきます。
飲みもの
私は3本ペットボトルを空けました。
たべもの
ウイダーのように、時間と場所を選ばない食べ物が望ましいです。
とはいえ、乗り換え待ちで時間が空いた時にポケモンパンとか食べるのもありです。
ケータイの充電器
バッテリ切れると乗換検索できなくて詰みます。
ひまを潰せるもの
僕は、PCでバイトの作業をしていました。
ただ、PCは重量が負担になったので、次回は本1冊とかにすると思います。
注意事項
途中、頭おかしくなってるところは軽い熱中症になっていたと思います。
基本的には電車内なので、涼しいのですが、ホームでの待機と、スタンプ行って帰っての往復が響いたのだと思います。
皆さんがスタンプラリーを回る際には十分に注意してください。
反省点
- 厳密解を有限時間で求めることが出きなかった。
- 当日の状況に応じてルートを臨機応変に計算できるツールが欲しかった。
この2点を来年は改善させたいと思っています。
おわりに
つかれた…
ポケモンスタンプラリー2014を最適ルートで回ってみた (コーディング編)
ポケモンスタンプラリー2014を最適ルートで回ってみた (問題提起編) - 新米コンサルの日常のつづき
おさらい
- ポケモンスタンプラリーとは、30駅を9:30~16:00で回るスタンプラリー
- これを最短最速で回ろうとすると、巡回セールスマン問題になる
- 巡回セールスマン問題は有限時間で解くのが困難 (NP困難)
- 実際、今回のルートについて全ての通りを数え上げると30!/2通りになる
問題定義
計算と、実証の簡単のために、問題を少し矮小化して、
「実行日(平日)の9:30~16:00で最も多くの駅を回るルートを見つける。」
とします。
どうしてこれが計算の簡単に役立つかというと、16:00以降どこに行くべきか、を意識に入れないで済むからです。
「10駅回ったところで16:15になりました。その後の最短ルートも探しますか?」
と言われたら、計算時間の無駄だからやめろって言いますよね。
実際、このおかげで、20!程度まで計算量を削減出来ました。
データの取得
自動乗り換え計算の方法を考えると、まず、最短経路の計算手段について
毎回きっちり調べるのか / 蓄えたデータを利用するのか
という小問題があります。
前者は厳密ですが時間がかかる、後者は近似的ですが時間がかかりません。
そこでまず、ランダムに作った30駅のルートを「毎回きっちり調べる」で計算してみたところ、ゆうに4秒程度かかりました。
一方、「蓄えたデータ利用」で計算すると、0.5秒かからず、数分の誤差の近似解を出すことができたので、今回はこちらを採用しました。
そもそも、4秒というのは今回膨大な処理を行うことを考えると、非常に大きい時間(!)で、私が生きている間に計算を終わらせることが出きそうにないので現実的ではありません。
ちなみにデータソースはYahoo!乗換検索をスクレイピングしたものです。APIを叩く方がいいんじゃないか、のような意見があると思うのですが、
のでスクレイピングをしました。
ちなみにGoogle経路検索APIは公共交通機関を(まだ)サポートしていません。
つくってみた
ルートを作成する方法を3通り作りました。
- ランダム作成
- 貪欲法で作成
- (エセ)分枝限定法で作成
それぞれについて説明します。
(ちなみにスタンプ、乗り換え時間を考慮していません。)
ランダム作成
こんな感じ。体感ですが平均8駅くらいしか回れません。(6:55と言うのは所要時間)
何も考えずに回るとこうなるよ、って話ですね。
ちなみに一番下の時間が、処理にかかった時間なのですが、データベースの読み込みに18秒ちょいかかるので、実質2秒で作って(表示して)るっぽいですね。
貪欲法
貪欲法って名前きくと尻込みするかもしれませんが、要するに、
一番行きやすい駅に行くのを繰り返す
ってことです。その結果がこれ ↓
いい感じですよね!
処理にかかる時間もランダムとほとんど変わらないのに、これだけ結果が向上するのはとても嬉しい。
しかし、これは厳密解ではありません。
良い近似解(ヒューリスティクス)と言えますが、決して、最良とは限らないのです。
実際、特に終盤になると顕著ですが、大きな移動が増えます。
前半にとりあえず近いところを… という試行を繰り返したツケを結局後半に払うわけですね。
(エセ)分枝限定法
分枝限定法って名前きくと尻込みするかもしれません。
大いに尻込みしてください。僕は尻込みしました。
要するに、問題を小さく分けて、解かなくていい問題を省こうね、って事らしいのです。
が、尻込みしました。厳密な実装は断念です。
なので、結局これは総当りです。とはいえ、タイムオーバーしたものなど、解かなくていい問題は解いないあたり分枝限定法と言えなくもない気が、しなくもなくもなくもない。
で、計算”途中”がこちら ↓
終わんねえよ…
計算量圧縮しきれませんでした。
ちなみにこれを3時間ほど回した結果、メモリにSSD容量食いつくされて色々クラッシュしました。
あかん。
結局、
近似解である、貪欲法ルートを今回の「最適ルート」としました。
残念ながらポケモンスタンプラリー全駅制覇の夢は断念です…
また、作業ディレクトリまるごとGitHubに上げたので、気になる人は見てください。
(spider.py, main.py, calc_route.pyくらいです。大事なのは)
次回、「回ってみた編」です。
ポケモンスタンプラリー2014を最適ルートで回ってみた (問題提起編)
夏休みといえば、何が思い浮かびますか?
JR東日本ポケモンスタンプラリーとは
- 1997年ほぼ毎年行われているスタンプラリー
- 東京、神奈川、埼玉、千葉の1都3県、合計30駅スタンプ駅がある (2014年)
- 6駅集めると景品がもらえる。30駅全部集めると抽選でなんかもらえる (2014年)
- スタンプ設置時間は9:30~16:00 (2014年)
です。
首都圏に住んでいる方なら、毎夏、電車内で子供がスタンプシートを持っている姿は、風物詩になっているのではないでしょうか。
僕も、小学生の頃、親にせがんで山手線の駅をぐるぐると回ったことを覚えています。
さて、そんなスタンプラリーですが、大学4年生になった今、表題の通り回って来きした。
スタンプラリーは、金はないが時間のある大学生の夏休みには、もってこいの暇つぶしになります。
そもそもスタンプラリー、実は奥が深い。
特に、後述するように、ポケモンスタンプラリーはスタンプラリー界でも屈指の難易度なのです。
実は、スタンプラリーのように、あるポイント群を最短で繋ぐことを求められる問題には名前がついています。
その名も巡回セールスマン問題です。
詳しくは説明しませんが、巡回セールスマン問題はNP困難と呼ばれる問題にカテゴライズされていて、普通に解いていては、生きている間に計算が終わらないのです!
今回のポケモンスタンプラリーはスタンプ駅が30駅もあります。
スタンプラリー界でもこれほど多いものは、あまりありません。
この時、全てのスタンプを押す順番の通りの数を求めると、
30!/2 ≒
132626429906096000000000000000000 [通り]
となります。
ぱねえ
ちなみに、漢字で書くと、
十三穣 二千六百二十六𥝱 四千二百九十九垓 六百九京 六兆 [通り]
になります。
ぱねえ。
試しに全部回ってたら余裕で寿命尽きてしまうでしょう。
というわけで、人類の偉大なる奴隷、コンピューターにこの計算を託すことにしました。
次回はコーティング編です。
(追記8/11)
コーディング編
ポケモンスタンプラリー2014を最適ルートで回ってみた (コーディング編) - 新米コンサルの日常
hello, はてなblog!
blogといふものを、してみむとするなり。