/ 最近 .rdf 追記 設定 本棚

脳log[ProjectEuler: 2011-02-13～]

カテゴリ[ProjectEuler]に属するセクションのみを表示しています。(他のカテゴリも表示)
最近 これより古い日記はありません

2011年02月13日 (日) 「青空が降る少年」が「恋しさと せつなさと 心強さと」と同じくらい好きだ。

最終更新: 2011-02-20T21:45+0900

♪ [ProjectEuler] Q58, Q59, Q60

 Q58

10%未満っていうのは絶妙なポイントなのかな。全然 9%未満に落ちない。

def prime? x
	return false if x < 2
	return true if x == 2
	quo, rem = x.divmod(2)
	return false if rem == 0
	t = 1
	while t < quo
		t += 2
		quo, rem = x.divmod(t)
		return false if rem == 0
	end
	return true
end

x, t = 1, 0
primes_on_diagonals = 0
loop{
	t += 2
	3.times{
		x += t
		primes_on_diagonals += 1 if prime? x
	}
	x += t
	puts "#{primes_on_diagonals} primes out of #{2*t+1} (#{100*primes_on_diagonals/(2*t+1)}%, side length=#{t+1})"
	exit if 100 * primes_on_diagonals / (2*t+1) < 10
}

 Q59

  1. 暗号化キーの長さが 3文字なのがわかってるので、数列を 3列に並べて各列を眺める。
  2. 英単語には eが一番使われるとか、単語では theが再頻出だとかの統計データがあるらしい。(と書いてあるのを何度も目にしたが実際のデータは見たことがない)
  3. 文章なら文字としてはスペースが一番多いはずだ。
  4. 単語で theが一番多いなら、theの前後の空白は右下に向いて、(1行1列目)↘(2行2列目), (1行2列目)↘(2行3列目), (1行3列目)↘(2行1列目) の並びで現れるはずだ。
  5. というかんじでマジックナンバーが出てきた。
  6. あ、問題文のサマリに「Using a brute force attack, can you ...」って書いてある。しまった。
encrypted_text = [79,59,12,...,22,73,0,0] # last 2 elements are padding.
text = ""
0.step(encrypted_text.size-1, 3){|i|
	text += (encrypted_text[i+0] ^ (71 ^ " "[0])).chr
	text += (encrypted_text[i+1] ^ (79 ^ " "[0])).chr
	text += (encrypted_text[i+2] ^ (68 ^ " "[0])).chr
}
text.chop!.chop! # remove padding
puts text
puts "sum: #{text.bytes.inject(:+)}"

 Q60

  1. 素数二つ(A,B)に分割できてローテートしても素数な素数(AB,BA)。⇒ a set of 2 primes (A,B)
  2. (AX,XA),(BX,XB)が 1の条件を満たす 2 sets of 2 primes が見つかる。⇒ a set of 3 primes (A,B,X)
  3. (AY,YA),(BY,YB),(XY,YX)が 1の条件を満たす 3 sets of 2 primesが見つかる。⇒ a set of 4 primes (A,B,X,Y)
  4. (AZ,ZA),(BZ,ZB),(XZ,ZX),(YZ,ZY)が 1の条件を満たす 4 sets of 2 primesが見つかる。⇒ a set of 5 primes (A,B,X,Y,Z)

1を満たす素数を発見しながらそれを使って、1の集合から2へ、2の集合から3へ、3の集合から4へ、要素をプロモートしていけばよさそう。

# 寝る前にやる。

寝てしまった。答えが出ない。素数を分割するんでなく、素数のペアを組み合わせて素数かどうか判定した方がいいかもしれない。そろそろ身にしみて理解してきたけど、素数って印象よりありふれ過ぎてる。

 @2011-02-17

ちょっとくらい時間がかかってもいーやって考えてたけど、何日もかけても四つ組みが 7つと、五つ組が 0個しか見つからないことがわかったので、1分以内に答えを出すべくもうちょっと考える。

  1. 小中学生の頃に読んだ数字遊びの本から得た知識によれば、10進表記の各桁の和が 3の倍数の数はそれ自体も 3の倍数だという。だというwww
  2. 各桁の和を 3で割った余りが 0の素数は 3だけ。
  3. 各桁の和を 3で割った余りが 1の素数と 2の素数を組にすると、それをつなげた数は 3の倍数になってしまい素数ではなくなるので組にできない。
  4. 各桁の和を 3で割った余りで素数を分類すると 5つ組みとして考えられるのは (0,1,1,1,1), (0,2,2,2,2), (1,1,1,1,1), (2,2,2,2,2)の 4パターンだけ。
  5. 3桁までの素数で総当たりしてみよう。
  6. 見つからなかったので 4桁までで総当たり。
def prime? x
	return false if x < 2
	return true if x == 2
	quo, rem = x.divmod(2)
	return false if rem == 0
	t = 1
	while t < quo
		t += 2
		quo, rem = x.divmod(t)
		return false if rem == 0
	end
	return true
end

set012 = [[],[3],[]]
require 'mathn'
Prime.new.each{|prime|
	break if 10000 <= prime
	dmod3 = prime.to_s.bytes.inject(0){|sum,byte| sum+byte-?0 } % 3
	set012[dmod3] << prime
}
set1, set2 = set012[1], set012[2]
set2[0] = 3
# set1 = [3,7,13,...]
# set2 = [3,5,11,...]

make_group_of_two = lambda{|set|
	pair = {}
	0.upto(set.size-2){|i|
		(i+1).upto(set.size-1){|j|
			if prime?("#{set[i]}#{set[j]}".to_i) and prime?("#{set[j]}#{set[i]}".to_i) 
				(pair[[set[i]]]||=[]) << set[j]
			end
		}
	}
	return pair
}
group1, group2 = make_group_of_two.call(set1), make_group_of_two.call(set2)

extend_group = lambda{|g|
	group = {}
	g.each_pair{|rest, last1s| # rest + one of last1s = group
		last1s.each{|last1|
			next1s = last1s
			gg, out = rest.clone, last1
			gg.size.times{|i|
				gg[gg.size-1-i], out = out, gg[gg.size-1-i]
				next1s &= g[gg]||[]
			}
			if ! next1s.empty?
				group[rest+[last1]] = next1s
			end
		}
	}
	return group
}
group1, group2 = extend_group.call(group1), extend_group.call(group2) # sets of 3 primes
group1, group2 = extend_group.call(group1), extend_group.call(group2) # sets of 4 primes
group1, group2 = extend_group.call(group1), extend_group.call(group2) # sets of 5 primes

printer = lambda{|rest, last1s|
	last1s.each{|last1|
		puts %[#{rest.inject(&:+)+last1}:\t#{rest.join("\t")}\t#{last1}]
	}
}
group1.each(&printer)
group2.each(&printer)

分単位の時間で答えはでたけどもその五つ組の合計が意外に大きくて、10000以上の素数を組に加えても最小の組み合わせになりうる。計算量の増大の仕方がひどくて、これ以上桁数を増やして試行するのは無理だというのに。

 「だという わらわらわら」@昨日

じゃないよね。

\begin{array}{rcl} q & = & a_0 + 10a_1 + 10^2a_2 +……+ 10^na_n \quad\mbox{(}a_n\mbox{は 0以上 9以下の整数)}\\ & = & (a_0 + a_1 + a_2 +……+ a_n) + 9a_1 + 99a_2 +……+(10^n-1)a_n\\ \end{array}

a_0+a_1+a_2+……+a_n が 3の倍数の整数 qは 3の倍数です。

たしか 4の倍数についても同じような判定規則があった気がした。忘れたけど。

たしか 5の倍数についてもどこかの桁を見るだけで(略

 @2011-02-19

4は 100を作るから下2桁だけ。5は 10を作るから下1桁だけを見ればいい。

 「計算量の増大の仕方がひどくて」

一番時間を食ってるのは make_group_of_two. 異なる二要素の組み合わせということで n^2-n 回の素数判定を行ってる。素数判定自体も nの大きさに比例する(※1:1ではないけど)ループを持っている。大変なはずだ。

とりあえず、今の素数判定より賢い素数判定があるのはわかってるけどわからないので使ってない。(注:わかる => 知ってる, 理解できる) 丁寧にコードを読んだらわかるかもだけどそれはチートっぽい。大学入試の数論関係の問題だって、解答をチラ見したら誰だって理解できんだよ。

ツッコミを入れる

2011年02月11日 (金)

最終更新: 2011-02-12T22:42+0900

♪ [ProjectEuler] Q56, Q57

 Q56

Bignumはできれば使いたくない。aが 100未満なので 8桁ずつ。

answer = [0, 0, 0] # sum, a, b
1.upto(99){|a|
	digits = "1"
	1.upto(99){|b|
		sum = 0
		carry = 0
		0.step(digits.size-1, 8) {|i|
			l, r = [0, digits.size-i-8].max, digits.size-i
			carry, digits8 = (digits[l...r].to_i * a + carry).divmod(100000000)
			digits8 = "00000000#{digits8}"[-8,8]
			digits[l...r] = digits8
			digits8.each_byte{|byte|
				sum += byte - ?0
			}
		}
		if carry != 0
			digits8 = carry.to_s
			digits = digits8 + digits
			digits8.each_byte{|byte|
				sum += byte - ?0
			}
		end
		if answer[0] < sum
			*answer = sum, a, b
		end
	}
}
p answer

 Q57

とかいいながら Bignum。

count = 0
numer, denom = 1, 1
1000.times{
	numer, denom = numer + denom + denom, numer + denom
	count += 1 if numer.to_s.length != denom.to_s.length
}
p count
ツッコミを入れる

2011年02月09日 (水) カレーライスのライスは右か左か。答えはでてるんだろうか。右利きだから左にご飯があると、1.スプーンをご飯に突き立てる。2.右側からカレーを巻き込みながらご飯のブロックをすくい上げる。という動作がスムーズに行えるな、なんて事を考えるんだけど、ぶっちゃけどっち向きでも食べられるし、量が減ってくるとお皿に熱を奪われたくなくて、縦向きに持って手前に寄せて食べてる。

最終更新: 2011-02-10T04:56+0900

♪ [ProjectEuler] Q51, Q52, Q53, Q55

 Q51

ただただ、手と CPUを動かすだけで精一杯。(頭は役に立ってないよ)

primes = [2]
is_prime = lambda{|x|
	result = true
	primes.each{|prime|
		quo, rem = x.divmod(prime)
		if rem == 0
			result = false
			break
		end
		break if quo < prime
	}
	return result
}

# replace 2 digits or 3 digits. キ・メ・ウ・チ
def find_8_prime_family(a)
	return [] if a.size < 8
	a.map!{|x| x.to_s }
	h = Hash.new{|h,k| h[k] = [] }

	# 2 digits
	0.upto(a.first.size-3){|i|
		(i+1).upto(a.first.size-2){|j|
			h.clear
			a.each do |prime|
				if prime[i] == prime[j]
					h[prime[0...i]+prime[(i+1)...j]+prime[(j+1)...(prime.size)]].push prime
				end
			end
			h.each do |_,v|
				return v if v.size == 8
			end
		}
	}

	# 3 digits
	0.upto(a.first.size-4){|i|
		(i+1).upto(a.first.size-3){|j|
			(j+1).upto(a.first.size-2){|k|
				h.clear
				a.each do |prime|
					if prime[i] == prime[j] and prime[j] == prime[k]
						h[prime[0...i]+prime[(i+1)...j]+prime[(j+1)...k]+prime[(k+1)...(prime.size)]].push prime
					end
				end
				h.each do |_,v|
					return v if v.size == 8
				end
			}
		}
	}

	return []
end

x = 1
start = 0 # start of primes of a width.
loop {
	x += 2
	next unless is_prime.call x
	print "#{x}\r"
	if primes[start].to_s.length != x.to_s.length
		a = find_8_prime_family primes.last(primes.size-start)
		if ! a.empty?
			puts a.sort.join(" ")
			exit
		end
		start = primes.size
	end
	primes.push x
}

 Q52

桁数ごとに探索範囲を決めて、総当たり。

問題が xについても同じ数の組み合わせであることを求めてると思わなくてチェックしてないけど、結果的に xも 2x,3xなんかと同じ数字で構成されてた。

digits = 10
loop {
	digits *= 10
	(digits/2).upto((digits*10-1)/6){|x|
		print "#{x}\r"
		x2 = (x*2).to_s.split(//).sort
		if [3,4,5,6].all?{|n|
			x2 == (x*n).to_s.split(//).sort
		} then
			puts [1,2,3,4,5,6].map{|n| x*n }.join(" ")
			exit
		end
	}
}

 Q53

浮動小数点数なんてファジーなものを使っちゃったよ。Math.sqrtの使用をこれまで頑なに避けてたのも、結果が Floatになるからだったり。

count = 0
23.upto(100){|n|
	cmb = 1.0
	1.upto(n/2){|r|
		cmb /= r
		cmb *= (n-r+1)
		count += (n-r == r) ? 1 : 2 if 1_000_000 < cmb
	}
}
p count

 Q55

問題文が難しかった。3割ぐらいは推測。

あっけなく答えが出たので to_s.reverse.to_i みたいなのをなくすべく、Integer#reverse を自作してみたら、かえって遅くなったし。

class Integer
	# 負数については考えてない。
	def reverse
		x = 0
		this = self
		begin
			this, rem = this.divmod(10)
			x = 10*x + rem
		end while 0 < this
		x
	end
end

count = 0
10.upto(10_000-1){|x|
	is_lychrel = true
	50.times{
		x = x + x.reverse
		if x == x.reverse
			is_lychrel = false
			break
		end
	}
	count += 1 if is_lychrel
}
p count
ツッコミを入れる

2011年02月08日 (火)

最終更新: 2011-02-09T20:16+0900

♪ [ProjectEuler] Q50

 Q50

  1. 100万未満の素数リストを作成。
  2. リストをコピーして作業領域とする。
  3. コピーしたリストの要素に、一つ右の位置の素数、二つ右の位置の素数、以下略を加えていき、都度、和が素数かどうか確かめる。

時間がかかるので逐一進捗を表示してる。この問題に魔法の一手なんてあるのかね。

primes = []
is_prime = lambda{|x|
	result = true
	primes.each{|prime|
		quotient, remainder = x.divmod(prime)
		if remainder == 0
			result = false
			break
		end
		break if quotient < prime
	}
	return result
}
2.upto(999_999){|x|
	primes.push x if is_prime.call x
}
puts "#{primes.size} primes under 1 million."

work = primes.dup
step = 0
primes_found = []
live_elements = work.size
while 0 < live_elements
	step += 1
	primes_found.clear
	live_elements = 0
	print "step #{step}\r"
	0.upto(work.size-1-step){|i|
		work[i] += primes[i+step]
		if work[i] < 1_000_000
			live_elements += 1
			primes_found.push work[i] if is_prime.call work[i]
		end
	}
	if primes_found.empty?
	elsif primes_found.size < 10
		puts "step #{step}: #{primes_found.join ' '}"
	else
		puts "step #{step}: #{primes_found.size} primes"
	end
end

魔法の一手はなくても……

  • 素数列の作成と和の評価を同時進行にできるかも。
  • 作業領域の範囲の狭め方が下手。
  • 奇数ステップ(偶数個の素数の和)は不要。
  • 100万に近い素数は不要。(それを一つ加えただけで 100万を超えるんでは項数を稼げない)
  • 項数の上限は求められる。

答えを出した後でググるのが楽しい。フォーラムは読んでないけど、多分これ以上ないっていうような答えが書いてありそうで、面白くなさそうな気がしてる。(理解できない数学的知識が使われてたら、print XXXXXXX(answer); って書かれてるのと変わらないから)

ツッコミを入れる

2011年02月07日 (月) 間違いさがし。『コールド メディシン A錠』の背表紙に「COLD MEDICINE CAPUSULE A」って書いてある。

最終更新: 2011-02-09T01:05+0900

♪ [ProjectEuler] Q47, Q48, Q49

 Q47

昨日よりちょっとはマシになったかと。アホすぎた素数判定を、素因数の数を数える処理と一体化した。でも 10秒以上かかります。

primes = [2]
have4primefactors = []

num_of_factors = lambda{|x|
	prime_factors = 0
	primes.each{|prime|
		quotient, remainder = x.divmod(prime)
		if quotient < prime
			prime_factors += 1
			break
		end
		if remainder == 0
			prime_factors += 1
			break if 4 < prime_factors
			x /= prime while x % prime == 0
			break if x == 1
		end
	}
	return prime_factors
}

x = 2
loop {
	x += 1
	print "#{x}\r"
	case num_of_factors.call(x)
	when 1
		primes.push x
		have4primefactors.clear
	when 4
		have4primefactors.push x
		p have4primefactors.first if have4primefactors.length == 4
	else
		have4primefactors.clear
	end
}

 Q48

恥ずかしいほどまっすぐで乱暴なスクリプトだけど、コンソールの表示も待てないくらいノーウェイトで答えが出るんだから仕方がない。

p (1..1000).inject(0){|sum,x| sum + x**x }

 Q49

  1. 4桁の素数リストを作る
  2. リストから条件を満たす二つの素数を選ぶ
  3. 計算で求めた三番目の数(三つのうち一番大きい)が条件を満たすか調べる。

10秒くらいかかります。

primes = []

is_prime = lambda{|x|
	result = true
	primes.each{|prime|
		quotient, remainder = x.divmod(prime)
		if remainder == 0
			result = false
			break
		end
		break if quotient < prime
	}
	return result
}

2.upto(9999){|x|
	primes.push x if is_prime.call x
}

primes_4digit = primes.last(primes.length - primes.rindex{|x| x < 1000 } - 1)
0.upto(primes_4digit.size-1){|i|
	p = primes_4digit[i]
#	next if p == 1487
	(i+1).upto(primes_4digit.size-1){|j|
		q = primes_4digit[j]
		r = q + q - p
		next if p.to_s.split(//).sort != q.to_s.split(//).sort or
		        q.to_s.split(//).sort != r.to_s.split(//).sort
		k = nil
		(j+1).upto(primes_4digit.size-1){|_k|
			if r == primes_4digit[_k]
				k = _k
				break
			elsif r < primes_4digit[_k]
				break
			end
		}
		if k
			puts "#{p} #{q} #{r}"
#			exit
		end
	}
}
ツッコミを入れる

2011年02月06日 (日)

最終更新: 2011-02-07T05:28+0900

♪ [ProjectEuler] Q46, Q47

 Q46

squares[]はソート済みなのに .include?()でそれを活かせないのが不満。

primes = [] # Omit 2. Even prime is not needed.
squares = [1]
def prime?(n)
	return false if 0 == n%2
	3.step(n/2, 2) {|x|
		return false if 0 == n%x
	}
	return true
end

x = 1
loop {
	x += 2
	squares.push((squares.size+1)**2) if squares.last < x
	if prime?(x)
		primes.push x
		next
	end
	print "#{x}\r"
	next if primes.any?{|prime| prime < x and squares.include?((x-prime)/2) }
	p x # answer
	break
}

 Q47

何の工夫もないのですんごく時間がかかる。

def prime_gt2?(n)
	return false if 0 == n%2
	x, upper_bound = 3, n/2
	while x <= upper_bound
		upper_bound, remainder = n.divmod(x)
		return false if 0 == remainder
		x += 1
	end
	return true
end

primes = [2]
have4primefactors = []
have4primefactor = lambda{|x|
	num_of_factors = 0
	primes.each{|prime|
		if x % prime == 0
			num_of_factors += 1
			break if 4 < num_of_factors
			x /= prime while x % prime == 0
		end
	}
	return num_of_factors == 4
}

x = 2
loop {
	x += 1
	print "#{x}\r"
	if prime_gt2? x
		primes.push x
		have4primefactors.clear
	elsif have4primefactor.call(x)
		have4primefactors.push x
		p have4primefactors.first if have4primefactors.length == 4
	else
		have4primefactors.clear
	end
}
ツッコミを入れる

2011年02月05日 (土)

最終更新: 2011-02-05T10:26+0900

♪ [ProjectEuler] Q14, 『珠玉のプログラミング』, Collatz予想

ちょっと前の日記から……

Q14

この漸化式は『珠玉のプログラミング』で見た。どうして収束するのかわからなかった。

見たっていうのはコラム4の問題で。

4.6問題

5.入力xが正の整数であるとき、以下のループが終了することを示してください。

while x != 1 do
  if xが偶数なら
    x = x/2
  else
    x = 3*x+1

これがまんま「コラッツの問題 - Wikipedia)」と呼ばれる未解決の問題だということに、今日「d.y.d.」を読んでいて気がついた。本の巻末のヒントを読み直してみたらこんなことが書いてあるし。

もし、この問題が解けたら、近くの大学の数学科に急いで行って、博士号を申請しましょう。

ひどい(笑)。わからなくて当然だ。遅刻学生が黒板の問題を宿題だと思って解いて提出したら、それは未解決問題だったとかいうのは、お話の世界なんだから。

ツッコミを入れる

2011年02月03日 (木)

最終更新: 2011-02-05T05:33+0900

♪ [ProjectEuler] Q45

 Q45

無駄にこったねえ。一瞬 JavaScriptで書こうとしたしたせいか、lambda多用。

generators = [
	lambda {
		n, tn = 1, 1
		lambda { n+=1; tn+=n; tn } # triangle numbers generator
	}.call,
	lambda {
		n, pn = 1, 1
		lambda { pn+=3*n+1; n+=1; pn } # pentagonal numbers generator
	}.call,
	lambda {
		n, hn = 1, 1
		lambda { hn+=4*n+1; n+=1; hn } # hexagonal numbers generator
	}.call
]
numbers = [1, 1, 1] # Ti, Pj, Hk
relations = "===" # Ti?Pj, Pj?Hk, Hk?Ti
actions = lambda {
	relation = lambda {|a,b|
		a==b ? '=' : a>b ? '>' : '<'
	}
	when_Nth_is_the_smallest = lambda {|i|
		lambda {
			numbers[i] = generators[i].call
			relations[i] = relation.call(numbers[i], numbers[(i+1)%numbers.size])
			j = (i-1) % relations.size
			relations[j] = relation.call(numbers[j], numbers[(j+1)%numbers.size])
			print "#{numbers[i]}\r"
		}
	}
	(0..2).map{|i| when_Nth_is_the_smallest.call(i) }
}.call
action_table = Hash.new {|h,rel|
	raise "missing action for '#{rel}'"
}
[
	["<<>", "<>>", "<=>", "=<>", "<>="], # when Ti is the smallest
	["><<", "><>", ">=<", "><="], # when Pj is the smallest (and Ti not)
	[">><", "<><", "=><"], # when Hk is the smallest (and the other not)
].each_with_index {|rels, i|
	rels.each {|rel| action_table[rel] = actions[i] }
}
action_table["==="] = lambda {
	puts numbers[0] # answer
	actions[0].call
}
loop {
	action_table[relations].call
}

相当な時間をかけて(求められていない)三番目の数字が出た。>57722156241751

六角数は三角数なので、三角数は無視できる。五角数と六角数を並べて比較していくだけ。

それがわからない。

チート。

Hn = n(2n-1) = (2n-1)(2n)/2 = m(m+1)/2 = Tm (m = 2n-1)

nは自然数だから、mは正の奇数になる。Triangle Numbersの奇数番目が Hexagonal Numbers.(逆も真) 言われたらそうかもね。それぞれの数列を眺めてたら気付くかもね。(それが無理なのはわかってる)

ツッコミを入れる

2011年02月02日 (水)

最終更新: 2011-02-03T09:33+0900

♪ [ProjectEuler] Q43, Q44

 Q43

愚直に。

divisors = [17, 13, 11, 7, 5, 3, 2, 1]
candidates = []
div = divisors.shift
div.step(999, div){|x|
	triplet = [x/100, x/10%10, x%10]
	candidates.push triplet if triplet.uniq!.nil?
}
until divisors.empty?
	div = divisors.shift
	candidates.size.times{
		candidate = candidates.shift
		(0..9).each{|d|
			if ! candidate.include?(d) && 0 == (100*d + 10*candidate[0] + candidate[1]) % div
				candidates.push [d] + candidate
			end
		}
	}
end
candidates.reject!{|c| c[0] == 0 }
p candidates.inject(0){|sum,c| sum + c.join("").to_i }

 Q44

最初に出てきた数字を書いたら通ったけど……。pentagonal numbersの名前の由来もわからんもんね。

_5 = [1] # [P1, P2,...]
_5_index = {1=>0} # 逆引き(Pn=>n-1)辞書
loop{
	i = _5.size
	_5.push(_5.last + 3*i + 1)
	_5_index[_5[i]] = i
	print "."
	(i-1).downto(0){|j|
		diff = _5[i] - _5[j]
		break if diff > _5[j]
		k = _5_index[diff]
		next unless k
		diff2 = _5[j] - _5[k]
		l = _5_index[diff2]
		next unless l
		puts
		puts  "D=#{_5[j]-_5[k]}"
		puts  "#{_5[j]-_5[k]} = P#{j+1}-P#{k+1}"
		puts  "#{_5[l]} = P#{l+1}"
		puts  "#{_5[j]+_5[k]} = P#{j+1}+P#{k+1}"
		print "#{_5[i]} = P#{i+1}"
		gets
	}
}
ツッコミを入れる

2011年01月25日 (火)

最終更新: 2011-02-01T10:42+0900

♪ [ProjectEuler] Q28, Q30, Q31, Q34, Q39, Q40, Q42, Q250

 Q28

sum = 1
1.upto((1001-1)/2){|d|
	sum += 2 * ( (2*d+1)**2 + (2*d+1)**2-3*2*d ) # (右上の数＋右下の数)の倍で対角4数の和
}
p sum

 Q30

9の5乗が6万弱なので6桁までの探索で十分。

t = [0, 1, 2**5, 3**5, 4**5, 5**5, 6**5, 7**5, 8**5, 9**5]
sum = 0
10.upto(999999){|n|
	sum += n if n == [n, n/10, n/100, n/1000, n/10000, n/100000].inject(0){|a,x| a+t[x%10] }
}
p sum

 Q31

キレイに書けたんではないかと。

coins = [200, 100, 50, 20, 10, 5, 2] # ,1
remainder = [200]
coins.each{|coin|
	remainder.length.times{|n|
		remain = remainder[n]
		while coin <= remain
			remain -= coin
			remainder.push remain
		end
	}
}
p remainder.size

メモリも CPUも節約できる真にすばらしい回答はこちら >Dreamshire | Project Euler Problem 31 Solution

target = 200
coins = [1,2,5,10,20,50,100,200]
ways = [1]+[0]*target
coins.each{|coin|
	coin.upto(target){|i|
		ways[i] += ways[i-coin]
	}
}
p ways[target]

ways[]のインデックスが残金(200-i㌺)で、値が場合の数、なのかな？

有名な問題で、SICPやら何やらに載ってるらしい。2005年以来封印してきたコンクリートマテマティクスを繙くときが来たのかもしれない。<もったいぶってないで勉強しろ

 Q34

def factorial(n)
	r = 1; n.downto(2){|x| r *= x }; r
end
factorials = [1]
9.times{ factorials.push( factorials.last * factorials.length) }

# 9の階乗が36万ちょっとなので 7桁までで十分
sum = 0
10.upto(9999999){|n|
	x = n
	m = 0
	while 0 < x
		m += factorials[x%10]
		x /= 10
	end
	sum += n if n == m
}
p sum

 Q39

Q9の発展。

best_p = 0
solutions_for_p = 0
3.upto(1000){|p|
	solutions = 0
	1.upto(p/3){|a|
		aa = a*a
		p_a = p-a
		a.upto(p_a/2){|b|
			solutions += 1 if aa + b*b == (p_a-b)*(p_a-b)
		}
	}
	if solutions_for_p < solutions
		solutions_for_p = solutions
		best_p = p
	end
}
p best_p

 Q40

# 一桁 1-9 9個
# 二桁 10-99 90個
# 三桁 100-999 900個
answer = 1
a = [1, 10, 100, 1000, 10000, 100000, 1000000]
width, count = 1, 9
n, pos = 1, 1
loop{
	count.times{
		if a.first < pos + width
			answer *= n.to_s[a.first-pos,1].to_i
			a.shift
			if a.empty?
				p answer
				exit
			end
		end
		n += 1
		pos += width
	}
	width, count = width+1, count*10
}

 Q42

names = ["A","ABILITY","ABLE",...]
name_values = names.map{|name| (0...(name.length)).inject(0){|wv,i| wv + name[i] - ?A + 1 } }.sort
count = 0
n, tn = 1, 1
until name_values.empty?
	name_values.shift while ! name_values.empty? and name_values.first < tn
	while ! name_values.empty? and name_values.first == tn
		count += 1
		name_values.shift
	end
	n, tn = n+1, tn+n+1	
end
p count

 Q250

わかんね。1^1, 2^2から 250250^250250までを、250で割った余りで 250種類に分類するところまでやったけど、そこから組み合わせの数を妥当な時間で計算できる気がしない。1要素で 250の倍数になるもの、ならないもの、2要素で 250の倍数になるもの、ならないもの、……、249要素で 250の倍数になるもの、を考えていくのかと思ったけど、それらの要素が有限なために自由には組み合わせられない(不可能な組み合わせが生じる)、単純に掛け合わせて可能な場合の数を求められない、というところで行き詰まった。ならばと、Q31で参考にしたスクリプトを下敷きに 250で割った余りをインデックスに、場合の数を値にした配列を使おうかと思ったけど、残金をインデックスにした場合と違って余りは循環する、というあたりで処理が一直線に進まなくてギブアップ。

memo = [[0, 1]]*250 # [exp, mod]
memo2 = (0...250).map{|x| x**250 } # exp=250特化版
set = [0]*250
1.upto(250250).each{|i|
	basemod = i%250
	mod = (memo[basemod][1] * (i-memo[basemod][0] == 250 ? memo2[basemod] : basemod**(i-memo[basemod][0]))) % 250
	memo[basemod] = [i, mod]
	set[mod] += 1
}
p set
ツッコミを入れる

2011年01月24日 (月)

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

♪ [ProjectEuler] Q11, Q14, Q15, Q16, Q18, Q67, Q20, Q22, Q24, Q25, Q26

約数とか素数とかでてくる問題は本当に勘弁して欲しい。

 Q11

愚直に書いただけ。

grid = <<GRID.strip.split(/\r\n?|\n/).map{|line| line.split(" ").map{|x| x.to_i } }
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
GRID

max = 0
0.upto(19) {|x|
	0.upto(19) {|y|
		if x <= 16
			# right
			max = [max, grid[y][x]*grid[y][x+1]*grid[y][x+2]*grid[y][x+3]].max

			# right-up
			if 3 <= y
				max = [max, grid[y][x]*grid[y-1][x+1]*grid[y-2][x+2]*grid[y-3][x+3]].max
			end

			# right-down
			if y <= 16
				max = [max, grid[y][x]*grid[y+1][x+1]*grid[y+2][x+2]*grid[y+3][x+3]].max
			end
		end
		if y <= 16
			# down
			max = [max, grid[y][x]*grid[y+1][x]*grid[y+2][x]*grid[y+3][x]].max
		end
	}
}
print max

 Q14

この漸化式は『珠玉のプログラミング』で見た。どうして収束するのかわからなかった。

 Q15

# 分子 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21
# 分母 20 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1

# 分子 39 37 33 31 29 23 7 5 2 2
# 分母 1
p 39*37*33*31*29*23*7*5*2*2

 Q16

digits = [1]
1000.times{
	carry = false
	0.upto(digits.length-1){|n|
		x = digits[n] * 2 + (carry ? 1 : 0)
		digits[n], carry = x%10, (x/10 != 0)
	}
	if carry
		digits.push 1
	end
}
p digits.inject(0){|sum,x| sum + x }

 Q18

底から上がっていきました。最近(少し上にも出てきた)本で見かけたヒープというデータ構造に似てるかもと思って一次元配列で三角形を表現したけど、子ノードが重なってるあたりがちょっと違ってて、親や子にアクセスするのに i/2, 2*i, 2*i+1 といった簡単な式は使えなかった。

numbers = <<NUMBERS.strip.split(/\s+/).map{|x| x.to_i }
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
NUMBERS

(Math.sqrt(numbers.length*2).floor-2).downto(0){|y|
	0.upto(y){|x|
		numbers[y*(y+1)/2+x] += [numbers[(y+1)*(y+2)/2+x], numbers[(y+1)*(y+2)/2+x+1]].max
	}
}

p numbers.first

 Q67

Q18の拡張。問題の数列が巨大なので載せないけど Q18と同じ方法で。

 Q20

Q16の拡張。

digits = [1]

2.upto(100){|n|
	carry = 0
	0.upto(digits.length-1){|i|
		x = digits[i] * n + carry
		carry, digits[i] = *(x.divmod(10))
	}
	while 0 < carry
		digits.push carry%10
		carry /= 10
	end
}

p digits.inject(&:+)

 Q22

英語を Ruby(1.8)に翻訳しただけ。

names = ["MARY","PATRICIA",...]
names.sort!

sum = 0
1.upto(names.length){|list_position|
	name = names[list_position-1]
	sum += list_position * (0...(name.length)).inject(0){|name_score,i| name_score + name[i] - 64 }
}
p sum

 Q24

最上位の桁から確定させていく。

remainder = 1_000_000
digits = (0..9).to_a
weight = (2..10).inject(&:*) # = (digits.size)!
answer = ""

until digits.empty?
	weight /= digits.size
	i = (remainder-1) / weight
	answer += digits.delete_at(i).to_s
	remainder -= weight * i
end
puts answer

 Q25

何度も出てきたパターン。数字が大きすぎるので(Rubyにとってはそうではないが)配列の要素として各桁の数字を保持する。

fib1, fib2 = [1], [1]
nth = 2
until 1000 <= fib2.length
	fib3 = []
	carry = 0
	0.upto(fib2.length-1){|keta|
		x = fib2[keta] + (fib1[keta]||0) + carry
		carry = x / 10
		fib3.push x % 10
	}
	fib3.push 1 if carry != 0
	fib1, fib2 = fib2, fib3
	nth += 1
end
p nth

 Q26

余りに注目。

longest_cycle = 0
longest_value = 0
1.upto(999){|n|
	numerator = 1
	numerator *= 10 while numerator < n
	a = [numerator]
	while numerator != 0
		numerator = a.last % n * 10
		i = a.index(numerator)
		if i
			if longest_cycle < a.length - i
				longest_cycle = a.length - i
				longest_value = n
			end
			break
		else
			a.push numerator
		end
	end
}
p longest_value
ツッコミを入れる

2011年01月23日 (日)

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

♪ [ProjectEuler] Q1-Q10

後ろの方の問題はしゃれにならない難しさだ。まずもって問題が理解できない。

 Q1

puts 3*(333*334/2) + 5*(199*200/2) - 15*(66*67/2)

 Q2

ぐだぐだ考えないで足し合わせていくだけでも良かった気がする。

def even_fibonacci(an_2, an_1)
	4*an_1 + an_2
end

a = [0, 2]
until 4_000_000 < a.last
	a[0], a[1] = a[1], even_fibonacci(*a)
end
print a[0] + (a[1] - 3*a[0])/4

 Q3

案ずるより産むが易し。

n = 600851475143

i = 3
while i*i < n
	if n%i == 0
		print i, " "
		n = n/i
		next
	end
	i += 2
end
print n

 Q4

12個列挙して一番大きいのを選びました。こんなんでいいのか？

999.downto(900){|p|
	999.downto(900){|q|
		x = (p*q).to_s
		if x == x.reverse
			puts "#{x} = #{p}*#{q}"
		end
	}
}

 Q5

# 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
#   2 3 2 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
#   2 3 2 5   7 8 9 10 11 12 13 14 15 16 17 18 19 20
#   2 3 2 5   7 2 9 10 11 12 13 14 15 16 17 18 19 20
#   2 3 2 5   7 2 3 10 11 12 13 14 15 16 17 18 19 20
#   2 3 2 5   7 2 3    11 12 13 14 15 16 17 18 19 20
#   2 3 2 5   7 2 3    11    13 14 15 16 17 18 19 20
#   2 3 2 5   7 2 3    11    13    15 16 17 18 19 20
#   2 3 2 5   7 2 3    11    13       16 17 18 19 20
#   2 3 2 5   7 2 3    11    13        2 17 18 19 20
#   2 3 2 5   7 2 3    11    13        2 17    19 20
#   2 3 2 5   7 2 3    11    13        2 17    19
puts 2*3*2*5*7*2*3*11*13*2*17*19

 Q6

これでは和の二乗から各数の二乗を素直に引くのと手間が変わらない。

puts (1..100).inject(0){|sum,x| sum += x*(5050-x) }

<追記@2011-03-11>Bignumを使わずに済ませられる効用があったみたい。オーバーフローとか Rubyにはないから気づかなかった。</追記>

 Q7

力押し。

class Boo
	def initialize(interval)
		@interval = interval
	end
	def boo?(t)
		t % @interval == 0
	end
end

a = []
n = 1
loop {
	n += 2
	next if a.any?{|boo| boo.boo?(n) }

	a.push Boo.new(n)
	break if 10000 <= a.length
}
puts n

 Q8

これはひどい(笑)

#Find 99999    0件
#Find [98]{5}  0件
#Find [987]{5} 3件(99879,79778,98787)
print 9*9*8*7*9

後付けで、8×7 > 9×6 なのは確認したけども……。

 Q9

素直に書き下しただけ。

1.upto(332){|a|
	aa = a*a
	b_c = 1000 - a
	(a+1).upto(b_c/2){|b|
		c = b_c - b
		if c*c == aa + b*b
			puts "#{a} * #{b} * #{c} = #{a*b*c}"
			exit
		end
	}
}

 Q10

10分以上かかっちゃってダメ。

ツッコミを入れる
最近 これより古い日記はありません
カテゴリ[ProjectEuler]に属するセクションのみを表示しています。(他のカテゴリも表示)
Generated by tDiary version 2.3.3.20091124
Powered by Ruby version 2.5.5-p157