‘アルゴリズム’ タグのついている投稿

アナグラム

2009年5月6日 水曜日

アナグラム (anagram) とは言葉遊びの一つで、単語または文の中の文字をいくつか入れ替えることによって全く別の意味にさせる遊びである。（Wikipediaより）

このとき、ひらがな/カタカナのアナグラムは見てすぐに分かるが、ローマ字のアナグラムは見てわかるものではない。

というわけで、ローマ字のアナグラムを生成するプログラムをRubyで組んでみた。


#!/usr/bin/ruby

$roman_jletter = /^(\s|[n]|[t][s][u]?|([kstcnhmrgzjdbp]?[y]?|[stcwd]?[h]?|[fw]?)[aiueo])*$/
$roman_jletter_process = /^(\s|[n]|[t][s][u]?|([kstcnhmrgzjdbp]?[y]?|[stcwd]?[h]?|[fw]?)[aiueo])*([t][s]|[kstcnhmrgzjdbp]?[y]?|[stcwd]?[h]?|[fw])?$/

class String
　def print_ano_name(tmp = '')
　　if self == '' then
　　　if tmp =~ $roman_jletter then
　　　　p tmp
　　　end
　　elsif tmp =~ $roman_jletter_process then
　　　i=0
　　　self.each_byte{|k|
　　　　if self.index(k.chr) == i
　　　　　(self[0...i] + self[(i+1)..self.length]).print_ano_name(tmp+k.chr)
　　　　end
　　　　i=i+1
　　　}
　　end
　end
end

ARGV[0].to_s.print_ano_name

注意としては、扱う文字が長くなると、計算時間が一気に長くなること。
上記プログラムに、文字列「takumi kanno」を与えたところ、95分かかっている。
プログラム内で少しは枝を切っている（＝途中で計算を打ちきることで、余分な計算をしないようにしている）が、文字列が長くなると、枝切りでも間に合わなくなる。

正規表現の与え方を工夫すれば計算速度は早くなりそうだが、計算量のオーダーに効いてこなさそうなのであんまし興味なし。

タグ:, ,
カテゴリー: 未分類 | コメントはまだありません »

エムリット捕獲大作戦・詳細

2009年3月1日 日曜日

エムリットを捕獲するため、いろいろと工夫をしたメモを残す。

・戦略
　ノズパスLv.35（結果としてダイノーズLv.37）に「せんせいのつめ」を持たせ、「とおせんぼ」で止める。「でんじは」でまひ状態にし、「いわくだき」でダメージを削りながら防御力を下げる。
　マニューラLv.56に切り替え、「みねうち」でＨＰを１にする。
　上記ノズパスに戻し、「とおせんぼ」を再度実施。あとは、ひたすらボールを投げる。

・条件
　エムリットが「わるあがき」をする前に勝負を決めねばならない。エムリットのわざとその回数は以下の通り。

　スピードスター　２０回
　おまじない　　　３０回
　みらいよち　　　１５回
　あまえる　　　　２０回

　すなわち、８５ターンの余裕があることになる。ただし、
　・まひ状態で多少稼げる。
　・マニューラのプレッシャーで１〜２ターン無駄になる。
　に注意する。

　なお、「とおせんぼ」はポケモンを入れ替えた瞬間に効果が切れることに注意。このとき、ポケモンを入れ替えたターンには向こうのポケモンがコマンド入力終わっているので、先手をとれば次のターンに１回だけ殴れる。

・確認

ポケゲット EX-G経由、ポケットモンスター情報センター２号館→ボールの計算式を利用。

係数 = ( ( ( 最大HP*3-現在HP*2 )*捕獲*ボール補正 ) / ( 最大HP*3 ) )*状態補正　（ただし、係数は1〜255の整数値に切り捨てされる）
閾値 = 0x000FFFF0 / ( √( √( 0x00FF0000/係数 ) ) )
捕獲率 = (閾値 / 0xFFFF)4

このとき、ポケゲット EX-Gのサイトに重要な事実が書いてある。

「ポケットモンスター情報センター」の式に基づいて計算した結果とここでの結果が違うような気がします。 （black_k_123殿より）

　特に携帯ゲーム機では、処理能力がおっつかないために、計算をはしょる場合があるんです。具体的には、小数点以下を常に切り捨てて計算を行います。つまり 5 ÷ 2 = 2 の世界です。ポケモン内部の捕獲を判定するプログラムも例に洩れず、それに従って計算されています。

　「ポケットモンスター情報センター」に書かれている式はこれを当たり前としているので、わざと表記を省略しているんですね。このことに気をつけて計算すると、うちの捕獲率計算機と同じ結果が出ると思います。ただし、切り捨てるタイミングで見落としがちな点があります。続けて次の項目も読んでみてね。

他の捕獲率を計算するプログラムで計算した結果と違う場合があるんですが。

　他の捕獲率を計算するプログラムでは、ちゃんと小数点の切り捨てを行っていますが、次の箇所で切り捨てを怠っているのを見たことがあります。

B = 000FFFF0 / ( √( √( 00FF0000/A ) ) )
※ポケットモンスター情報センターより引用

以上の式のルートを２回連続で行う部分において、一度に２回行った後に切り捨てていました。これは誤りで、ねんネン氏によれば、ルートを計算するルーチンもまた整数で答えを出してくるので、１回ルートを行う毎に切り捨てなければならないとのことです。よって、結果的に答えが違ってくるということです。

（太字は、いずれも菅野たくみによる）

　この事実をもとに閾値の計算式を見ると、平方根の計算→小数点の切り捨て、が２回発生していることに気がつくであろう。係数は１〜255の間しかありえないため、これは大きくないテーブルで捕獲率を表現できることを意味する。実際に三四郎きゅんに計算させたところ、２９列のテーブルで書けることがわかった（付表）。

伝説ポケモン（捕獲=3）、タイマーボール（ボール補正=4＠30ターンめ以降）、現在HP1、まひ（状態補正=1.5）、を前提に計算すると、41個のボールが必要と出た。

タイマーボール補正ターン（３０）＋ボール投げるターン（４１）＋回復とかに必要な予備（１０）＝８１＜８５、より、戦略の正しさが証明されたところで実行開始。

・実際のところ
　タイマーボール41個は確かにこの数持って行ったが、内情は計算値ではなく金銭問題 orz
　せんせいのつめ発動まで、５回くらい逃げられました。発動率を考えると、運はかなり良さげ。
　上記マニューラの切り替え時、「とおせんぼ」の効果を知らなかったので逃げられて焦った。
　計算式を読み間違えて４０ターン待ったため、クイックボール・ハイパーボールを無駄遣い。
　使ったタイマーボールは１０個くらいで、エムリット捕獲に成功。５割くらいの確率なので、これは運が良かった。

・結論
　エムリットかわいいよエムリット。
　ただ、エスパーポケモンのスロットには大好物のサーナイトが座っているので、使うのが難しい。うーむ。

付表：係数と捕獲率の対応表

係数 捕獲率 95％必要ボール数 補足
1 0.42% 719
2 0.83% 360
3 1.23% 242
4 1.60% 186
5 2.11% 141 伝説：ハイパーボール
6 2.56% 116
7 2.83% 105 伝説：麻痺＋ハイパーボール
8 3.14% 94
9 3.90% 76
10,11 4.37% 68 伝説：タイマーボール
12 4.90% 60 伝説：眠り＋ハイパーボール
13,14 5.53% 53
15 6.25% 47
16-18 7.10% 41 伝説：麻痺＋タイマーボール
19,20 8.09% 36
21-23 9.27% 31
24-27 10.66% 27 伝説：眠り＋タイマーボール
28-31 12.33% 23
32-36 14.34% 20
37-42 16.78% 17
43-50 19.75% 14
51-59 23.42% 12
60-71 27.97% 10
72-85 33.69% 8
86-104 40.96% 6
105-128 50.28% 5
129-159 62.42% 4
160-200 78.46% 2
201-255 99.99% 1

タグ:, ,
カテゴリー: 未分類 | 2件のコメント »

キャラメリック・バウト・オンライン・オフライン会

2008年6月30日 月曜日

いろいろと仕事や作業の忙しかったところ、一段落したところで、「きゃらばと！オンライン」関連にて、仙台の知り合い宅へ遊びに行っていました。

仙台へ旅行ということで、一日は松島観光、一日はまったりと身内遊びして、騒ぎながら楽しんだ一泊二日の旅行でした。

詳細は関係者向け専用に後日公開する予定です。

問題）
　カードの集合Ｕのうち、属性Ａを持つものをＸ枚、属性Ｂを持つものをＹ枚、属性Ｃを持つものを（３０−Ｘ−Ｙ）枚取り出し、３０枚のカードの束を作る。
　（１）この問題の欠点を指摘し、妥当な解決案を示せ。
　（２）上記を実現するアルゴリズムのうち、後戻りがないものを示せ。

　この問題についても、関係者向け専用の詳細レポートの中で解答を示します。他に知りたい人がいたら直接ご連絡いただくか、blogにコメントください（ただし、レポート記述完了後の対応になります）。

タグ:, ,
カテゴリー: 未分類 | 1件のコメント »

nCr

2007年7月12日 木曜日

数学の「組み合わせ」の記号。
Excelでこの記号を使うと、カードゲームの土地事故率がきれいに解けます。

n枚のデッキで、引きたいカードがm枚入っている。
１）初期手札＋現在のドローの総計がr枚のとき、そのうち引きたいカードをi枚引くことが出来る確率は、

mCi * (n-m)C(r-i) / nCr

で表すことが出来る（Eric Tam, 1998）。
２）初期手札＋現在のドローの総計がr枚のとき、そのうち引きたいカードをi枚以上引くことが出来る確率は、

Σ_k=i to r {mCk * (n-m)C(r-k)} / nCr

で表すことが出来る。

Excelを使い込んで上の式をシートにする（組み合わせnCrは関数Combin(n, r)で表されます）と、デッキの事故率が非常にわかりやすく表示されます。

そして、うどんげが厳しいという事実が、改めて浮き彫りになるわけです orz（スペル23枚が８ターン止まらない確率が６４％しかない。フランでスペル22枚が４ターン止まらない確率は実に９３％）

タグ:,
カテゴリー: 未分類 | コメントはまだありません »

円周率

2006年5月28日 日曜日

＜経緯＞
会社の研修で、Ｃ言語を勉強しているのだが、内容が基礎的ゆえ全部『教えた』経験のある事柄ばかり、という暇っぷり。

んで、しゃーないので与えられた課題を、おかしな方法で解くことにする……ループ命令をいっさい使わず、再帰関数とif文でループをくむというやり方である。

これで、ほとんどの課題はうまくいったのだが、たったひとつうまくいかない課題があった。
「円の半径をコマンドライン引数からとって、円の面積を表示するプログラムを作れ」というものである。
一見簡単そうに見えるが、実は円周率πを正しく求めるのに、かなりの調査を要した。
まず最初に、小学生でもわかる求め方の一つとして、円とそれに外接する正方形の比をとる方法を２種類実装した。ひとつはランダムな点を打って、円の中か外かを判断することで、大数の法則に期待して円周率を求めるというやり方（モンテカルロ法という）。もうひとつは正方形の中にメッシュを張って、メッシュの各点が円の中にあるかどうかを判定するやり方。
要するに、どちらもCPUパワーに任せた、力づくのやりかたなわけだが、ループ命令を使わないデメリットがもろに出てしまう結果になった……すなわち、精度を上げようとループ回数を増やすと、スタック・オーバーフローによるエラーでプログラムが落ちてしまうのだ。

で、Wikipediaに頼って円周率を効率よく探すアルゴリズムを探してみると、「円周率の歴史」ページに、そのアルゴリズムがあった。

1995年9月19日午前0時29分

カナダのサイモン・フレイザー大学において、デビット・H・ベイリー、ピーター・ボールウェイン、サイモン・プラウフの研究チームが無限級数
¥pi = ¥sum_{k = 0}^{¥infty} ¥frac{1}{16^k} ¥left( ¥frac{4}{8k + 1} – ¥frac{2}{8k + 4} – ¥frac{1}{8k + 5} – ¥frac{1}{8k + 6}¥right)
を発見する。この式では2進表示または16進表示で n – 1 桁までを求めずに n 桁目以降の π の値を計算できる。ベイリーのウェブサイトで様々なプログラミング言語用の実装例を見ることができる。

これは、コンピュータ上において「桁数を区切って」円周率を求めることが可能という、画期的アルゴリズム。数式がTeXソース形式で読みづらいのはご愛敬。
このアルゴリズムの収束の早さに助けられ、私は無事円周率を再帰関数で求めることができた。私の「おかしな方法でプログラムを組む」というポリシーはこうして守られたのだ。

＜主張＞
で、ベイリー氏のサイトから。

あなたの名前が、円周率のどこの桁にあるか探してみませんか？
という、氏の円周率アルゴリズムの特長を生かした、すてきなお誘いが。

というわけで、実際に探してみた。

search string = “takumi”
30-bit binary equivalent = 101000000101011101010110101001

search string found at binary index = 3336826008
binary pi : 0110011010100000010101110101011010100101001100110011100111110010
binary string: 101000000101011101010110101001
character pi : up;ljm,rl;dwqnmsftakumiisggyhd;jlcx;wc
character string: takumi

というわけで、33億3682万6008桁めに私の名前があることが、このアルゴリズムにより明らかにされた。

あなたも、円周率の数字の奥深くに、自分の名前が隠されているかもしれません。ひとときの思い出のために、英語をおそれずに、少しの時間を使って、試してみるのはいかがでしょう？

タグ:, , ,
カテゴリー: 未分類 | コメントはまだありません »