読者です 読者をやめる 読者になる 読者になる

新米コンサルの日常

僕の日常の非日常を適当に書いていきます。

Processingでライフゲームつくった。

Processing

バイトで暇だったので、Processingでライフゲームつくった。

ライフゲームとは、

単純なルールでシュミレートされた細胞生物を、ぼーっと見て楽しむものである。

 

こんなのとか
f:id:t11378rs:20140826175024g:plain

こんなパターンが出てきて楽しい。
f:id:t11378rs:20140826175020g:plain

詳しくは、
ライフゲーム - Wikipedia


 

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


これ。だれかの参考になれば。
「Processing ライフゲーム」でぐぐるとエセソースコードでるので注意。

思ったこと

多次元配列、クラスの入門なんかが学べるし。大学の授業でやってもおかしくないテーマだなあとおもった。教材にぜひどうぞ。

GoogleFinance()がめっちゃ使える話

GoogleSpreadsheet

最近株始めようと思ってるんですが、そのデータ管理に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駅回る事ができるようです。

f:id:t11378rs:20140812084008j:plain

ぱっと見でも良さげのルートですね。

 

 

実際に回ってみた

ここからは当日の僕のツイートと共にお楽しみください。

最初スタンプ押すの結構勇気が要りました。

ありがとう、前のリーマン風のおっさん…

 

巻いてたのはほんの数分。ここらへんで、どんどん押しだします。

 

池袋にて埼京線が止まります。以後、埼京線に苦しめられることに。

 

埼京線が遅延した時点で、ルートを再計算すべきでした。

来年以降、当日用のプログラムも作らねばいけないと痛感。

 

ここらへんから23駅諦めだします。目標20駅

 

マジこれ

 

13:17、開始から3時間47分でようやく10駅達成。しかし残り3時間を切っています。 

 

山手線は順調。

 

お分かりでしょうか?

ここらへんから、ちょっと頭がおかしくなってきています。

最後なんてネタツイートで駅数間違える痛恨のミス。

 

 

そして

なんとか20駅を達成することが出きました。

 

終了時点で余裕があったので、最後は景品交換もできました。

そういう意味では21駅ですね。

 

 

もちもの

あと、必ず買え、というものを挙げておきます。

飲みもの

私は3本ペットボトルを空けました。

たべもの

ウイダーのように、時間と場所を選ばない食べ物が望ましいです。

とはいえ、乗り換え待ちで時間が空いた時にポケモンパンとか食べるのもありです。

ケータイの充電器 

バッテリ切れると乗換検索できなくて詰みます。

ひまを潰せるもの

僕は、PCでバイトの作業をしていました。

ただ、PCは重量が負担になったので、次回は本1冊とかにすると思います。

 

 

注意事項

途中、頭おかしくなってるところは軽い熱中症になっていたと思います。

基本的には電車内なので、涼しいのですが、ホームでの待機と、スタンプ行って帰っての往復が響いたのだと思います。

皆さんがスタンプラリーを回る際には十分に注意してください。 

 

 

反省点

  • 厳密解を有限時間で求めることが出きなかった。
  • 当日の状況に応じてルートを臨機応変に計算できるツールが欲しかった。

この2点を来年は改善させたいと思っています。

 

 

おわりに

つかれた… 

ポケモンスタンプラリー2014を最適ルートで回ってみた (コーディング編)

python アルゴリズム スタンプラリー ポケモン 巡回セールスマン問題

ポケモンスタンプラリー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通り作りました。

  1. ランダム作成
  2. 貪欲法で作成
  3. (エセ)分枝限定法で作成

それぞれについて説明します。

(ちなみにスタンプ、乗り換え時間を考慮していません。)

 

 

ランダム作成

f:id:t11378rs:20140811172923j:plain

こんな感じ。体感ですが平均8駅くらいしか回れません。(6:55と言うのは所要時間)

何も考えずに回るとこうなるよ、って話ですね。

ちなみに一番下の時間が、処理にかかった時間なのですが、データベースの読み込みに18秒ちょいかかるので、実質2秒で作って(表示して)るっぽいですね。

 

 

貪欲法

貪欲法って名前きくと尻込みするかもしれませんが、要するに、

一番行きやすい駅に行くのを繰り返す

ってことです。その結果がこれ ↓

f:id:t11378rs:20140811173259j:plain

いい感じですよね!

処理にかかる時間もランダムとほとんど変わらないのに、これだけ結果が向上するのはとても嬉しい。

しかし、これは厳密解ではありません。

良い近似解(ヒューリスティクス)と言えますが、決して、最良とは限らないのです。

実際、特に終盤になると顕著ですが、大きな移動が増えます。

前半にとりあえず近いところを… という試行を繰り返したツケを結局後半に払うわけですね。

 

 

(エセ)分枝限定法

分枝限定法って名前きくと尻込みするかもしれません。

大いに尻込みしてください。僕は尻込みしました。

要するに、問題を小さく分けて、解かなくていい問題を省こうね、って事らしいのです。

が、尻込みしました。厳密な実装は断念です。

なので、結局これは総当りです。とはいえ、タイムオーバーしたものなど、解かなくていい問題は解いないあたり分枝限定法と言えなくもない気が、しなくもなくもなくもない。

で、計算”途中”がこちら ↓

f:id:t11378rs:20140811174215j:plain

終わんねえよ…

計算量圧縮しきれませんでした。

ちなみにこれを3時間ほど回した結果、メモリにSSD容量食いつくされて色々クラッシュしました。

あかん。

 

 

結局、

近似解である、貪欲法ルートを今回の「最適ルート」としました。

残念ながらポケモンスタンプラリー全駅制覇の夢は断念です…

また、作業ディレクトリまるごとGitHubに上げたので、気になる人は見てください。

(spider.py, main.py, calc_route.pyくらいです。大事なのは)

t11378rs/tsp_poke · GitHub

 

 

次回、「回ってみた編」です。

ポケモンスタンプラリー2014を最適ルートで回ってみた (回ってみた編) - 新米コンサルの日常

ポケモンスタンプラリー2014を最適ルートで回ってみた (問題提起編)

python アルゴリズム スタンプラリー ポケモン 巡回セールスマン問題

夏休みといえば、何が思い浮かびますか?

 

 

 

そう、JR東日本ポケモンスタンプラリーですよね。

f:id:t11378rs:20140807164930p:plain

(JR東日本ポケモンスタンプラリー公式HPより引用)

 

 

 

JR東日本ポケモンスタンプラリーとは

  • 1997年ほぼ毎年行われているスタンプラリー
  • 東京、神奈川、埼玉、千葉の1都3県、合計30駅スタンプ駅がある (2014年)
  • 6駅集めると景品がもらえる。30駅全部集めると抽選でなんかもらえる (2014年)
  • スタンプ設置時間は9:30~16:00 (2014年)

です。

首都圏に住んでいる方なら、毎夏、電車内で子供がスタンプシートを持っている姿は、風物詩になっているのではないでしょうか。

僕も、小学生の頃、親にせがんで山手線の駅をぐるぐると回ったことを覚えています。

 

さて、そんなスタンプラリーですが、大学4年生になった今、表題の通り回って来きした。

スタンプラリーは、金はないが時間のある大学生の夏休みには、もってこいの暇つぶしになります。

 

 

 

そもそもスタンプラリー、実は奥が深い。

特に、後述するように、ポケモンスタンプラリーはスタンプラリー界でも屈指の難易度なのです。

 

実は、スタンプラリーのように、あるポイント群を最短で繋ぐことを求められる問題には名前がついています。

その名も巡回セールスマン問題です。

f:id:t11378rs:20140807165148j:plain

詳しくは説明しませんが、巡回セールスマン問題はNP困難と呼ばれる問題にカテゴライズされていて、普通に解いていては、生きている間に計算が終わらないのです!

 

今回のポケモンスタンプラリーはスタンプ駅が30駅もあります。

スタンプラリー界でもこれほど多いものは、あまりありません。

 

この時、全てのスタンプを押す順番の通りの数を求めると、

30!/2 ≒

132626429906096000000000000000000 [通り]

となります。

  

ぱねえ

 

ちなみに、漢字で書くと、

十三穣 二千六百二十六𥝱 四千二百九十九垓 六百九京 六兆 [通り]

になります。

 

ぱねえ。

 

試しに全部回ってたら余裕で寿命尽きてしまうでしょう。

 

というわけで、人類の偉大なる奴隷、コンピューターにこの計算を託すことにしました。

 

 

 

次回はコーティング編です。

 

(追記8/11)

コーディング編

ポケモンスタンプラリー2014を最適ルートで回ってみた (コーディング編) - 新米コンサルの日常