脳log[20120119] Problem 10, 12, 14, 17, 19, 21, 23

最終更新: 2012-01-20T00:09+0900

♪ [ProjectEuler] Problem 10, 12, 14, 17, 19, 21, 23

穴埋め。解ける問題がはやなくなってきたから……(完全になくなってはいないはずっ)。

 Problem 10

時間コストを空間コストに置き換えて。

arr = [true] * 2_000_000
sum = 0
2.upto(arr.size-1){|i|
	next unless arr[i]
	sum += i
	i.step(arr.size-1, i){|j|
		arr[j] = false
	}
}
p sum
p Process.times

 Problem 12

Rubyに頼った。prime_divisionのこと。

require 'mathn'

trinums = lambda{
	tri, n = 0, 1
	return lambda{
		tri, n = tri+n, n+1
		return tri
	}
}.call

loop{
	tri = trinums.call
	div = tri.prime_division.inject(1){|d,_| f,e = *_; d*(e+1) }
	if 500 < div
		puts tri
		p Process.times
		exit
	end
}

 Problem 14

ゴールから攻めようとか小賢しいことは考えずに。

number_of_chain = lambda{
	memo = {1=>1}
	this = lambda{|n|
		return memo[n] || (memo[n] = 1 + this[n%2==0 ? n/2 : 3*n+1])
	}
	return this
}.call

p (1...1_000_000).max_by{|_| number_of_chain[_] }
p Process.times

 Problem 17

面倒なだけ。

cc = lambda{
	return this = lambda{|n|
		count, num = 0, n

		digit1000 = num / 1000
		if 0 < digit1000
			count += this[digit1000] + 'thausand'.length
			num -= digit1000 * 1000
			count += 'and'.length if num != 0
		end

		digit100 = num / 100
		if 0 < digit100
			count += this[digit100] + 'hundred'.length
			num -= digit100 * 100
			count += 'and'.length if num != 0
		end

		digit10 = num / 10
		if 2 <= digit10
			count += {
				20=>'twenty'.length,
				30=>'thirty'.length,
				40=>'forty'.length,
				50=>'fifty'.length,
				60=>'sixty'.length,
				70=>'seventy'.length,
				80=>'eighty'.length,
				90=>'ninety'.length,
			}[digit10*10]
			num -= digit10 * 10
		end

		if num != 0
			count += {
				1=>'one'.length,
				2=>'two'.length,
				3=>'three'.length,
				4=>'four'.length,
				5=>'five'.length,
				6=>'six'.length,
				7=>'seven'.length,
				8=>'eight'.length,
				9=>'nine'.length,
				10=>'ten'.length,
				11=>'eleven'.length,
				12=>'twelve'.length,
				13=>'thirteen'.length,
				14=>'fourteen'.length,
				15=>'fifteen'.length,
				16=>'sixteen'.length,
				17=>'seventeen'.length,
				18=>'eighteen'.length,
				19=>'nineteen'.length
			}[num]
		end
		return count
	}
}.call

p (1..1000).inject(0){|sum,n| sum + cc[n] }

 Problem 19

問題文が難しかった。閏年の条件として "A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400." って書いてあったけど、centuryって XX01年から XY00年の 100年間を指す語だと思ってるから、"a century"が XY00年のことだけを示してるとは思わなくて、結果的に 100の条件を読み飛ばした上に 400の条件を逆にとらえてた。

days_of_month = lambda{|year,month|
	return 31 if [1,3,5,7,8,10,12].include?(month)
	return 30 if [4,6,9,11].include?(month)
	return 29 if year % 400 == 0
	return 28 if year % 100 == 0
	return 29 if year % 4 == 0
	return 28
}

dow = 1 # 日月火水木金土=0123456. 1=Monday. 1900-01-01 was a Monday.
(1..12).each{|month|
	dow = (dow + days_of_month[1900,month]) % 7
}
# Now dow indicates the day of 1901-01-01.

count = 0
(1901..2000).each{|year|
	(1..12).each{|month|
		count += 1 if dow == 0
		dow = (dow + days_of_month[year,month]) % 7
	}
}
p count

 Problem 21

愚直に(←これしか書いてなくない？)。

d = lambda{|n|
	divsum = 1
	t, tmax = 2, n
	while t < tmax
		q, r = *n.divmod(t)
		divsum += (t!=q ? t+q : t) if r == 0
		t, tmax = t+1, q
	end
	return divsum
}

p (1..10000).inject(0){|sum,n|
	dn = d[n]
	sum + (n < dn && d[dn] == n ? n+dn : 0)
}

 Problem 23

そのまま(←愚直にを言い換えただけ)。

class Integer
	def abundant?
		divsum = 1
		t, tmax = 2, self
		while t < tmax
			q, r = *self.divmod(t)
			divsum += (t!=q ? t+q : t) if r == 0
			t, tmax = t+1, q
		end
		return self < divsum
	end
end

expressible = [false] * (28123+1)
abundant = []
(1..(28123-12)).select(&:abundant?).each{|n|
	abundant << n
	abundant.each{|a|
		break if expressible.size <= a+n
		expressible[a+n] = true
	}
}
p (1..28123).inject(0){|sum,n| sum + (expressible[n] ? 0 : n) }