/ 最近 .rdf 追記 設定 本棚

脳log[2011-03-12~]



2011年03月12日 (土) combinationメソッドを調べるために Ruby 1.8.7のドキュメントを少し読んだ(常用のリファレンスは20051129だ)。choiceから sampleへの名前変更は良かった。choiceは意思を明らかにする行為だと思うからランダム抽出とは相容れないよ(それとも神の選択か)。「Ruby 1.8.8 以降では Array#sample を使ってください。」 Ruby 1.8.8 は出るんでしょうか?

最終更新: 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月11日 (金) [SakuraEditor] お宝発見。落とし穴マップ> サクラの小枝研 - メモ


2011年03月10日 (木) JR東:迷惑な座り方できません…山手線で新型座席試行へ - 毎日jp(毎日新聞)」 寝っ転がれないベンチと同じ発想なのね。人間工学が聞いてあきれる。人間が見えてないよ(骨格と筋肉ぐらいしか見てないんだろう)。人がいない空間や人が脇役の空間を創り出したいの?■■■@2013-06-20「壊れる前に…: 歩道の役割」■■■@2013-07-20「必要がなくても座りたくなる…奇抜なデザインのベンチいろいろ:らばQ

最終更新: 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月09日 (水) [790FX-GD70] バイオス 1.H


2011年03月08日 (火) 本の虫: グラフィックカードのドライバーをアップデートしない低能達」 アップデートしないよ。ATI RADEON X1600 PROだもん。いまさら関連のある変更があるとも思えないし。って、調べてみたら一年前にリリースされた最新の(そしてたぶん最後の)バージョンがインストールされてた。カードを買い換えようにも最近の GPUはでかいしアイドル時の消費電力がたぶん今のカードの消費電力と同じくらいだと思うんだよね。無駄。

最終更新: 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月07日 (月) 『コンクリート マテマティクス』 googleでコンクリートマテマティクスを検索するとマテマティクスとマテリアルが似た語にみなされる。いきなり逸れたが、高揚している。表紙とかざりの紙をめくるとタイトルとともに「オイラーに捧げる」と書いてあった。Project Eulerに必携の書なのは間違いない(表紙を開いてすらいないからそのことにすぐ気づけないんだ)。学校の教科書ではついぞ覚えがないが、この感覚は J.P.ホーガン『星を継ぐもの』を読んだときに似ている。小説と違い演習問題の存在が憂鬱にさせるが、楽しく「読める」本だ。


2011年03月06日 (日) フラクタル-FRACTALE-。6話「最果ての町」は面白かった。ここからに期待。


2011年03月05日 (土) 携帯の個体識別番号は「通信の秘密」や「個人情報」に該当しない? - スラッシュドット・ジャパン」それらに準じるものだと思う。そしてそんなものを強制的に垂れ流すケータイブラウザに改善を要求したい。


2011年03月03日 (木) 電気カーペット。左面と右面を別々に制御できるだけの変哲のないもの。そのコントローラ。オンオフの 2-stateスイッチと左面-全面-右面の 3-stateスイッチ。カーペットの状態が 4しかないのにスイッチには 6。複雑度が増している。ここに、両面にそれぞれ人がいてそれぞれ暑さ寒さの感じ方が違うとする。左面の人がこまめにスイッチをオンオフしたがり、その際にカーペットの現在の状態を確認するような慎重さを持ち合わせない粗忽者だったら(※)。右面の人は不要なのにスイッチを入れられ、必要なのにスイッチを切られたりということがしょっちゅうだ。明らかに、2つのスイッチは左面のオンオフと右面のオンオフであるべきだった。※目視するのが面倒でも手探りで二回操作するだけで自分の側だけをオンオフできるはずなのだ。この話の趣旨はあくまでその二回の操作すら無駄であり無理な要求だったということだけど。


2011年03月02日 (水)

最終更新: 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月01日 (火)

最終更新: 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は何乗したらいいかもわからない。下手の考え休むに似たりっていうけどどうしたもんかなあ。ない知恵を絞るのも悪くないと思うんだけど。


2011年02月25日 (金) レベルE(アニメ)。ジャンプで読んでいて、単行本も持ってるので話は知ってるんだけど面白い。カラーレンジャーの話をみてたらゲームがやりたくなってきて、迷った末にうっかりロマンシング サ・ガ 2を選んでしまった。SFC本体と一緒に買った、一番最初のソフトだ。中古で 2000円。時間が過ぎていく~。


2011年02月24日 (木) まだ、赤盤を再生していない。ハードル上げすぎ。