Google Code Jam Japan 2011 決勝 問題E 無限庭園
正解者が一人という超難問「無限庭園」の解説動画です。
講師はITmediaの『最強最速アルゴリズマー養成講座』でお馴染みの高橋直大さんです。
Google Code Jam Japan 2011 決勝 問題E 無限庭園
動画情報
- 時間 33分
- 画面 720x480
- 大きさ 286MB
高橋直大の『プログラマのための論理思考トレーニング〜問題を素早く把握し実装するために〜 初級編 1』
12月17日に、プログラミング初心者向けにプログラミング講座を行いました。
Red Coder 高橋直大の『プログラマのための論理思考トレーニング〜問題を素早く把握し実装するために〜 初級編 1』
70人ぐらいの方が見に来て下さったようで、本当にありがとうございました!
次回(多分、一月にやります)もたくさんの人が楽しめるような問題を用意しますので、御期待下さい!
FNVハッシュ関数
FNVハッシュ関数は簡単に実装できるハッシュ関数です。
Twitterで見かけたので忘れないうちにメモ。
FNV-1 hash
hash=offset_basis for each octet_of_data to be hashed hash=hash*FNV_prime hash=hash xor octet_of_data return hash
octet_of_dataは変換元データから8bitずつ取り出した物を表します。変換元データがアルファベットだけから成る文字列なら、一文字ずつ取り出すのと同じです。
offset_basisとFNV_primeについては後述します。
FNV-1a hash
XORを先にするだけです。変換元のデータが32bitよりも小さい場合はハッシュ値の分散度合いが良くなります。
hash=offset_basis for each octet_of_data to be hashed hash=hash xor octet_of_data hash=hash*FNV_prime return hash
offset_basis
hashのビット幅に応じて次の物を使います
- 32bit 2166136261
- 64bit 14695981039346656037
- 128bit 144066263297769815596495629667062367629
- 以下略
FNV_prime
hashのビット幅に応じて次の物を使います
- 32bit 16777619
- 64bit 1099511628211
- 128bit 309485009821345068724781371
- 以下略
例
#include <stdio.h> int main() { char *s="abcde"; unsigned int hash=2166136261UL; while (*s) { hash*=16777619UL; hash^=*(s++); } printf("%u\n",hash); return 0; }
CakePHPでOAuth
Twitter等で使われているOAuthをCakePHPで使うライブラリを紹介します。
OAuth consumers for CakePHP - by cakebaker
導入方法
使い方
Twitterを例にして説明します。Twitter以外のサービスを利用する場合も基本的には同じです。
大まかな流れは次の様になります。
・事前準備
Webサービスの立ち上げ前に、Twitterからconsumer keyとconsumer secretをあらかじめ取得しておく
・認証とAPI利用の流れ
- Twitterからリクエストトークンを取得
- Twitterの認証ページへリダイレクト
- ユーザにログインしてもらう
- ログイン後、あらかじめ設定しておいた自サイトのURLにTwitterがリダイレクトしてくれる
- Twitterからアクセストークンを取得
- 取得したアクセストークンを使ってTwitterのAPIを実行
それでは具体的に説明して行きます。
事前準備
OAuthを使う際には、立ち上げようとするWebサービス毎にconsumer keyとconsumer secretというものが必要になります。consumer keyとconsumer secretはサービスの提供者側から取得します。Twitterの場合はhttp://twitter.com/oauth_clients で取得する事ができます。
認証とAPI利用の流れ
1. ライブラリの取り込み
App::import('Vendor','oauth',array('file'=>'OAuth'.DS.'oauth_consumer.php'));
$consumer=new OAuth_Consumer(取得したconsumer key,取得したconsumer secret); $requestToken=$consumer->getRequestToken( 'http://twitter.com/oauth/request_token', 'http://認証後のリダイレクト先'); // 認証後に使うので保存 $this->Session->write('request_token',$requestToken);
3. Twitterの認証ページへリダイレクト
$this->redirect('http://twitter.com/oauth/authorize?oauth_token='.$requestToken->key);
この後、ユーザにTwitterの認証ページでログインしてもらいます。
4. Twitterから自サイトへリダイレクト
ログインに成功するか、認証の拒否をすると、$consumer->getRequestToken()の第二引数で指定したURLにリダイレクトされます。
認証に成功した場合、「$this->params['url']['oauth_token']」と「$this->params['url']['oauth_verifier']」に値が設定されます。
一方、認証を拒否した場合、「$this->params['url']['denied']」が設定されます。
$consumer=new OAuth_Consumer(取得したconsumer key,取得したconsumer secret); $requestToken=$this->Session->read('request_token'); $accessToken=$consumer->getAccessToken('http://twitter.com/oauth/access_token',$requestToken);
6. 取得したアクセストークンを使ってTwitterのAPIを実行
一度アクセストークンを取得してしまえば、そのアクセストークンを使って何度でもAPIを呼び出す事ができます。
// 自分のつぶやきを一つ取得 $tweet=$consumer->get($accessToken->key, $accessToken->secret, 'http://api.twitter.com/1/statuses/user_timeline.xml', array('count'=>1));
プログラム例
consumer keyとconsumer secretは自分で取得したものを使ってください。
<?php App::import('Vendor','oauth',array('file'=>'OAuth'.DS.'oauth_consumer.php')); class ExamplesController extends AppController { public $autoRender=FALSE; public $name='Examples'; public $uses=NULL; public function index() { $consumer=new OAuth_Consumer( 'XyPpN9KVd8xljAlafa00tsg', 'lLiQnseikjlajtrIJL3aosVRhLAKjl3jafRliLExFj0gOjlKjraebAu6z2p8'); // 認証後、「http://localhost/examples/exMain」にリダイレクトする $requestToken=$consumer->getRequestToken( 'http://twitter.com/oauth/request_token', 'http://localhost/examples/exMain'); // 認証後、アクセストークンを取得する際に必要なので保存 $this->Session->write('request_token',$requestToken); // Twitterの認証ページにリダイレクト $this->redirect('http://twitter.com/oauth/authorize?oauth_token=' .$requestToken->key); } // 認証後、このアクションが呼ばれる public function exMain() { // 認証を拒否したかどうか調べる if (isset($this->params['url']['denied'])) { echo 'access denied'; return; } $consumer=new OAuth_Consumer( 'XyPpN9KVd8xljAlafa00tsg', 'lLiQnseikjlajtrIJL3aosVRhLAKjl3jafRliLExFj0gOjlKjraebAu6z2p8'); $requestToken=$this->Session->read('request_token'); $accessToken=$consumer->getAccessToken( 'http://twitter.com/oauth/access_token', $requestToken); // 自分のつぶやきを一つ取得 $tweet=$consumer->get( $accessToken->key, $accessToken->secret, 'http://api.twitter.com/1/statuses/user_timeline.xml', array('count'=>1)); echo $tweet; } } ?>
安全になったRequestHandler->getClientIP()
RequestHandler->getClientIP()の事を調べていたら、RequestHandler->getClientIP()が返す結果は信用できないという記事を見つけました。
CakePHPのgetClientIPを使っていいのは小学生までだよねー
簡単に言うと、HTTP_X_FORWARDED_FORは簡単に偽装できるのに、HTTP_X_FORWARDED_FORに値が設定してあるとその値を返してしまうらしいです。
現在の最新版であるCakePHP 1.2.5ではどうなったかというと、対応されています。
function getClientIP($safe = true) {
if (!$safe && env('HTTP_X_FORWARDED_FOR') != null) {
$ipaddr = preg_replace('/(?:,.*)/', '', env('HTTP_X_FORWARDED_FOR'));
} else {
if (env('HTTP_CLIENT_IP') != null) {
$ipaddr = env('HTTP_CLIENT_IP');
} else {
$ipaddr = env('REMOTE_ADDR');
}
}
デフォルトの動作ではHTTP_X_FORWARDED_FORを無視し、引数としてFALSEを渡すと、従来通りHTTP_X_FORWARDED_FORを優先するようです。
actionにパラメータを渡す時に注意すべき文字
CakePHPでは「action名/値1/値2/...」 のような形式でアクセスすると、各値をactionの引数として渡す事ができます。しかし、文字によってはうまくいかない場合があるようなので、確認できた範囲内で書いておきます。
- #、%23 #又は%23以下が捨てられる
- %、%25 %又は%25の後に二文字あるとURLデコードされる。ない場合はアクションが呼ばれない
- &、%26 &又は%26以下が捨てられる
- %2B 空白になる
- %2F(/) アクションが呼ばれない
- %3A(:) :と同じ扱いになり、$this->params['named']に格納される
- ?、%3F ?又は%3F以下が捨てられる
日付時刻(2)
asctime_r()、ctime_r()、gmtime_r()、localtime_r()
char *asctime_r(const struct tm *tm,char *buf); char *ctime_r(const time_t *timep,char *buf); struct tm *gmtime_r(const time_t *timep,struct tm *result); struct tm *localtime_r(const time_t *timep, struct tm *result);
asctime()、ctime()、gmtime()、localtime()は静的に確保された領域を返します。これらの領域は、別の場所で呼び出された関数によって結果が上書きされる可能性があります。
#include <stdio.h> #include <time.h> int main() { char *s; time_t clock; struct tm *time_ptr; time(&clock); s=ctime(&clock); printf("ctime(1): %s",s); time_ptr=localtime(&clock); printf("asctime(1): %s",asctime(time_ptr)); clock=clock+1*60*60; // 一時間進める printf("asctime(2): %s",asctime(localtime(&clock))); // 一時間先の時刻を出力 printf("ctime(1): %s",s); // 元の時刻を出力 printf("asctime(1): %s",asctime(time_ptr)); // 元の時刻を出力 return 0; }
この結果は次の様になります。
ctime(1): Sat Feb 27 16:09:41 2010 asctime(1): Sat Feb 27 16:09:41 2010 asctime(2): Sat Feb 27 17:09:41 2010 <- 一時間後 ctime(1): Sat Feb 27 17:09:41 2010 <- 一時間後になってる!? asctime(1): Sat Feb 27 17:09:41 2010 <- 一時間後になってる!?
上書きされると困る場合は複製すれば良いのですが、マルチスレッド環境で同時に実行される可能性がある場合は次の関数を使います。
char *asctime_r(const struct tm *tm,char *buf); char *ctime_r(const time_t *timep,char *buf); struct tm *gmtime_r(const time_t *timep,struct tm *result); struct tm *localtime_r(const time_t *timep, struct tm *result);
二番目の引数に、結果を格納する為のバッファを渡します。asctime_r()とctime_r()で使うバッファは、最低でも26文字分必要です。
使い方
#include <stdio.h> #include <time.h> int main() { char s1[26],s2[26]; time_t clock; struct tm time_ptr1,time_ptr2; time(&clock); ctime_r(&clock,s1); printf("ctime_r(1): %s",s1); localtime_r(&clock,&time_ptr1); printf("asctime(1): %s",asctime(&time_ptr1)); clock=clock+1*60*60; // 一時間進める // 一時間先の時刻を出力 printf("asctime_r(2): %s",asctime_r(localtime_r(&clock,&time_ptr2),s2)); printf("ctime_r(1): %s",s1); // 元の時刻を出力 printf("asctime(1): %s",asctime(&time_ptr1)); // 元の時刻を出力 return 0; }
結果
ctime_r(1): Sat Feb 27 16:19:30 2010 asctime(1): Sat Feb 27 16:19:30 2010 asctime_r(2): Sat Feb 27 17:19:30 2010 <- 一時間後 ctime_r(1): Sat Feb 27 16:19:30 2010 <- 影響を受けてない asctime(1): Sat Feb 27 16:19:30 2010 <- 影響を受けてない
