/ 最近 .rdf 追記 設定 本棚

脳log[2011-03-20~]



2011年03月20日 (日)

最終更新: 2011-03-21T02:43+0900

[ProjectEuler] Problem 76, 77, 78

 Problem 76

Problem 31と同じ問題。その解答(20110125p01.03)。ただし、Problem 31には通用した俺の解法では全然終わらない。

Target = 100
a = [1] + [0]*Target
(Target-1).downto(1){|pick|
	0.upto(Target-pick){|i|
		a[i+pick] += a[i]
	}
}
p a[Target]

 Problem 77

素数ごとに一から再試行してるけど計算量はたかがしれてた。

require 'mathn'
prime_gen = Prime.new
primes = []
prime_gen.each{|prime|
	primes.push prime

	a = [1] + [0]*prime
	primes.each{|pr|
		0.upto(prime-pr){|i|
			a[i+pr] += a[i]
		}
	}

	answer = a.index{|x| 5000 < x }
	if answer
		p answer
		exit
	end
}

 Problem 78

まったくひどい解答。76から続くシリーズの締めらしく、何も考えないと計算量が膨大になる。手続き的な解法から一歩進む必要がある。それか一分ルールを無視して何時間もかけて良しとするか。

Target = 100000
a = [1] + [0]*Target
(Target-1).downto(1){|pick|
	0.upto(Target-pick){|i|
		a[i+pick] += a[i]
	}
}
p a.index{|x| x%1_000_000 == 0}

2011年03月19日 (土) 「乗るべきか乗らないべきか」 ちょっと違和感が。文法的に説明できないし、古めかしく聞こえるけど「乗らぬべき」がしっくりくるかな(音的に)。「すべき」と「するべき」も迷う。なんとなく「すべき」にしたい。あと、最近「べき」が使われすぎてて押しつけがましさを感じる。検索>「「べき」という言葉はどう使うべきか[絵文録ことのは]2004/05/14」 べきは連体形で終止形はべしだとか。べしはもはや出てこないなあ。べきに動詞の何形が接続するのか考えたときに、せ・し・する・する・すれ・しろ(せ(よ))……「す」がない。あれ? するべき? とわき上がった疑問もあっさり解消。「現代語では、「する」という動詞がある。しかし、古典文法では、それは「す」という動詞なのだ(連体形が「する」である)。「終止形+べし」というルールに従えば、古典では「すべし」、現代文法的には「するべし」ということになる。」■■■@2014-02-12「よく見る「しないべき」とかも「するべきでない」にしてほしい。」べしの方を否定するのか。そちらの方が普通だな。そして先に書いた「ぬべき(ぬべし)」に関して、「【ぬべし】って否定? | 扶桑(ふさう)」。ぬべしのぬは完了(※リンク先では確述といってますね)のぬであった。そりゃあ音で判断すればありだったかもしれないが意味が変わってしまっていた。「乗らざるべき」はますますもって文語調なので「乗るべきか乗るべきでないか」とするのが一番自然でした。■「乗りぬべし」だったら否定だとは間違えなかった。区別がつくんだから「乗らぬべし」は否定のず(ぬ)で解釈してくれても……。■判別性を根拠にするその言に説得力がないのは、区別できなくてもらを抜かない、無理矢理可能動詞を作ったりしない人間の言うことだから。■間違いさがし。1.風立ちぬべし。2.風立たざるべし。3.「風立たぬべし」。4.「風立たないべし」。5.「風立たないべき」。4と 5から受ける印象を比べると「~いべき」を含む「~べき」は単なる間違いから一歩抜けた新しい段階にいると感じる。自分自身、「べき」の終止形が「べし」だという意識はなかったのだし(連体形だけでも文は作れる。それが最近気になり出した傾向でもあるのだけど>20140123)。


2011年03月16日 (水) 糸井さんが示した目安「じぶんひとりを3日雇えるくらいのお金」が大変参考になった。それとこちら>「@14:36」 いわゆる封筒裏の計算で、一時の熱狂が過ぎた後も継続して、収入の 1割を今後 10年間差し出す覚悟があるかと問うている。時限法案で消費税 1%上げとかいう話も聞くから、とりあえずそこを目処に続けんとダメやろね。


2011年03月15日 (火)

最終更新: 2012-02-29T17:34+0900

[ProjectEuler] Problem 72

 Problem 72

前のバージョンはここ(20110312p01.02)。step2を最適化*すると倍くらい速くなって 1分半(ウチのPC基準で。C++だとコンマ1秒)。それに伴い素因数の組み合わせを求める必要がなくなったので、100万要素の配列の配列が 100万要素の Fixnum配列になってメモリ使用量が再び数MBレベルになった。

LIMIT = 1_000_000
pfs = Array.new(LIMIT+1, 1)
count = LIMIT*(LIMIT+1)/2 - 1 # 1) 2からLIMIT以下の分母 d につき d 通りの分子を予め計上する。
2.upto(LIMIT){|d| # 0) 2からLIMIT以下の分母 d に対して、
	print d,"\r"
	d.step(LIMIT, d){|_| pfs[_] *= -d } if pfs[d] == 1
	# 2) 分子が d で分母が d の倍数になるものを加減する。
	count += pfs[d]/pfs[d].abs * (LIMIT/d)*(LIMIT/d+1)/2 if pfs[d].abs == d
}
p count

一週間後にはこのコードが理解できなくなってること請けあい。


ググった>「Dreamshire | Project Euler Problem 72 Solution」。φ関数の値を合計するとかで、Rubyでも10秒未満。Problem 69に出てきた関数だけど、その問題はインチキしたから理解してないんよね。

LIMIT = 1000000
phi = (0..LIMIT).to_a
2.upto(LIMIT){|n|
	n.step(LIMIT, n){|m|
		phi[m] *= (n-1.0)/n
	} if phi[n] == n
}
p phi.inject(&:+).floor-1

繰り返しの構造は似てるのにこの実行時間の差はなんだ? と思ったら print d,"\r" の有無だけだった。俺のも同等に速い。

* 全体でみると同じ数字を足したり引いたりを繰り返してる気がしたので個々の dに特有の値だけを加減するように。


2011年03月14日 (月) ActiveRuby.msiのアンインストーラは binフォルダに放り込んだ ruby.icoや lib/ruby/site_rubyに個人的にインストールしたライブラリを残してくれるのね。抜かりがない。時間はかかるけど。

最終更新: 2011-03-14T21:52+0900

前後の衛星写真をくらべて言葉を失った。地形がかわっとる。町がない。思い出せばリポーターは最初からこの状況を伝えようとしていた。そして、言葉からでは想像が難しかったことが衛星写真で明らかになったように、衛星写真でわかることは実際の万分の一もない。

1号機に続いて 3号機でも(建物内の水素ガスが)爆発。2号機の冷却機能喪失。原発設置のハードルがさらに上がってしまったのが残念。非現実的なコストを積み上げて想定される災害対策を行っても、心情的に無理なんじゃないか。

専門家は癌を死の病だと盲目的におそれる患者(キャスターがその役)に対するように、不安を煽らないように煽らないようにしゃべっていた。でもそれでは不信を招く。これだけ浴びたらこういう症状が出ます、という情報も知りたい。当事者には汚染の有無だけが重要で、汚染はあるんだし、避難勧告に従っていれば大丈夫っていっても、避難できなかった人が被曝して「「除染」後の検査でも高い放射線量の値を示したため、第2次被曝医療機関に搬送されていた」んだけど。


不勉強。


2011年03月13日 (日) コツ(3):「伝え返し」と「問い掛け」を駆使する」 「伝え返し」ねえ。TVドラマで頻繁にみかけるそういうのを見て、アホみたい、テンポが悪い、と思ってしまうからコミュニケーションが下手なんだろうなあ。カウンセラーの常套手段なのにね。相手の言葉を聞いて自分は納得して先に進もうとするけどその前に相手にそのシグナル(ACKていうの?)を伝えてない自覚はある。合理性や正しさが唯一絶対の価値だと信じてるきらいもある。自分の正しさを信じがちなところがまた質が悪い。(信じる⇐根拠がない)

最終更新: 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月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話「最果ての町」は面白かった。ここからに期待。