PamGau

裸の英会話

Wed, 8 Jul 2009 23:57:45 +0900

先日、外国の知人(♂)とともに風呂屋に行きました。湯船に浸っていると、"What's that?"との問いが彼から発せられました。

私、やや食い気味に答えて曰く、"The guard of Buddha. He manipulates the flame."

「や」のつく自由業の方かどうかしりませんが、背中に不動明王を背負ってらっしゃったのを事前に確認し、子供の頃に近所の爺さんから聞いたことをそのまま云ってみただけでした。

ただ、その答えが正しかったかどうかに自信がなく、調べてみました。

釈迦が成道の修業の末、悟りを開くために「我、悟りを開くまではこの場を立たず」と決心して菩提樹の下に座した時、世界中の魔王が釈迦を挫折させようと押し寄せたところ、釈迦は穏やかな表情のまま降魔の印を静かに結び、魔王群をたちまちに超力で降伏したと伝えられるが、不動明王はその際の釈迦の内証を表現した姿であるとも伝えられる。穏やかで慈しみ溢れる釈迦も、心の中は護法の決意を秘めた鬼の覚悟であったというものである。

うーん、釈迦の内証を表現した姿だとは知りませんでしたが、まあ間違ってはいないかなぁ…。年寄りの話はよく聞いておくものです。

RubyでProject Euler - Problem 59

Tue, 23 Jun 2009 22:17:00 +0900

Problem 59 (Project Euler) [原文]

暗号化鍵は3文字の小文字である. cipher1.txtは暗号化されたASCIIのコードを含んでいる. また, 平文はよく用いられる英単語を含んでいる. この暗号文を復号し, 平文のASCIIでの値の和を求めよ.

ちょっとしたハッカー気分でどうぞ。

要は、英小文字3文字からなるパスワードを用意し、先頭バイトからXOR演算を繰り返し行って、文字に復号してみろ…ということです。

まず先頭の何文字か分だけを復号し、「ありふれた英単語」が含まれるか否を確認してパスワードを決定します。全てを復号して答えを求めるのはその後がよさそうです。

最初に何バイトぐらいを復号するか、また「ありふれた英単語」として何を選ぶのかの２点で少し試行錯誤が必要でした。わかってしまえばなんでもないのですけど…。

復号後の"cipher1.txt"はちょっと意地悪な書き出しになっています。

RubyでProject Euler - Problem 58

Tue, 23 Jun 2009 21:45:00 +0900

Problem 58 (Project Euler) [原文]

1から初めて, 以下のように反時計回りに数字を並べていくと, 辺の長さが7の渦巻きが形成される.
(中略)
面白いことに, 奇平方数が右下の対角線上に出現する. もっと面白いことには, 対角線上の13個の数字のうち, 8個が素数である. ここで割合は8/13 ≒ 62%である.

渦巻きに新しい層を付け加えよう. すると辺の長さが9の渦巻きが出来る. 以下, この操作を繰り返していく. 対角線上の素数の割合が10%未満に落ちる最初の辺の長さを求めよ.

Problem 28で扱った螺旋数列の問題で、手間が省けて簡単かと思いきや、さすがにこのレベルの問題はひとひねりがあります。

「エラストテネスの篩」はせいぜい400万ぐらいまでを用意すればよかろうと思ったら、篩で用意した素数の範囲を超えても、なかなか10%を割りません。

5千万ぐらいまで確保しようとしたところで、当然のことながら、必要なメモリ領域を確保できなくなりました。

やむなく「ミラー・ラビン」でググると、親切にもWikipediaに素数判定用のRubyコードがあったのでコピペしました。敗北感にまみれながら…orz

ミラー-ラビン素数判定法 (Wikipedia)

RubyでProject Euler - Problem 57

Tue, 23 Jun 2009 00:45:50 +0900

Problem 57 (Project Euler) [原文]

2の平方根は無限に続く連分数で表すことができる.

√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + … ))) = 1.414213…

(中略)

第8項は1393/985である. これは分子の桁数が分母の桁数を超える最初の例である.

最初の1000項を考えたとき, 分子の桁数が分母の桁数を超える項はいくつか?

とりあえず、連分数部分の分母・分子の数列をそれぞれ a_n, b_n とすると、以下の漸化式が成立します。

a_n = 2a_n-1 + b_n-1, a₁ = 2
b_n = a_n-1, b₁ = 1

プログラムで漸化式を扱う場合、そのまま関数にすると再帰呼び出しによる再計算量が異常に多くなり、実行効率が激減します。

メモリを上手に使うのがうまいやりかたでしょう。

  seq_a = [2] # 分母
  seq_b = [1] # 連分数部分の分子
  ans = 0       # カウンタ

  (1..1000).each do |i|
    seq_a << seq_a[i-1] * 2 + seq_b[i-1]
    seq_b << seq_a[i-1]
    ans += 1 if seq_a[-1].to_s.length < (seq_a[-1] + seq_b[-1]).to_s.length
  end
  puts ans

RubyでProject Euler - Problem 55, 56

Mon, 22 Jun 2009 23:16:45 +0900

初の複数問掲載記事。

Problem 55 (Project Euler) [原文]

10000未満のLychrel数の個数を答えよ.

50回も題意の処理をしても回文数が表れなければ、Lychrel数と見做しても差し支えないという条件をつけられているので楽です。

案外、Lychrel数は多いです。また、Lychrel数でありながら、回文数でもある数も他に見つかりました。

Problem 56 (Project Euler) [原文]

a, b < 100について自然数 a^b を考える. 桁の和の最大を答えよ.

云われた通りやるだけです。

各桁の総和を求める関数を下のように書きました。

  def sum_digits(n)
    n.to_s.split(//).inject(0){|s,v|s+v.to_i}
  end

RubyでProject Euler - Problem 54

Mon, 22 Jun 2009 21:16:04 +0900

Problem 54 (Project Euler) [原文]

poker.txtには1000個のランダムな手札の組が含まれている. 各行は10枚のカードからなる (スペースで区切られている): 最初の5枚がプレイヤー1の手札であり, 残りの5枚がプレイヤー2の手札である. 以下のことを仮定してよい

全ての手札は正しい (使われない文字が出現しない. 同じカードは繰り返されない)

各プレイヤーの手札は特に決まった順に並んでいるわけではない

各勝負で勝敗は必ず決まる

1000回中プレイヤー1が勝つのは何回か?

問題文の引用は一部だけにとどめました。

独りポーカーなんかでは各役に以下のような得点をつけることがあります。

005点 : ワンペア
010点 : ツーペア
015点 : スリーカード
020点 : ストレート
025点 : フラッシュ
030点 : フルハウス
050点 : フォーカード
080点 : ストレートフラッシュ
100点 : ロイヤルストレートフラッシュ

こうした問題で見通しをよくするにはクラスを作ってしまうことでしょう。

カード単体(Card)とカードを5枚保持する手札(Hands)とにそれぞれ相当するクラスがあれば十分です。

カード単体相当のクラスを作ると、"initialize"が使えるだけでもファイル読み込みの処理が随分楽になります。

また、5枚のカードを保持する手札相当のクラスでは"initialize"と同時に役相応の点数を計算保持するとともに、他者との勝負判定用に不等号演算子の再定義も行いました。

同役の際の勝負判定には役に関わるカードの数値が使われるので、当該数値を上記の得点の小数点以下に埋め込みます。

ちょっと処理が面倒だったのが、同役同数値の場合の勝負判定でした。役に付随するカード以外のカードの数値に基づいて判定されるので、役の点数とは別のインスタンス変数を設けました。

"poker.txt"は完全にランダムに作成されたらしく、無役の割合が多くて、高い役はありませんでした。なお、同ファイル中、"10"は"T"と1文字で表記されています。

RubyでProject Euler - Problem 53

Sun, 21 Jun 2009 21:49:50 +0900

Problem 53 (Project Euler) [原文]

12345から3つ選ぶ選び方は10通りである.

123, 124, 125, 134, 135, 145, 234, 235, 245, 345.

組み合わせでは, 以下の記法を用いてこのことを表す: ₅C₃ = 10.

一般に, r <= n について_nC_r = n!/(r!(n-r)!) である. ここで, n! = n×(n-1)×...×3×2×1, 0! = 1と階乗を定義する.

n = 23になるまで, これらの値が100万を超えることはない: ₂₃C₁₀ = 1144066.

1 <= n <= 100について, 100万を超えるnCrは何通りか?

Rubyに関する限り、この程度の問題で数値のオーバーフローを気にする必要はありません。導入も親切な問題ですし、そのまま書いて終わりです。

スペースが余ったのでコードを載せます。

  def fact(n)  # 階乗
    return 1 if n == 0 || n == 1
    (2..n).to_a.inject(1){|v, i| v*i}
  end

  def combination(n, r) # 組み合わせ(コンビネーション)
    fact(n) / (fact(r) * fact(n-r))
  end

  cnt = 0

  (1..100).each do |n|
    (1..n).each do |r|
      cnt += 1 if combination(n, r) > 100_0000
    end
  end

  puts cnt

RubyでProject Euler - Problem 52

Sun, 21 Jun 2009 21:48:24 +0900

Problem 52 (Project Euler) [原文]

125874を2倍すると251748となる. これは元の数125874と同じ数を含む.
2x, 3x, 4x, 5x, 6xがxと同じ数を含むような最小の正整数xを求めよ

求める正の整数xは、6倍しても桁数が増えないことにまず気づきます。

また5倍しても同じ数を含むのですから、xの各桁のいずれかには0か5かは含まれます。

3倍しても同じ数を含むのですから、各桁の総計は3の倍数であって、xも3の倍数です。

というわけで、ざっと考えると上の太字の条件を確認しつつ、下記のような範囲の整数を「3つ飛ばし」で走査していけばよいことになります。

3桁 : 102 - 165
4桁 : 1002 - 1665
5桁 : 10002 - 16665
6桁 : 100002 - 166665
7桁 : 1000002 - 1666665
8桁 : 10000002 - 16666665
9桁 : 100000002 - 166666665

問題文には各桁の数字が全て異なるか否かについての言及はありませんので、この際無視しました。

RubyでProject Euler - Problem 51

Sun, 21 Jun 2009 21:46:47 +0900

Problem 51 (Project Euler) [原文]

*57の第1桁を置き換えることで, 157, 257, 457, 557, 757, 857という6つの素数が得られる.

56**3の第3桁と第4桁を同じ数で置き換ることを考えよう. この5桁の数は7つの素数をもつ最初の例である: 56003, 56113, 56333, 56443, 56663, 56773, 56993. よって, この族の最初の数である56003は, このような性質を持つ最小の素数である.

桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ. (注:連続した桁でなくても良い)

素数大好きオイラー先生。右の本はGoogleの書籍検索でプレビューが提供されています。

さて、ある数の各桁の和が３の倍数であれば、元の数字も３の倍数であることはよく知られています。

この事実を踏まえると、求める素数に設けられる"*"は３の倍数個でなければならないことが判明します。その理由は次の通りです。

"*"に当てる数字を、0から9のうちからどのように選ぼうとも、8つもあると3による剰余系(mod 3)の0, 1, 2の全てを満たすことになります。従って、"*"が３の倍数個でなければ、"*"にこれらの数字を順次当てはめていくうちに3の倍数ができてしまい、元の数が素数であるという条件を満たすことがないからです。

問題には「最小の」とあるのですから、さし当たっては"*"は3個に限定して、以下のような処理手順で書くことにしました。

100万までの素数配列を作成
同じ数字を3個以上含む素数に限定
各素数の同一の数の桁に"*"マスクをかけた文字列に置換
同一文字列が8個ある組み合わせを特定

ここで面倒だったのが、同じ数字が4個以上ある素数に"*"マスクをかける処理でした。同じ数字が都合4桁ある素数に対しては3個、同じく5桁に対しては10個のマスクされた文字列を作らなければなりません。

完成したプログラムを走らせると20秒ぐらいで答えが出ましたが、正解にこぎつけるまでに要した時間はその何倍か…。

結局、今回は数学というよりも、Rubyでの文字列処理の問題だったように感じます。

RubyでProject Euler - Problem 50

Fri, 19 Jun 2009 21:02:00 +0900

Problem 50 (Project Euler) [原文]

素数41は6つの連続する素数の和として表せる:

41 = 2 + 3 + 5 + 7 + 11 + 13.

100未満の素数を連続する素数の和で表したときにこれが最長になる.

同様に, 連続する素数の和で1000未満の素数を表したときに最長になるのは953で21項を持つ.

100万未満の素数を連続する素数の和で表したときに最長になるのはどの素数か?

2を先頭要素とする素数配列:$p_listとします。$p_listの先頭要素から順次各要素を加算して求められる部分和が初めて100万を超えるときの要素のインデックスは546です。

従って、題意の項数を目一杯大きく見積もっても547個であり、実際にはこれ以下の項数でしか表せないことがわかります。

ですから、この項数を順次減らすとともに加算の起点となる素数をずらすことで、題意の素数を探索していくという方針にしました。

また、項数は必ず奇数であることに注意します。これを忘れるとどえらいことになります(笑)

Level 2 到達を記念して小汚いコードを曝します。汚いけど実行速度は悪くないと思います。