タイトル変更とドメイン設定しました

ブログタイトルを「ありんこ日記」から「ありぺい日記」に変更しました。また、aripei.comを取得したので、ブログをサブドメインのblog.aripei.comにして運用する事にしました。こうなると他のアカウントとかも@aripeiにしたくなるところだが、だいたいすでに取られてる…。

Top Coder SRM 609 Level3 おさらい

今週末もTop Coderに参戦したが、例のごとく最終問題のみ解けなかったので復習した。

今回はGumiとIaとMayuというボーカロイドが音楽アルバムを作りますという若干Geekyなお題でした。以下のような入力値が与えられた時に、すべての曲が必ず一名以上に歌われるようなアルバムのパターンは何種類あるかという問題です（一つの曲を複数人で歌うのはOK）。

入力値(すべて1から50までの整数)

• S: 全曲数
• gumi: Gumiが歌う曲数
• ia: Iaが歌う曲数
• mayu: Mayuが歌う曲数

出力値

• Int: アルバムのパターン数

例えば(3,1,1,1)だと3C1 * 2C1 * 1C1で6パターンとなります。

各曲に対して、各一名ずつ歌う場合（3パターン）、各二名ずつ歌う場合（3パターン）、三人全員が歌う場合（1パターン）の合計7パターンあります。なので7のS乗回試行して条件を満たすものをカウントすればよいのですが、Sが50の場合には1.798465e+42回ほど試行する事になるので残念ながら僕が死ぬまでには計算が終わらなそうです。

この手の問題はどうやら以下の二種類の方法で解けるようです。

• 場合分けをして数学的に解く
• 動的計画法で解く

前者は場合分けを行ってCombinationを駆使して解く方法、後者は分割統治法とメモ化と呼ばれる手法を使って問題を細分化して同じパターンの部分をキャッシュしながら解く方法です。勿論、数学的に解けた方がエレガントではあるのですが、Top Coderでは動的計画法は必須知識らしく、他の多くの問題に応用可能なようなので今回はこちらで解いてみました。

まずは各項が以下の漸化式で求められるという事に気づく必要があります。こちらは前述の通り各曲に対して7パターン存在するということからも分かると思います。

• f(s, g, i, m) = f(s-1, g-1, i, m) + f(s-1, g, i-1, m)  + f(s-1, g, i, m-1)  + f(s-1, g,-1 i-1, m)  + f(s-1, g-1, i, m-1) +  + f(s-1, g, i-1, m-1)  + f(s-1, g-1, i-1, m-1)
• f(0,0,0,0) = 1

後は、各入力値は正の値であるとか、g+i+m > sであるとかの確認をして、この漸化式を満たして、s/g/i/mのパターンをキャッシュしてあげるようなプログラムを実装すればよいです。

できあがりは以下のようなコードになりました。でも、やっぱこのレベルの問題を30分で完璧に解くのはまだまだ無理だなぁ。あ、ちなみに1000000007で割ってるのは問題文に数値がでかすぎるのでこの値の剰余をとるようにって書いてあったから。

import java.util.*;

public class VocaloidsAndSongs {

    long cache[][][][];
    final long MOD = 1000000007L;

    public int count(int S, int gumi, int ia, int mayu) {

        cache = new long[S + 1][gumi + 1][ia + 1][mayu + 1];

        for (int s = 0; s <= S; s++) {
            for (int g = 0; g <= gumi; g++) {
                for (int i = 0; i <= ia; i++) {
                    for (int m = 0; m <= mayu; m++) {
                        cache[s][g][i][m] = -1L;
                    }
                }
            }
        }
        return (int) dp(S, gumi, ia, mayu);
    }

    private long dp(int s, int g, int i, int m) {

        if (s > (g + i + m)) {
            return 0;
        }

        if (s == 0) {
            if (g == 0 && i == 0 && m == 0) {
                return 1L;
            } else {
                return 0L;
            }
        }

        if (g < 0 || i < 0 || m < 0) {
            return 0L;
        }

        if (cache[s][g][i][m] == -1L) {
            cache[s][g][i][m] = dp(s - 1, g - 1, i, m) +
                    dp(s - 1, g, i - 1, m) +
                    dp(s - 1, g, i, m - 1) +
                    dp(s - 1, g - 1, i - 1, m) +
                    dp(s - 1, g - 1, i, m - 1) +
                    dp(s - 1, g, i - 1, m - 1) +
                    dp(s - 1, g - 1, i - 1, m - 1);

        }

        return cache[s][g][i][m] % MOD;
    }

}

Top Coder SRM 608 Level3 おさらい

昨日、Top Coder SRMに二回目の参加をしてみたのですが、Level 3が解けなくて悔しかったので復習してみた。

問題は要約するとN個のノードからなる有効グラフが渡された時にステップ数Lからなる経路の数が多項式P(L)で表されるか判別するプログラムを書くというのが問題です。本番では英語だし若干複雑なので理解するのに若干時間がかかりましたが…。 

入力値は個々のエッジを表すYとNの文字の羅列が以下のようにStringのArrayとして渡される。配列長と文字数はグラフの頂点の数と同じです。

String[] graph = new String[]{"NYN","NNY","YNN"};

また、出力は多項式解が存在する場合には"Bounded"、存在しない場合には"Unbounded"をリターンするだけです。

この問題は本番時にはコード以前にそもそもどういうアルゴリズムにすれば解けるのかが思いつきませんでした。終了後に以下のようにホワイトボードを使って精査したらやっとひらめいた。




NPがNon Polynomial(多項式解なし)でPがPolynomial(多項式解あり)を表しています。どうやら循環して自分に戻ってくるような経路を二つ以上もつノードがある場合に多項式解がなくなるようです。赤のラインで循環を示しているのですが、このラインが一つのノードから2つ以上出ている場合に多項式解がなくなります。例えば循環経路がM、自分に戻ってくるまでにNステップかかると経路数の計算は「Mの(L / N)乗」になるはずです。という訳でMが1の場合には多項式解、Mが2以上の時には多項式では解けないはず。

ルールさえ分かってしまえばコードはこんな感じで簡単に書けました。単純に一つ一つのノードをイテレートして循環が2つ以上ないか確認するだけです。

import java.util.*;

public class BigOEasy {
    static final String UNBOUNDED = "Unbounded";
    static final String BOUNDED = "Bounded";

    boolean[][] edges;
    public String isBounded(String[] graph) {

        // edges as boolean 2d array
        edges = new boolean[graph.length][graph.length];
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph[i].length(); j++) {
                edges[i][j] = (graph[i].charAt(j) == 'Y');
            }
        }

        // each vertex
        for (int currentVertex = 0; currentVertex < edges.length; currentVertex++) {
            int num_of_circle = 0;

            // each edge
            for (int nextVertex = 0; nextVertex < edges[currentVertex].length; nextVertex++) {
                // check if circular
                if (edges[currentVertex][nextVertex]) {
                    if(checkCircular(currentVertex, nextVertex, new boolean[edges.length])){
                        num_of_circle++;
                    }
                }

                // unbounded if more than one circulars
                if(num_of_circle > 1){
                    return UNBOUNDED;
                }
            }
        }
        return BOUNDED;
    }

    private boolean checkCircular(int startVertex, int currentVertex, boolean visited[]) {
        visited[currentVertex] = true;
        for(int nextVertex = 0; nextVertex < edges.length; nextVertex++){
            if(edges[currentVertex][nextVertex]){
                if(startVertex == nextVertex){
                    return true;
                }else if(visited[nextVertex]){
                    continue;
                }else{
                    if(checkCircular(startVertex, nextVertex, visited)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

ただ、Level 1で10分、Level 2で20分程度は消費すると考えるとLevel 3に費やせる時間は30分程度しかありません。ちょっと本番でこのレベルの問題がでたらかなりラッキーじゃないと時間内に解ける気がしませんね。今のところは確実にLevel 1とLevel 2を片付けることを目標とするか。忘れかけたJavaをググりながら書いているので、この辺りのTipsが身に付けば早く解けるようになってもう少しスコアがあがるはず。

Pythonでデータ分析ごっこ事始めしてみる

弊社(Cambridge Energy Data Lab)ではデータサイエンス系の開発言語をPythonに統一しておりまして、社員達がNumPy、SciPy、pandasなどなどを目下勉強中です。

データサイエンティストも積極採用中なのですが、応募者全員に以下のデータ解析タスクをGitHubから提出するという課題を課しています。

Cambridge Energy Data Lab: EnergyDataSimulationChallenge

既に15フォークされていて、質の良いPull Requestも多く来ていて嬉しい限りです。Cambridge大学の学生もどんどん応募してきてくれています。皆さんもお暇な時に是非 :)

これが採用に非常に有効で、まずランダムにCVを送りまくっている応募者や、最低限のスキルの身に付いていない応募者のフィルタリングが非常に効率的に行えます。基本的にはこのプログラミングタスクの提出をしていない応募者のCVは一切確認しません。また、どの言語が得意なのか、どんなライブラリの扱いに慣れているか、どのように考えて分析を進めているのかなどなど、やはりコードを見ると非常に効率よく応募者のスキルを知る事ができます。

とか偉そうな事を言っておいて、実は僕はWeb Applicationの開発に集中しないといけないという言い訳があり、自分ではデータ解析部分に殆ど触れておらずデータサイエンティストに任せっきりにしていました。しかしながら採用活動をバンバンしている手前、それじゃいかんなと反省して、週末にちょっと時間をみつけて自分でもPythonでデータ解析をしてみました。

環境設定

まずはCanopyをインストールしました。こちらはPythonでのデータ解析に利用されるライブラリ群（NumPy、SciPy、Matplotlib、pandasなどなど）に加えてIPythonが搭載された統合環境です。これをインストールするだけで必要なツールが一気に揃うので、Macを使っている方には非常にお薦めです。

分析結果はIPython Notebookにまとめると便利です。Web上でInteractiveにコードの実行が出来、かつDescriptionなども加えられて自分の分析がNotebookとしてまとめられるので分析結果の公開が非常にやり易いです。

以下のように実行すると、Plotに必要なライブラリが読み込まれ、かつ結果のグラフ等の出力がHTMLに出力されて便利です。

ipython notebook --pylab inline

UIはこんな感じ。

チャレンジ

覚えないと行けない事は非常に多いのですが、とりあえずはpandasのDataFrameとしてデータを取り込んで、Matplotlibで可視化するという事を目標にして、Challenge 2 - Visualization of Energy Consumptionsに取り組みました。主にデータの可視化、時系列変換、クラスタリングを行うタスクです。

初めて触るということもありやっぱデータの扱いに慣れておらず、半日近くかけてなんとか以下の処理だけ済ませました。

1. pandasにデータ取り込み
2. そのままPlot
3. データのDiffをプロット
4. 時系列変換してプロット
5. データの分類（クラスタリング）をしてプロット

ちなみに、Gitに載せておくとIPython Notebook Viewerというサービスで公開できて便利です。僕の分析はこちらから見られます。とりあえず最低要件だけはなんとか済ませたというレベルなので、暇を見つけてちょっとかっこ良く分析するかな。特に単純に平均から標準偏差を足して引いてしてるだけの分類がダサいので。

HerokuからS3へアクセスするRakeを作ってみた

S3に置かれたデータファイルを取得し、それを読み込みデータを更新するというRakeタスクを作って、Herokuのスケジューラでバッチタスクとして登録してみました。このあたり（Using AWS S3 to Store Static Assets and File Uploads）を参照しながら進めました。

Rakeの設定

Rakeのタスクはrailsコマンドでlib/tasks以下に生成される。

$ rails generate task loader
      create  lib/tasks/loader.rake

とりあえずこんな感じで作って。

namespace :loader do
  desc "Load Data Files"
  task :test => :environment do
    puts "test"
  end
end

実行できる。

$ rake loader:test
test

RSpecもこんな感じで書けました。generatorはないっぽいけどspec/tasks以下とかに置けばよいのでは。

require 'spec_helper'
require 'rake'
MyApp::Application.load_tasks

describe 'Rake Test' do
  it 'run test' do
    Rake::Task['test'].invoke('arg')
  end
end

S3へのアクセス

RubyからS3の利用はAmazonのドキュメント（AWS SDK for Ruby）を見ながら設定したら思いのほか簡単にできました。 S3のアクセス情報はHerokuのConfigに突っ込んで環境変数として使います(Configuration and Config Vars)。ローカルから走らせる場合には環境変数に設定するかRakeコマンドに引数として渡す事もできます。

$ heroku config:set S3_KEY=xxx S3_SECRET=yyy S3_BUCKET=zzz
Adding config vars and restarting app... done, v21
  S3_BUCKET  => zzz
  S3_KEY     => xxx
  S3_SECRET  => yyy

まぁ、以下のようにrailsのconfigに置いちゃっても良いみたいだけど。ちなみにこれは接続に失敗した時に表示されるAWSライブラリのエラーメッセージです。

= Ruby on Rails
       
In a Ruby on Rails application you may also specify your credentials in
the following ways:
       
* Via a config initializer script using any of the methods mentioned above
 (e.g. RAILS_ROOT/config/initializers/aws-sdk.rb).
       
* Via a yaml configuration file located at RAILS_ROOT/config/aws.yml.
  This file should be formated like the default RAILS_ROOT/config/database.yml
  file.

Rubyからのアクセスには、まず以下のGemを追加します。

gem "aws-sdk", "~> 1.32.0"

そうすると上で設定した環境変数を引っ張って下記のように接続からBucketの取得までできます。

AWS.config(access_key_id: ENV['S3_KEY'],
           secret_access_key: ENV['S3_SECRET'],
           region: 'us-west-2')
BUCKET = AWS::S3.new.buckets[ENV['S3_BUCKET']]

すると以下のように、key名のprefixでS3上のオブジェクトを取得したりデータを読み込んだりできます。オブジェクトの詳細な扱いとかはAWS::S3のクラスドキュメントにまとまっています。

BUCKET.objects.with_prefix(directory).each do |obj|
  puts obj.key
  puts obj.read
end

スケジューラへの追加

スケジュール化されたタスクを走らせる方法としては定期的にRakeコマンドを実行するHeroku SchedulerとClockworkなどのGemを利用する方法があるらしい。Heroku Schedulerはone-off dynos上で実行されるBest Effortサービスらしいが、とりあえずこっちの方が簡単そうなのでこちらで実装してみました。 Heroku Schedulerのアドオンを追加すると以下のような感じで簡単にJobの登録ができます。
実行後に以下のようにログを確認できます。

$ heroku logs -p scheduler
2014-01-16T18:07:59.715840+00:00 heroku[scheduler.7222]: Starting process with command `bundle exec rake test`
2014-01-16T18:08:00.376906+00:00 heroku[scheduler.7222]: State changed from starting to up
2014-01-16T18:08:04.282904+00:00 app[scheduler.7222]: Loading Files for 20140116
2014-01-16T18:08:04.719251+00:00 app[scheduler.7222]: 
2014-01-16T18:08:04.719251+00:00 app[scheduler.7222]: [AWS S3 200 0.431475 0 retries] list_objects(:bucket_name=>"zzz",:max_keys=>1000,:prefix=>"pre")  
2014-01-16T18:08:05.958921+00:00 heroku[scheduler.7222]: Process exited with status 0
2014-01-16T18:08:05.980991+00:00 heroku[scheduler.7222]: State changed from up to complete

ところで、Herokuのログってdefaultだと1500行までしか保持してくれないんですね。アドオン導入しないとな。やっぱPapertrailでしょうか。