脳log[2011-03-13～]

最終更新: 2011-03-14T23:14+0900

♪ [ProjectEuler] Problem 73, 74

 Problem 73

昨日(20110312p01)の延長。Problem 72の解答と同じ部分より違う部分を見つける方が難しい。

LIMIT = 12000
pfs = Array.new(LIMIT+1){ [] }
count = 0
2.upto(LIMIT){|d| # 0) LIMIT以下のすべての分母 d に対して、
	print d,"\r"
	d.step(LIMIT, d){|_| pfs[_] << d } if pfs[d].empty?
	n_min, n_max = d/3, (d-1)/2 # (n_min, n_max]
	next unless n_min < n_max
	count += n_max - n_min # 1) とりあえず一通りの分子を計上し、
	# 2) 8分の6など通分可能なものを差し引きする。
	(1..(pfs[d].size)).each{|r|
		cms = pfs[d].combination(r).map{|pf| pf.inject(&:*) }
		count -= (-1)**(r%2+1) * cms.map{|cm| n_max/cm - n_min/cm }.inject(&:+)
	}
}
p count

 Problem 74

問題文のヒントを最大限に利用したが数分かかる。総当たりでなく組み合わせ単位でテストしてその順列を計上したらマシになるかも。順列を考えるときに先頭の桁に 0を置くようなミスを犯しそうだがね。

factorial = [1,1] # [0!,1!,...]
factorial.push(factorial.size*factorial.last) until 9 < factorial.size

chain_length = lambda{
	memo = {
		169 => 3, 363601 => 3, 1454 => 3,
		871 => 2, 45361 => 2,
		872 => 2, 45362 => 2
	}
	f = lambda{|start|
		return memo[start] if memo.has_key?(start)
		next_ = start.to_s.chars.map{|c| factorial[c[0]-?0] }.inject(&:+)
		return memo[start] = 1 + (start == next_ ? 0 : f.call(next_))
	}
}.call

p (1...1_000_000).inject(0){|sum,n| sum += 1 if chain_length.call(n) == 60; sum }

最終更新: 2011-03-15T00:15+0900

♪ [ProjectEuler][Ruby] Problem 71, 72

 Problem 71

「HCF(n,d)=1」には用語の説明があると思ったんだけどなかった。n/dの nと dは最大公約数が 1の既約分数だとすると意味がとおるので HCF=Highest Common Factorだと決めた(でっちあげ)。

分数とはなんぞやだとか切断だとか小難しく考えてしまったが(実際には考えられるほど知らない)、ワンライナーだった。3/7より少し小さい100万個の分数を小数になおして、一番小さいものを見つける。有理数にして比較しないのは時間がかかるから。公約数をみつけたりする時間だろうか。

require 'rational'
p Rational(*(2..1_000_000).inject([0,1]){|answer,d|
	answer[0]/answer[1].to_f < (d*3-1)/7/d.to_f ? [(d*3-1)/7,d] : answer
})

 @2011-03-14 なにこれ！

Project Euler Problem #71 « KeyZero Conversation

分数を初めてならった小学生が必ず間違える分数の足し算(通分せずに分母どうし分子どうしを加算する)にこんな意味があるとか！

 Problem 72

分単位のお時間がかかります。(訳:一時間はかからないけど……)

何倍も速くなるので「Integer#prime_division」を使う代わりに 100万要素の配列を使ってる。トレードオフで使用メモリは数MBから 100MB超になるが。 小手先のチューンよりアルゴリズムを改良しろってのはもっともだけど、かなしいかな、できることとできないことがあるのです。

LIMIT = 1_000_000
pfs = Array.new(LIMIT+1){ [] }
count = 0
2.upto(LIMIT){|d| # 0) LIMIT以下のすべての分母 d に対して、
	print d,"\r"
	count += d-1 # 1) とりあえず d-1 通りの分子を計上し、
	d.step(LIMIT, d){|_| pfs[_] << d } if pfs[d].empty?
	# 2) 8分の6など通分可能なものを差し引きする。
	(1..(pfs[d].size)).each{|r|
		cms = pfs[d].combination(r).map{|pf| pf.inject(&:*) }
		count -= (-1)**(r%2+1) * cms.map{|cm| (d-1)/cm }.inject(&:+)
	}
}
p count

Ruby 1.9からバックポートされてきた(のだと思われる見覚えのないメソッド) cycle, tap, combination, permutation, productといったメソッドが便利だ。あとは自然数を無限に生成し続ける無限リストのようなものをどれだけ簡単に書けるかだ。なにかショートカットがあるのだろうか。これでは長すぎる。

Enumerable::Enumerator.new(lambda{|&block| n=0; loop{ block.call n+=1 } }, :call).each{|x| p x }

それと、block.callの部分を yieldにできないのもわかりにくい。Procと blockと lambdaの微妙な違いによるものなのだろうか。

Rubyによる他所の Project Eulerの解答をみていてこういう書き方も知ってるけど、カウンタが Floatになっちゃうのが不満。

1.upto(1/0.0){|n| p n }

あれ？ Fixnumだ。Floatになるのは stepだった。

1.step(1/0.0){|n| p n } # 1.0, 2.0, 3.0,...

明示的に Fixnumの増分: 1を指定しても n は Float. この違いはなんだろう。

cycleの使い道として zipを想定していたが拒否されてしまった。

irb> [1,2,3,4,5].zip([0])
=> 1, 0], [2, nil], [3, nil], [4, nil], [5, nil
irb> [1,2,3,4,5].zip([0].cycle)
TypeError: can't convert Enumerable::Enumerator into Array
        from (irb):2:in `zip'
        from (irb):2
        from :0
irb> RUBY_DESCRIPTION
=> "ruby 1.8.7 (2010-01-10 patchlevel 249) [i386-mswin32]"

最終更新: 2011-03-12T02:24+0900

♪ [ProjectEuler] 65, 66, 67, 68, 69

 Problem 65

分母を一番深いところから順番に計算していく。

a = ([2] + (1..33).map{|k| [1,2*k,1] }.inject(&:+)).reverse
denom, numer = *a.inject([0,1]){|nd, x| [nd[1], x*nd[1]+nd[0]] }
require 'rational'
p Rational(numer, denom).numerator.to_s.chars.inject(0){|sum,c| sum - ?0 + c[0] }

 Problem 66

xを増やしながらの総当たりで、最後に見つかった Dが答え。と思ったんだけど Dが見つかるペースがどんどこ落ちていく。一日以上かけても 969個の Dのうち 270個が残ってる。

 Problem 67

Problem 18の延長で以前解いた。

 Problem 68

1. 16桁だから 10は一回しか使わない。10は external node.
2. 先頭の桁(外側のノードの最小値)を最大にするために、external nodeに 10,9,8,7,6を配置する。
3. そうすると一辺の和はとりうる値の中で最小の 14。
4. 二桁目を最大にする 6-5-3からスタートして考えよう。次は 10-3-1しかない。
5. ってなかんじで穴埋め。

 Problem 69

前問に引き続いて、数学でもプログラミングでもなく、オラクルで。

1. n/φ(n)を最大にするために……
2. 分母を小さくするために、nはたくさんの素数を因数に持っている方がいい。⇒すべて異なる素数の積からなる数。
3. 分子を大きくするために、nは上限の 100万に近い方がいい。
4. 分子と分母のバランスの取り方は勘で。

最終更新: 2011-03-12T03:46+0900

♪ [ProjectEuler] Q62, Q63, Q64

 Q62

"exactly five" って書いてあるから、同じ数字の並べ替えで作れる立方数が 6以上あってもダメだと思うんだ。

memo = Hash.new{|h,k| h[k] = [] }
n = 0
k_length = 1
loop{
	n += 1
	cube = n*n*n
	k = cube.to_s.split(//).sort.join('')
	if k.length != k_length
		answer = memo.values.select{|cubes| cubes.size == 5 }
		if not answer.empty?
			answer.each{|cubes| p cubes }
			exit
		end
		memo.clear
		k_length = k.length
	end
	memo[k] << cube
}

 Q63

# (x-1)/x <= log10(n) < 1 (n = ?,?,...)
count = 0
x = 0
loop{
	x += 1
	boundary = (x-1.0)/x
	lower_bound = (1..9).to_a.reverse.find{|n| Math.log10(n) < boundary } || 0
	count += 9 - lower_bound
	break if lower_bound == 9
}
p count

またまた「Dreamshire | Project Euler Problem 63 Solution」の解答を検討してみたい。二重のループなんてない。logの計算だって 9回だけ。どういうことだ？

1. 10の n乗は常に n+1桁になる。
2. 9の n乗は 10の n乗より小さいため n+1桁には絶対に届かず、ある程度までは n桁を保つが、そのうち n-1桁に落ちる。
3. 8の n乗は 9の n乗より早く n-1桁に落ちる。
4. 以下 1の n乗まで。
5. で、「ある程度」って具体的には？
6. 10を約0.954乗すると 9になる。9は 10より 0.046(=1-0.954)程度小さい数だ。
7. この 0.046がいくつ集まると 10一個分小さい(=桁が落ちる)ことになるだろう。21.7(=1÷0.046)だ。
8. 9の場合、21乗までは n乗が n桁を保っているが 22乗は違う。

というストーリーをひねり出した。「9は 10より 0.046(=1-0.954)程度小さい数だ」ってくだりがいかにも苦しい。小数だからごまかしがきいてるけど、ぴったり 10一個分小さくなる場合は n桁、n-1桁、どっち？ (たぶんまだ n桁だな。1^1がそう)

ともあれ、明かされてみればワンライナーの問題だったよ。

p (1..9).inject(0){|sum,n| sum + (1/(1-Math.log10(n))).floor }

常用対数を直接求めるメソッドが用意されてるあたりが Rubyだなとおもた。

 Q64

連分数っていうらしい。a_nの求め方、a += 1 while 0 <= r - (n - d*(a+1))**2 の条件部分が判然としない。スクリプト中のコメントにあるように、対象としてるルートの係数が必ず約分されて 1になることも理解できてない。

def next_frac(r, n, d) # (√r + n) / d = a + 1 / [(√r + n_) / d_]
	a = 0
	a += 1 while 0 <= r - (n - d*(a+1))**2
	d_ = (r - (n - d*a)**2) / d
	raise if (r - (n - d*a)**2) % d != 0 # why OK?
	n_ = -(n - d*a)
	return a, r, n_, d_
end

def period_of(r)
	rnd = [r, 0, 1]
	arr = []
	loop{
		a, *rnd = next_frac(*rnd)
		arr << rnd
		period = arr.size-1 - arr.index(rnd)
		return period if 0 != period
		return 0 if rnd[2] == 0 # √r is rational.
	}
end

count = 0
1.upto(10000){|n|
	count += 1 if period_of(n) % 2 == 1
}
p count

ところで、この問題を解くときに Math.sqrtを使うのってインチキくさくない？(だから使ってないんだけど)

最終更新: 2011-03-04T22:27+0900

♪ 20110223p01の続き。

認証結果(GET/POSTデータ)の再利用によるなりすましを防ぐために nonceを使うのが一般的。でもそうするとコメントのプレビュー時にはまだ認証ができないことになる。事前に認証してしまったら自分自身がその結果を再利用するかたちになるから。tDiaryはアカウントやログインって概念を管理してないから OpenIDによる認証結果をそれらと結びつけて持続させることができない。認証とコメントの投稿が同時のぶっつけ本番。書き込み前にどういう表示になるのかはやっぱり知りたいよ。

Bloggerの解。

表示名には、OpenID プロバイダから Google に送信されたあなたの名前が使用されます。表示名がない場合は、OpenID の URL から表示名の取得を試みます。

こういう割り切りが必要なのかな。でも Yahoo!!!なんかは味気ない URLしか返してこないよね(※1)。mixiしか聞かない、表示名が取得できたってのは。もちろん、myOpenIDもユーザーフレンドリーな名前を返す。ペルソナをかぶることすらできるから選んだ。OpenID Providerとしての Googleはひと味違って claimed_idが realmごとに固有のものに変化するらしい(※2)。Webサービスからすると、ユーザーをリダイレクトしたときと返ってきたときの claimed_idが変わったように見える。OpenIDをいろんなサービスへのログイン手段としてだけみるなら、余分な情報を渡さないのはメリット。自己紹介として URLを提示したときにはそれと違うものが claimed_idとして Webアプリに渡るのはデメリット。さて、独自ドメインの URLを提示しておいて、そのドメインから Googleへ認証を delegateした場合の claimed_idはどうなる？

※1 知らぬ間に AX(Attribute Exchange)に対応してた。「Yahoo! JAPAN、OpenIDでプロフィール情報を提供　拡張仕様「AX」「UI」に対応：CodeZine」でも、SREGには対応しないってどういうこと？ AXの汎用性は却って対応が面倒なんだけど。「Attribute Exchange のメモ - Yet Another Hackadelic」定義済みのシェーマがあるらしいが、すでに二つもある。

※2 もっとも、そのことを知ったのはこういうタイトルの記事。「OpenIDでGoogleからグローバルユニークなユーザー識別子を取得できるかもしれない方法 - r-weblife」realm(Webサービスのドメイン)固有の claimed_id ↔ 「グローバルユニークなユーザー識別子」

閑話休題。nonceをワンタイムでなく時限式にするしかないのだろうか。タイムアウトって嫌いなんだけど。

 @2011-03-04

OpenID Providerへコメントの全文ごとユーザーをリダイレクトするのはまずいかなと思って、通常通りコメントを保存した後でリダイレクトし、正しく認証されて返ってきたときに、その印としてコメントに OP名を付与することを考えた。問題はその認証がどのコメントに対するものなのかだ。ユーザーを送り出すときに「このパラメータと一緒に返ってきてね」ということはできるが……。コメントを他者が推測できない UUIDみたいなものとともに保存しておいてユーザーにそれを運んでもらおうか。(もちろんどの日の日記に対するコメントなのかを表すパラメータもユーザーに運んでもらう)

最終更新: 2011-03-02T05:24+0900

♪ [ProjectEuler] Q61

 Q61

何も考えずにコーディングしただけ。一瞬 CPUが考え込みます。

generators = [
	lambda{ n = 0
		lambda{ n+=1; n*(n+1)/2 }
	}.call,
	lambda{ n = 0
		lambda{ n+=1; n*n }
	}.call,
	lambda{ n = 0
		lambda{ n+=1; n*(3*n-1)/2 }
	}.call,
	lambda{ n = 0
		lambda{ n+=1; n*(2*n-1) }
	}.call,
	lambda{ n = 0
		lambda{ n+=1; n*(5*n-3)/2 }
	}.call,
	lambda{ n = 0
		lambda{ n+=1; n*(3*n-2) }
	}.call,
]
# 数を準備
d4polynumbers = generators.map{|g|
	() while (p = g.call) < 1000
	a = [p]
	a.push(p) while (p = g.call) < 10000
	a
}
# 端緒(の集まり)
bunch_of_chain = d4polynumbers[d4polynumbers.size-1].map{|p|
	[[p, d4polynumbers.size-1]]
}
# 端緒を伸ばすもの
extender = lambda{|chain, pool|
	xx = chain.last.first.to_s[-2,2]
	( (0...(pool.size)).to_a - chain.map{|_| _.last } ).map{|i|
		[i, pool[i]]
	}.map{|i, nums|
		nums.find_all{|num|
			num.to_s[0,2] == xx
		}.map{|num|
			chain + [[num, i]]
		}
	}.inject(&:+)
}
# 伸ばしていく
(d4polynumbers.size-1).times{
	bunch_of_chain = bunch_of_chain.map{|chain|
		extender[chain, d4polynumbers]
	}.inject(&:+)
}
# 輪っか？
bunch_of_cyclic_chain = bunch_of_chain.reject{|chain|
	chain.first.first.to_s[0,2] != chain.last.first.to_s[-2,2]
}
# 出力
bunch_of_cyclic_chain.each{|chain|
	puts chain.map{|a,_| a }.join("\t")
	puts chain.map{|_,b| "P#{b+3}" }.join("\t")
	puts "sum: #{chain.map{|a,_| a }.inject(&:+)}"
}

先は長いのにもう失速してる。「良いもの。悪いもの。: Project Eulerを100問解いてみた」テトレーションとか聞いたこともない単語なんだけど……。

中学生の時に 3^{50} の一の位は何かという問題が出た。でも Problem 188は何乗したらいいかもわからない。下手の考え休むに似たりっていうけどどうしたもんかなあ。ない知恵を絞るのも悪くないと思うんだけど。