Google Recruit Problem

Document Links

• マルチスケールシミュレーション特論まとめ
• Google recruit problem, exp and prime

Google Recruit

Google Recruit Problemとは

{e(自然対数の底)の値で連続する10桁の数のうち，最初の素数}を求めよ．ただしeは200桁まで．

2.7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274274663919320030599218174135966290435729003342952605956307381323286279434907632338298807531952510190

解説

考えたことは，素数判定のメソッド，10桁ずつに分割する必要がある，くらいかなぁ．

というわけで，

google_recruit.rb

require './aeroc'
require 'prime'
require 'colorize'

def my_prime(num)
    2.step(to: Math.sqrt(num), by: 1) do |i|    
	return false if num%i==0
    true
    end
end

# exp = gets.to_s.chomp.delete(".") # File名を標準入力で受け取る
exp = File.read("exp.txt").delete(".") # 講義資料のように，改行があるtxtファイルならば，.delete("\n")する．

0.step(to: exp.length-10, by: 1) do |i|
    num = exp[i..i+10-1].to_i
    if my_prime(num)
	result = num
    end
    if Prime.prime?(num)
	assert_equal(num,result)
	break
    end
end

調べたところによると，Rubyには素数判定したり，素数を生成したりするためのPrime classがあるらしい．

使い方はprime moduleをImportして，class methodを呼び出す．

require 'prime'

Prime.instance.prime?(2)
Prime.prime?(2)

便利ですなぁ．．．でもまあ，自分で素数判定のmethodを書きますか．

ということで，考えたのは単純に，「渡された数字(num)に対して，"2 〜 sqrt(num)"で割り切れるか判定する」ということ．(なぜ，sqrt(num)で良いかは分かるじゃろうて)

10桁ずつに分割する方法は，単純に，文字列の範囲指定して数値に変換，範囲の更新はstep()を使って" i "でループする．

で書いたのが上のCodeですが，美しくない．．．

とりあえず，以前作成したassert_equalを用いて自分のmethodの値とPrime classとの値を比べる．

$ ruby google_recruit.rb
expected :: 7427466391
result   :: 7427466391
succeeded in assert_equal.

まあ，回答は合ってるみたい．

Update

色々調べていると，いい感じのを見つけた．

• 高速な素数の判定（Ruby）

記事内のこの部分，「 *高速化の多少の工夫があって、2以外の偶数はあきらかに素数でないので、*先に除外し、3以上の奇数で割っています。 」たしかに．．．

あと，0か否かを判定する".zero?"があるらしい，こっちのほうがSmartですなぁ．

ほんでもって，"step(to: ,by: )"のtoとbyは省略できるんか．

というわけで，修正した．

google_recruit_update.rb

require './aeroc'
require 'prime'
require 'colorize'

def update_prime(num)
    return false if (num % 2).zero? #偶数か否かの判定
    3.step(Math.sqrt(num), 2) do |i| #奇数だけで判定
	return false if (num % i).zero?
    true
    end
end

# exp = gets.to_s.chomp.delete(".") # File名を標準入力で受け取る
exp = File.read("exp.txt").delete(".") # 講義資料のように，改行があるtxtファイルならば，.delete("\n")する．

0.step(exp.length-10, 1) do |i|
    num = exp[i..i+10-1].to_i
    if update_prime(num)
	result = num
    end
    if Prime.prime?(num)
	assert_equal(num,result)
	break
    end
end

Google Recruit Problem Level2

どうやら，上述の問題を解くと，新たな問題(Level2)が出されたらしい．

*Congratulations. You've made it to level 2.*Go to www.Linux.org and enter Bobsyouruncle as the login and the answer to this equation as the password.

f(1)=7182818284
f(2)=8182845904
f(3)=8747135266
f(4)=7427466391
f(5)=__________

f(5)が何かを求めて，それをパスワードにサイトにログインしてね．ってさ．

方程式っぽいけど，どうせ何かしらのパターンがあるだろうし，流れ的にネイピア数と関係してるんでしょ．と考えて，調べると，

2.7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274274663919320030599218174135966290435729003342952605956307381323286279434907632338298807531952510190

はい，ありました．

• f(1):小数点1桁目〜10桁目
• f(2):小数点5桁目〜14桁目
• f(3):小数点23桁目〜32桁目
• f(4):小数点99桁目〜108桁目

ではパターンを探しますか．

数字の差分に法則があるとか，桁数の差とかに法則があるとか？．．．見つからない．

ということは，それぞれの数字に共通点があるんでしょう．

はい，見つけました．（簡単に書いてるけど，1時間弱かかった．．．）

各桁の総和が49になってます．

というわけで，10桁の各桁の総和が49になる箇所を探すCodeを書く．

google_recruit_level2.rb

def check_49(num)
    sum = 0
    0.step(num.length-1, 1) do |i|
	sum += num[i].to_i
    end
    return false if sum != 49
    true
end

exp = File.read("exp.txt").delete(".")

count = 0
0.step(exp.length-10, 1) do |i|
    num = exp[i..i+10-1]
    if check_49(num)
	count += 1
	puts "f(#{count})=#{num}"
	if count == 5
	    break
	end
    end
end

実行結果

$ ruby google_recruit_level2.rb
f(1)=7182818284
f(2)=8182845904
f(3)=8747135266
f(4)=7427466391
f(5)=5966290435

完成！

締め

今回はGoogle Recruit Problemを解くCodeをRubyで書いた．

もっと美しいCodeがかけるようになりたい．．．

---

• source ~/school/multi/my_ruby/grad_members_20f/members/evendemiaire/post/google_recruit.org