« 2009年7月 | トップページ | 2009年9月 »

2009年8月

2009年8月31日 (月)

Project Euler - Problem 59

問題はこちらをご覧ください。


面倒くさそうだったので、しばらくほったらかしにしていたのですが、「暗号解読」(サイモン・シン著)を読んだら解法のヒントがあったので、解いてみました。

「ある程度の長さをもつ普通の英文」の場合、"e" が最頻出文字であることが分かっています。

今回の暗号は 3 文字のキーワードが使われているので、暗号化された文章を三文字おきにグループ分けすると、その中のグループの頻出文字に "e" が含まれていることが予想されます。

そこで、それぞれのグループの出現頻度の高い順に 5 つの文字を拾い上げて、それが "e" だったと仮定してキーワードの文字を推測してみました。

今回は元の文字のコードをキーワードのコードと "xor" することで暗号化しているので、暗号化された文字のコードと元の文字のコードを "xor" するとキーワードのコードが返ってきます。

# -*- coding: utf-8 -*- # # = 鍵となる文字を探す # class Array # == 数字の出現頻度を数え上げて、多い順に並べて返す。 def count h = Hash.new(0) self.each do |n| h[n] = h[n] + 1 end return h.to_a.sort_by{|a| a[1]}.map{|a| a[0]}.reverse end end cipher_text = open("cipher1.txt"){|file| file.read} cipher_arr = cipher_text.split(",").map{|str| str.to_i} # text_arr を鍵の同じ文字に対応する 3 つの部分に分ける。 part = Array.new 3.times{|i| part[i] = Array.new} cipher_arr.each_with_index do |n, i| part[i % 3].push(n) end # 各パートで頻出する 5 文字を "e" に見立てて鍵の文字を推測する。 part.each do |arr| p arr.count.take(5).map{|n| (n ^ "e".ord).chr} end

今回の文章はあまり長い文章ではなかったので、さすがに "e" が最頻出とはなっていませんでしたが、それらしいキーワードを想定するだけの材料にはなりました。


それでは、キーワードが分かったところで、暗号文を復号してみましょう。

# -*- coding: utf-8 -*- # # = 暗号文を解読する # cipher_text = open("cipher1.txt"){|file| file.read} cipher_arr = cipher_text.split(",").map{|str| str.to_i} key_word = "***" # "***" の代わりに鍵となる 3 文字を入れる。 key = key_word.split("").map{|i| i.ord} arr = Array.new cipher_arr.each_with_index do |n, i| arr.push(n ^ key[i % 3]) end plain_text = arr.map{|i| i.chr}.join puts arr.inject(:+) puts plain_text

正しく復号されれば、数字と聖書の一節が英文で表示されるはずです。


ところで、今回は三つのグループのいずれでも "e" が最頻出文字となっていませんでした。

そこで、最頻出文字は何だったかを調べてみました。すると……なんと " " (半角スペース)でした。

確かに、アルファベットの中では "e" が最頻出かもしれませんが、今回のように「半角スペース」まで含めて暗号化されれば、「半角スペース」が最頻出になりますよね。もう少し良く考えれば想像できたかもしれません。


実際に問題を解いた後、他の人の解き方を調べてみたら、問題文の「平文はよく用いられる英単語を含んでいる」という部分から、暗号文の文字列が "the" や "was" などの単語に復号できる部分を探してそこからキーワードを推測している方が何人かいらっしゃいました。

それでも正解が得られているようなので、間違った解法というわけではないのでしょうが、「平文はよく用いられる英単語を含んでいる」という一文は、「単語の出現頻度は極端に偏っていない」ということを強調したかったのでは?と私は思っています。

2009年8月27日 (木)

Project Euler - Problem 58

問題はこちらをご覧ください。


この問題は Problem 28 の考え方がそのまま使えます。あとは四隅の数が素数かどうかを判別するだけです。

require 'math_tool' nums = 1 primes = 0 dt = 2 n = 1 while true 4.times do n = n + dt primes = primes + 1 if n.prime? end nums = nums + 4 if primes / nums.to_f < 0.1 puts dt + 1 exit end dt = dt + 2 end

素数の判定に時間が必要だったのでしょうか? Ruby 1.9 で答えが出るまでに 6 秒もかかりました。

2009年8月20日 (木)

"math_tool.rb" の改良

先日、以前から興味のあった「素因数分解と素数判定」という本をやっと手に入れました。

まだ読み始めたばかりなのですが、ちょうど「試し割による素因数分解」のアルゴリズムが出てきました。

そのアルゴリズムが「2, 3 以外の素数 p は

p % 6 == 1 または p % 6 == 5

という条件を必ず満たす」という事実をもとに書いてありました。

このことは以前から知っていたのですが、自分の作った素数を扱うメソッドではこの考え方を利用していませんでした。

今回この考え方を使って、自作の "math_tool.rb" のメソッドの一部 ("Integer#prime?", "Integer#factorize") を改良してみました。

さらに、"prime_list" もコードを見直して、無駄な処理を削ってみました。

ちょっとだけ速くなりました。

実際のコードはここにあります。


実際のスピードを添付ライブラリの "prime.rb" と比べてみるためのスクリプトを書いてみました。。

# test.rb require 'prime' t = Time.now (2 .. 10_0000).each{|x| x.prime?} prime1 = Time.now - t t = Time.now (2 .. 10_0000).each{|x| x.prime_division} prime_division = Time.now - t t = Time.now a = Prime.each(10_0000).to_a prime_each = Time.now - t require 'math_tool' t = Time.now (2 .. 10_0000).each{|x| x.prime?} prime2 = Time.now - t t = Time.now (2 .. 10_0000).each{|x| x.factorize} factorize = Time.now - t t = Time.now a = prime_list(10_0000) prime_list = Time.now - t print "prime.rb : prime? : #{prime1} sec\n" print "math_tool.rb : prime? : #{prime2} sec\n" print "\n" print "prime.rb : prime_division : #{prime_division} sec\n" print "math_tool.rb : factorize : #{factorize} sec\n" print "\n" print "prime.rb : Prme.each : #{prime_each} sec\n" print "math_tool.rb : prime_list : #{prime_list} sec\n"

結果はこの様になりました。(ちなみに測定条件は「Pentium M 1.5GHz, Ruby 1.91」でした)

$ ruby test.rb prime.rb : prime? : 2.730776398 sec math_tool.rb : prime? : 0.227278105 sec prime.rb : prime_division : 6.384688654 sec math_tool.rb : factorize : 1.022429391 sec prime.rb : Prme.each : 0.176912212 sec math_tool.rb : prime_list : 0.025297353 sec

"prime.rb" より数倍速いという結果が出ました。自作のメソッドのスピードが予想以上に速かったので、ビックリしつつも非常に喜ばしい結果でした。

2009年8月19日 (水)

Project Euler - Problem 57

問題はこちらをご覧ください。


最初にこの問題を考えたとき、何も良いアイデアが浮かばなくて、とりあえず「文字列の置換を使う」というほとんど反則っぽい方法で解いてみました。

# -*- coding: utf-8 -*- require 'mathn' # * num の桁数が den の桁数を越えていれば true を返す。 def check(num, den) while den > 0 num = num.div(10) den = den.div(10) end return num > den end count = 0 str = "1 + 1/2" 1000.times do rat = eval(str) num = rat.numerator den = rat.denominator count = count + 1 if check(num, den) str = str.sub("1/2", "1/(2 + 1/2)") end puts count

これでも答えは出たのですが、非常に遅い……。Ruby 1.9 で約 20 秒もかかってしまいます。


「これではいけない」と思い、数式をいろいろいじりながら考えていたら、以下のような漸化式に気づきました。

n 番目の項を Tn とすると、Tn = 1 + 1 / (1 + Tn - 1)

この式を使ったコードは次の様になりました。

require 'mathn' count = 0 rat = 3/2 1000.times do num = rat.numerator den = rat.denominator count = count + 1 if num.to_s.size > den.to_s.size rat = 1 + 1 / (1 + rat) end puts count

このコードでは答えが 0.3 秒で出ました。


さらに "Tn = An / Bn" と置くと、

An / Bn = (2 * Bn - 1 + An - 1) / (An - 1 + Bn - 1)

という漸化式が導き出されます。ここまでくると、分子と分母を別々に計算できるので、mathn.rb もいらなくなります。

count = 0 a, b = 3, 2 1000.times do count = count + 1 if a.to_s.size > b.to_s.size a, b = a + 2 * b, a + b end puts count

このコードでは答えが 0.2 秒ででました。


Project Euler をうまく解こうと思ったら、しっかりした数学的考察が必要なんでしょうね。

2009年8月14日 (金)

Project Euler - Problem 55, 56

Problem 55 と Problem 56 は特に工夫もしていないので、まとめて書いちゃいます。


Problem 55 の問題はこちらをご覧ください。

require 'math_tool' class Integer def lychrel? num = self 50.times do num = num + num.to_s.reverse.to_i return false if num.palindromic? end return true end end ans = (1 ... 10000).select{|i| i.lychrel?} puts ans.size

Problem 56 の問題はこちらをご覧ください。

require 'math_tool' max_v = 0 (1 ... 100).each do |a| next if a % 10 == 0 (1 ... 100).each do |b| max_v = [(a ** b).sum_of_digits, max_v].max end end puts max_v

Project Euler - Problem 54

問題はこちらをご覧ください。


久しぶりにオブジェクト指向っぽいコードを書いてみました。

アルゴリズム自体はそんなに難しくなかったのですが、分岐が多くなって長いコードになってしまいました。

役が同じ場合の勝敗を決めるのがちょっと大変だったかな?

class Player def initialize @card_n = nil # 手札の数字の配列 @card_s = nil # 手札のスートの配列 @hand = nil # [役の番号, 役の配列, 残りの配列] end attr_reader :hand # == カードの整列、役の確定 def set(arr) @card_n = arr.map do |a| case a[0] when "A" 14 when "K" 13 when "Q" 12 when "J" 11 when "T" 10 else a[0].to_i end end @card_n.sort!.reverse! @card_s = arr.map{|a| a[1]}.uniq @hand = judge() end # == 役の判定 # * 役のランクと役の名前 # 0 : 役無し # 1 : ワン・ペア # 2 : ツー・ペア # 3 : スリーカード # 4 : ストレート # 5 : フラッシュ # 6 : フルハウス # 7 : フォーカード # 8 : ストレートフラッシュ # 9 : ロイヤルフラッシュ def judge # ストレート系およびフラッシュ系の判定 n_arr = @card_n.map.with_index{|v, i| v + i}.uniq if n_arr.size == 1 s_flag = true else s_flag = false end f_flag = (@card_s.size == 1) case when (f_flag and @card_n == [14, 13, 12, 11, 10]) return [9, @card_n, []] when (f_flag and s_flag) return [8, @card_n, []] when f_flag return [5, @card_n, []] when s_flag return [4, @card_n, []] end # その他の役の判定 count = Hash.new(0) @card_n.each do |n| count[n] = count[n] + 1 end nums = count.to_a.sort_by{|a| a[1]}.reverse! case when nums[0][1] == 4 return [7, [nums[0][0]], [nums[1][0]]] when (nums[0][1] == 3 and nums[1][1] == 2) return [6, [nums[0][0], nums[1][0]], []] when nums[0][1] == 3 n = nums[0][0] @card_n.delete(n) return [3, [n], @card_n] when (nums[0][1] == 2 and nums[1][1] == 2) n1 = nums[0][0] n2 = nums[1][0] @card_n.delete(n1) @card_n.delete(n2) return [2, [n1, n2].sort.reverse!, @card_n] when nums[0][1] == 2 n = nums[0][0] @card_n.delete(n) return [1, [n], @card_n] else return [0, @card_n, []] end end # == 勝敗の判定 def win?(other) rank1, arr1, rest1 = @hand rank2, arr2, rest2 = other.hand case when rank1 > rank2 return "win" when rank1 < rank2 return "lose" end arr1.each_with_index do |n, i| case when n > arr2[i] return "win" when n < arr2[i] return "lose" end end rest1.each_with_index do |n, i| case when n > rest2[i] return "win" when n < rest2[i] return "lose" end end return "draw" end end p1 = Player.new p2 = Player.new count = 0 File.open("poker.txt") do |file| file.each do |line| arr = line.chomp!.split p1.set(arr[0, 5]) p2.set(arr[5, 5]) count = count + 1 if p1.win?(p2) == "win" end end puts count

2009年8月13日 (木)

Project Euler - Problem 53 : 0.1s (Ruby 1.9)

問題はこちらをご覧ください。


自作の "math_tool.rb" には組み合わせの場合の数を計算する "Integer#combination_size" があるので、それを使用しても良かったのですが、この問題では階乗の計算が繰り返し行われるので、階乗の計算をメモ化してみました。

class Integer @@fact = {0 => 1} def fact ans = @@fact[self] if ans return ans else ans = self * (self - 1).fact @@fact[self] = ans return ans end end def comb(r) return self.fact / (r.fact * (self - r).fact) end end ans = 0 (1 .. 100).each do |n| (1 .. n).each do |r| ans = ans + 1 if n.comb(r) > 100_0000 end end puts ans

自作の Integer#combination_size は下降階乗冪を使用しているため、問題に書いてある「組み合わせの計算方法」よりずっと速いのですが、階乗の計算をメモ化するとさらに速くなりました。

Project Euler - Problem 52 : 0.4s (Ruby 1.9)

問題はこちらをご覧ください。


1x, 2x, 3x, 4x, 5x, 6x が全て同じ桁になるためには、元の数の一番大きな桁の数は 1 になります。( 一番大きな桁に 2 以上の数がくると、どこかで必ず繰り上がってしまい、桁が増えてしまうので……)

元の数の一番大きな桁の数が 1 の場合、2 番目に大きな桁の数が繰り上がったとしても、2x, 3x, 4x, 5x, 6x では一番大きな桁の数は 6 種類になります。

以上のことより、元の数字は最低 6 種類の数字を含んでいなければならないので、6 桁以上の数字ということになります。

# -*- coding: utf-8 -*- require 'math_tool' 123456.upto(1/0.0) do |num| # 123456 : 6 個の数字を含む最小の数 num_arr = num.to_a next if num_arr[0] > 1 num_arr = num_arr.sort if (2 .. 6).all?{|i| (i * num).to_a.sort == num_arr} puts num exit end end

2009年8月12日 (水)

Project Euler - Problem 51 : 1.1s (Ruby 1.9)

問題はこちらをご覧ください。


8 つの素数を見つけるということは、置き換えられる数字が 8 種類あるということです。

一の位に偶数や 5 があるとその数は偶数または 5 の倍数となってしまいます。したがって一の位は 1, 3, 7 ,9 のいずれかになるので、一の位が置換されることはありません。

また、0 から 9 までの数字のうち 8 個の数字が出現するのですから、その中の一番小さい数は 0, 1, 2 のいずれかになります。

そこで、0, 1, 2 のいずれかを 2 個以上含む素数を見つけたら、実際に他の数で置換して素数になるかどうかを調べてみます。

require 'prime' require 'math_tool' Prime.each do |n| arr = n.to_a # 0, 1, 2 の位置を探す ( 一の位は調べない ) pos_arr = [[], [], []] arr[0 .. -2].each_with_index do |v, i| pos_arr[v].push(i) if v < 3 end # 同じ数字を置換して、素数を探す。 pos_arr.select{|a| a.size > 1}.each do |pos| 2.upto(pos.size) do |r| # 同じ数字が 2 個以上あった場合、2 個変えた場合、3 個変えた # 場合……と、全ての組み合わせを考える。 pos.combination(r).each do |a| nums = Array.new (0 .. 9).each do |n| a.each{|i| arr[i] = n} nums.push(arr.to_i) unless arr[0] == 0 end select_nums = nums.select{|n| n.prime?} if select_nums.size == 8 # p select_nums puts select_nums[0] exit end end end end end

2009年8月11日 (火)

Project Euler - Problem 50 : 0.1s (Ruby 1.9)

問題はこちらをご覧ください。


2 から順に素数を足していった時、547 個目の素数を足した時点で和が 100 万を越えてしまいます。

したがって、求める答えは 546 個以下の素数の和になるはずです。

では、どのくらいの素数を用意しておけば良いのでしょうか?

問題文の中では、「連続する素数の和で 1000 未満の素数を表したときに最長になるのは 953 で 21 項を持つ」という表記があります。

話を単純化するために、「連続する 21 個の奇数の和が 100 万未満で一番大きくなる場合」を考えてみます。和が最大になる時、その中に含まれる奇数の最大値を計算すると 47579 になります。

このことから、かなり大雑把に考えても 5 万以下の素数があれば計算には足りそうです。

そこで、5 万以下の素数列を準備し、その中から連続する素数を取り出して実際にその和が素数になるかどうかを調べてみます。

調べる長さは 546 から始めてだんだん減らしていきます。

require 'math_tool' Limit = 100_0000 Max = 5_0000 p_lst = prime_list(Max) p_len = p_lst.size sum = 0 len = p_lst.take_while{|a| sum = sum + a; sum <= Limit}.size len.downto(21) do |i| 0.upto(p_len - i) do |j| sum = p_lst.drop(j).take(i).inject(:+) break if sum > Limit if sum.prime? puts sum exit end end end

実際に答えを計算させると、最初に求めた 546 番目の素数 (3931) より大きな素数は必要ないことが分かるのですが、あえて最初に考えたとおり 50000 までの素数を準備してから答えを計算させました。

2009年8月 5日 (水)

Project Euler - Problem 49 : 0.1s (Ruby 1.9)

問題はこちらをご覧ください。


以下の説明の中で「数を構成する数字を小さい順に並べたもの」を「数の組成」という言葉で表現していますが、これは説明を簡単にするために私が勝手に使っている言葉で、きちんとした定義があるわけではありません。(ちなみに 4512 の組成は 1245 となります)


初めに、素数と素数の組成をペアにして配列に入れます。このペアを組成を使ってソートすると、同じ組成を持つ素数のグループが塊になって並びます。

そうしておいて、同じ組成のグループだけを取り出して等差数列ができるかどうかを調べていきました。

既に同じ組成の数が集まっている分、探す手間が省けるので結構速く答えが出ます。

(自作の "math_tool.rb" に関してはこちらをご覧ください)

require 'math_tool' p_lst = prime_list(9999).drop_while{|i| i < 1000} p_lst = p_lst.map{|i| [i, i.to_a.sort.to_i]}.sort_by{|x| x[1]} ans = Array.new until ans.size == 2 arr = p_lst.take_while{|a| p_lst[0][1] == a[1]}.map{|a| a[0]} len = arr.size p_lst = p_lst.drop(len) next if len < 3 arr = arr.sort while arr.size >= 3 a = arr.shift arr.each do |b| c = b + (b - a) ans.push([a, b, c]) if arr.include?(c) end end end p ans

2009年8月 3日 (月)

Project Euler - Problem 48

問題はこちらをご覧ください。


puts (1 .. 1000).map{|i| i ** i}.inject(:+) % (10 ** 10)

Ruby だと、一行で終わってしまいました。コメントのしようがありません。

Project Euler - Problem 47 : 3.5s (Ruby 1.9)

問題はこちらをご覧ください。


詳しい証明は省略しますが、連続する数について次のことが言えます。

  • 連続する 2 つの自然数は共通因数を持たない。(互いに素である)
  • 連続する 2 つの正の奇数は共通因数を持たない。(互いに素である)
  • 連続する 2 つの正の偶数は共通因数として 2 のみを持つが、ひとつは 21 * a の形をとり、もうひとつは 2n * b (ただし n ≧ 2) の形をとる。

以上のことから、連続する 4 つの数はすべて異なる素因数を持つことになります。

ですから、この問題では素因数分解したときの因数の数だけを調べればいいことになります。

require 'math_tool' n = 2 * 3 * 5 * 7 factors = [n.factorize.size, (n + 1).factorize.size, (n + 2).factorize.size, (n + 3).factorize.size] while true if factors.all?{|i| i == 4} puts n exit end n = n + 1 factors.shift factors.push((n + 3).factorize.size) end

Project Euler - Problem 46

問題はこちらをご覧ください。


すみません。何の工夫もしていません。

require 'math_tool' class Integer # * self が「平方数の2倍と素数の和」で表せたら true を返す。 def goldbach? 1.upto(1.0/0.0) do |i| n = 2 * i * i return false if n > self return true if (self - n).prime? end end end n = 33 while n.goldbach? n = n + 2 n = n + 2 while n.prime? end puts n

2009年8月 2日 (日)

Project Euler - Problem 45

問題はこちらをご覧ください。


n = 2 * m - 1 の時、Tn = Hm となるので、六角数は必ず三角数になります。

このことから、この問題では「五角数かつ六角数」となる数を求めればいいことになります。

class Integer # * 五角数であれば、何番目かを返す。 def pentagon? x = ((1 + 24 * self) ** 0.5 + 1) / 6.0 if x == x.to_i then return x.to_i else return false end end # * 六角数を求める。 def hexagon return 2 * self * self - self end end 144.upto(1/0.0) do |i| h = i.hexagon if h.pentagon? puts h exit end end

Project Euler - Problem 44 : 3.8s (Ruby 1.9)

問題はこちらをご覧ください。


五角数を順に求めていって、配列の先頭に収めていきます。

新しい五角数を求めたとき、その五角数と配列の中身を頭から順に調べていくという方法をとっています。

もし、配列の最後まで調べた結果、条件に合わなければ、この五角数も、配列の先頭に入れます。

これを繰り返していくと配列には大きい順に五角数が並びます。

そのため、最初に見つかった五角数のペアの差が最小なのは自明なので、それ以上調べる必要がありません。

class Integer # * 五角数を求める。 def pentagon return (3 * self * self - self) / 2 end # * 五角数であれば、何番目かを返す。 def pentagon? x = ((1 + 24 * self) ** 0.5 + 1) / 6.0 if x == x.to_i then return x.to_i else return false end end end penta_list = [1] 2.upto(1/0.0) do |k| p_k = k.pentagon penta_list.each do |p_j| if (p_k - p_j).pentagon? and (p_k + p_j).pentagon? puts p_k - p_j exit end end penta_list.unshift(p_k) end

« 2009年7月 | トップページ | 2009年9月 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ