2011-05-28

LLセットでコーラ缶グラスをコンプリート

数学

某ハンバーガーチェーンMでLLセットを頼むとコーラ缶型のグラスをもらえるキャンペーンをやってるらしい、と言うのを耳にして実際に行ってみた。
どうやら3色の中からランダムらしく、緑を入手。
あと2色もらうには何食LLセット食べればいいかなと思い、確率計算してみました。

「試行ごとに3種類の中からランダムで手に入る。 $n$ 回目に3種類全て手に入っている確率を求めよ。3種類は相当数用意されており、残数を考慮せず常に各種 $\frac{1}{3}$ の確率で手に入るとする。」こんなモデルでいいでしょう。

$a_n$ を $n$ 回目に1種類手に入っている確率として、同様に $b_n$ を2種類、 $c_n$ を3種類とします。 $(n\geq1)$
求めるのは $c_n$ というわけです。
ちなみに $n$ 回目ちょうどに3種類揃った確率ではなく、 $n$ 回目以前に3種類揃う確率です。もし前者が求めたければ $c_n-c_{n-1}$ で求められます。

明らかに $a_1=1,{\quad}b_1=c_1=c_2=0$ です。
漸化式立てると、
$a_{n+1}=a_n\cdot\frac{1}{3}$ $\cdots\quad(1)$
$b_{n+1}=a_n\cdot\frac{2}{3}+b_n\cdot\frac{2}{3}$ $\cdots\quad(2)$
$c_{n+1}=b_n\cdot\frac{1}{3}+c_n$ $\cdots\quad(3)$
となり、確率なので当然
$a_n+b_n+c+n=1$ $\cdots\quad(4)$
も任意のnに対して成り立ちます。

蛇足ながら解説を少しすると、
$(1)$ は(前回( $n$ 回目)に1種類だった確率 $a_n$ ) $\times$ (今回( $n+1$ 回目)同じ1種類を入手する確率 $\frac{1}{3}$ )。
$(2)$ は( $n$ 回目に1種類だった確率 $a_n$ ) $\times$ ( $n+1$ 回目に異なる2種類のいずれかを入手する確率 $\frac{2}{3}$ )
$+$ ( $n$ 回目に2種類だった確率 $b_n$ ) $\times$ ( $n+1$ 回目に入手済みの2種類のいずれかを入手する確率 $\frac{2}{3}$ )
$(3)$ は( $n$ 回目に2種類だった確率 $b_n$ ) $\times$ ( $n+1$ 回目に最後の1種類を入手する確率 $\frac{1}{3}$ )
$+$ ( $n$ 回目に既に3種入手済みの確率 $c_n$ )

さて解いていきます。
$(1)$ からほぼ自明に、
$a_n=(\frac{1}{3})^{n-1}$ $\cdots\quad(5)$
$(2),\quad(5)$ より
$b_{n+1}=\frac{2}{3}\{b_n+(\frac{1}{3})^{n-1}\}$
両辺 $3^{n+1}$ かけて
$3^{n+1}{\cdot}b_{n+1}=2(3^n{\cdot}b_n+3)$
両辺 $6$ 加えて
$3^{n+1}{\cdot}b_{n+1}+6=2(3^n{\cdot}b_n+6)$
$3^n{\cdot}b_n+6=6\cdot2^{n-1}$ $\cdots\quad(6)$
$3^n{\cdot}b_n=6(2^{n-1}-1)$
$b_n=\frac{2(2^{n-1}-1)}{3^{n-1}}$ $\cdots\quad(7)$

$(6)$ の手前で少しサボりましたが、 $d_n=3^n{\cdot}b_n+6$ とおくと $d_{n+1}=2d_n,{\quad}d_1=6$ となりますので $(6)$ が導けます。

さて $a_n$ , $b_n$ が求まったので $(4),\quad(5),\quad(7)$ より
$c_n=1-(\frac{1}{3})^{n-1}-\frac{2(2^{n-1}-1)}{3^{n-1}}$
$\quad=1-\frac{2^n-1}{3^n-1}$
このままでもいいですが少し整理して
$c_n=\frac{3^{n-1}-2^n+1}{3^{n-1}}$

さてある程度計算してみるとこんな感じに。(百分率を小数第2位で四捨五入)

$n$	3	4	5	6	7	8	9	$\cdots$
$c_n(%)$	22.2	44.4	61.7	74.1	82.6	88.3	92.2	$\cdots$

5,6食で全種類制覇できそうですね。
実際には某Mのポテトがあまり好きじゃないので数年ぶりの1食で十分でしたが。

いい頭の体操になりました。いまの学習要領知りませんが自分の頃、数列と漸化式と確率習うのは高校2年ぐらいでしょうか。
たまに数字と戯れるのは楽しいですね。
昔livedoor blog使ってたころに数式をtableタグで組んだことがありますが、はてなダイアリーはtex記法が使えるので数倍楽でした。

2010-08-24

Pac-Manシミュレーター改

JavaScript Google

twitterの#devquizや#gdd2010jpにいろんな方の回答が上がってきたのでトレース機能を追加。

[twitter:@tet_rw]な人の581点の動きが素晴らしい。
HとVの誘導が絶妙。

http://www.mizote.com/gdd2010pacman.html

矢印:自機移動(キーアサイン:カーソルまたはhjkl)
・:足踏み(キーアサイン:ピリオド(テンキーも))
1,2,3:ステージ切り替え(キーアサイン:1,2,3(テンキーも))
R:Reset(キーアサイン:r,テンキー0)
U:Undo(キーアサイン:u)
S:Save,サーバー側にいるPHPに送るだけの自分仕様(キーアサイン:s)
T:Traceコマンド群入力で自動実行(キーアサイン:t)
Normal/IgnoreVH/IgnoreAll:当たり判定の有無
- Normalは通常の当たり判定
- IgnoreVHはR,L,Jのみ判定
- IgnoreAllは判定なし(=無敵)

2010-08-23

CakePHPのURLエンコード

PHP CakePHP Apache

CakePHPではapp/webroot/.htaccessに

RewriteEngine On
RewriteCond %{REQUEST_FILENAME} !-d
RewriteCond %{REQUEST_FILENAME} !-f
RewriteRule ^(.*)$ index.php?url=$1 [QSA,L]

という記述があり、オリジナルのURLを$_GET['url']にいれた状態でRouterに渡す。
ここで、問題が発生するのがオリジナルのURLに+や%40などのエスケープされた文字が入っていた場合、mod_rewrite上で案エスケープされてしまう為、元の文字列が取得できない。

もっともシンプルな解決法はApacheの2.2.6以降に準備されているRewrite RuleのBフラグ。

'B' (escape backreferences)
Apache has to unescape URLs before mapping them, so backreferences will be unescaped at the time they are applied. Using the B flag, non-alphanumeric characters in backreferences will be escaped. For example, consider the rule:
RewriteRule ^(.*)$ index.php?show=$1
This will map /C++ to index.php?show=/C++. But it will also map /C%2b%2b to index.php?show=/C++, because the %2b has been unescaped. With the B flag, it will instead map to index.php?show=/C%2b%2b.
This escaping is particularly necessary in a proxy situation, when the backend may break if presented with an unescaped URL.

とあるように、先ほどの.htaccessの最後の行を

RewriteRule ^(.*)$ index.php?url=$1 [QSA,L,B]

とすればエスケープしてくれる。

残念ながらApahceを2.2.6以上にできない場合はhttpd.confを触れれば
下記の様な解決法も。
httpd.confで

RewriteLock /tmp/httpd.rewrite.lock
RewriteMap urlencode prg:/etc/httpd/conf.d/bin/urlencode.pl

としておいて.htaccessは

 RewriteRule ^(.*)$ index.php?url=${urlencode:$1} [QSA,L]

RewriteMapで外部スクリプトにエンコードさせるわけです

今回は手っ取り早く下記Perl スクリプトを試しましたが速度的にはオススメできません

#!/usr/bin/perl
$| = 1;
while (<STDIN>) {
  s/\n$//;
  s/([^\w ])/'%'.unpack('H2', $1)/eg;
  tr/ /+/;
  print "$_\n";
}

参考にしたサイト

mod_rewrite - Apache HTTP Server
- http://httpd.apache.org/docs/2.2/mod/mod_rewrite.html#rewriterule

2010-08-23

GDD2010JPのDevQuizで使ったPac-Manシミュレーター

JavaScript Google

回答期間も終わったので公開。
少しずつ機能足したので節制無いソースですがご容赦を。
http://www.mizote.com/gdd2010pacman.html

矢印:自機移動(キーアサイン:カーソルまたはhjkl)
・:足踏み(キーアサイン:ピリオド(テンキーも))
1,2,3:ステージ切り替え(キーアサイン:1,2,3(テンキーも))
R:Reset(キーアサイン:r,テンキー0)
U:Undo(キーアサイン:u)
S:Save,サーバー側にいるPHPに送るだけの自分仕様(キーアサイン:s)
Normal/IgnoreVH/IgnoreAll:当たり判定の有無
- Normalは通常の当たり判定
- IgnoreVHはR,L,Jのみ判定
- IgnoreAllは判定なし(=無敵)

提出スコアは41, 226, 512でした。
580ぐらいの猛者のコマンドもちらほら見かけるのでトレース機能追加しようかと思ってます

2010-08-18

GDD2010Jp-DevQuiz完了

Google JavaScript

お盆の帰省とちょうど時期がかぶったので充実した暇つぶしを。
無事完了。

JavaScirptでPAC-MANシミュレータ実装したり、楽しいひと時でした。
せっかくなので回答期間(〜8/23 10:00)終了後、公開しようと思ってます。

2009-11-14

シンボルテーブルとmy

Perl

my,our,localについて勉強しなおしていて下記サイトのコードサンプルを実行中に疑問がわいたので記す。

Perl/codepiece/my_and_locals1 - Glamenv-Septzen.net
- http://www.glamenv-septzen.net/view/139

こちらmyの挙動を試しているのが下記。(以下：コードmy1)

「myによる字句解析的(lexical)なスコープ決定」コードピース(1)
- http://www.glamenv-septzen.net/view/139#ideef3e3

#!/usr/bin/perl

my $compile_time = 123;
$compile_time = 456;

print join " ", keys(%::);
print "\n----------\n";
print "main::compile_time = [", $main::compile_time, "]\n";
print "::compile_time = [", $::compile_time, "]\n";
print "compile_time = [", $compile_time, "]\n";

これを実行しシンボルテーブルには存在するのにアクセスできないとしている。

その後でてくるパッケージ切り替えとmyの挙動の試行。(以下：コードtry5)

「大量のtry&errorの果てに。」コードピース (5) : 同じファイル中で、パッケージを切り替えてmyをするとどうなるか。
- http://www.glamenv-septzen.net/view/139#id2fa29c

#!/usr/bin/perl

print "package=[", __PACKAGE__, "]\n";
print '%:: = ', join(" ", keys(%::)), "\n";
print '%hoge:: = ', join(" ", keys(%hoge::)), "\n";

my $var1;
$var1 = "abc";

この実行結果として%:: = にvar1が出てこず当然、とされているのだがこれが気になった。

コードmy1とコードtry5との差を考え、下記コードを実行。

#!/usr/bin/perl

my $compile_time = 123;
$compile_time = 456;

print join " ", keys(%::);

これがコードmy1におけるコードtry5とほぼ同等のコードでる。
実行してみるとシンボルテーブルにcompile_timeは存在しない。

オリジナルのコードmy1においてシンボルテーブルにcompile_timeが存在した理由は、シンボルテーブルの参照後に

print "main::compile_time = [", $main::compile_time, "]\n";

または

print "::compile_time = [", $::compile_time, "]\n";

として、表示のためにcompile_timeを参照した際にシンボルテーブルにも書き込まれたというのが結論のようだ。
これは下記でも述べられているようにコンパイル時にシンボルテーブルに書かれるのでコードの後半にパッケージ変数の参照があって冒頭でシンボルテーブル一覧を表示すると載っているのは自然な挙動だ。

グローバル変数（パッケージのシンボルテーブルとソフトリファレンス）
- http://www.glamenv-septzen.net/view/139#idaceaf2

他人のサイトの指摘に終始してしまったが、大変勉強になりました。
msakamoto-sfさんありがとうございます。

なんとなく適当に俺々ツール作りに使っている、perl。奥が深い。
my,our,localの勉強はまだ完了してないので、理解し終えてから別エントリとしたい。

参考にしたサイト

上記サイトはコメント、トラックバックができないようなので、同一著者のはてダにTB。

my, our, local - ぐらめぬ・ぜぷつぇんのはてダ
- http://d.hatena.ne.jp/msakamoto-sf/20080110/1199940725

元々はここのトラックバックで見つけた記事。

404 Blog Not Found:perl - myとourとscopeと
- http://blog.livedoor.jp/dankogai/archives/50982802.html

2009-04-22

XML1.0にvalidな文字列の出力

XML PHP

RSSパーサーを使っていて、たまに外部のblogサービス*1のRSSが変な文字を含んでいてパースできないことがあるので、XMLの仕様を再確認してみた。

許可されるのはC0制御文字集合(0x00〜0x1f)のう水平タブ=HT(0x09), 改行=LF(0x0a), 復帰=CR(0x0d)とC1制御文字集合(0x80〜0x9f)、あと削除=DEL(0x7f)。

ただしXML1.1ではC1制御文字集合のうち0x85以外*2はinvalidに。

0x00と改行文字以外の制御文字(0x01〜0x08, 0x0b〜0x0c, 0x0e〜0x1f, 0x7f〜0x84, 0x86〜0x9f)は文字参照 *3として記述可能

自前で出力してるコードで同様のケースがないようにXML1.0としてinvalidな制御文字を除去するPHPコード。

mb_regex_encoding('UTF-8');
$str = mb_ereg_replace('[\x00-\x08\x0b\x0c\x0e-\x1f]', '', $str);

今回参考にしたサイトのURL

＠IT：XML 1.1を分析する
- http://www.atmarkit.co.jp/fxml/tanpatsu/37xml11/xml1101.html

*1:seesaaのRSSに含まてれるケースがよくある(tinymceのせい？)

*2:0x85は改行文字に追加(メインフレームの改行文字NEL)

*3:例:&#99