脳log[2011-04-01～]

最終更新: 2011-08-20T02:12+0900

♪ [ProjectEuler] Problem 85

 Problem 85

incorrect

Target = 2_000_000
Size = Math.sqrt(Target*2).floor+1
a = (1..Size).map{|i| i*(i+1)/2 }
answer = 0
until a.empty?
	jv = a.last
	answer = [a.map{|iv| iv*jv }.min_by{|v| (v-Target).abs }, answer].min_by{|v| (v-Target).abs }
	a.pop
end
p answer

 @2011-04-14

まったく恥ずかしい。答えが合わないとなって当然問題を読み直してはいたんだけど、日を置いて改めて読んでみたら問題が何を求めてるのかが見えてきた。"nearest solution" ではなく "area" だったとさ。

Target = 2_000_000
Size = Math.sqrt(Target*2).floor+1
a = (1..Size).to_a
answer = [0,0]
until a.empty?
	j = a.last
	answer = ([answer] + a.map{|i| [i,j] }).min_by{|i,j| (i*(i+1)/2*j*(j+1)/2 - Target).abs }
	a.pop
end
puts "#{answer[0]} * #{answer[1]} = #{answer[0]*answer[1]}"

最終更新: 2014-04-25T14:53+0900

♪ [ProjectEuler] Problem 81, 82, 83

 Problem 81

迷路より簡単。右下から左上に向かって、右の要素と下の要素を参照しながら順番に処理するだけ。

matrix = DATA.lines.map{|ln| ln.chomp.split(",").map(&:to_i) }
raise "正方行列でない！" if matrix.size != matrix[0].size
(matrix.size-1).downto(0){|i|
	(matrix[i].size-1).downto(0){|j|
		incr = nil
		incr = matrix[i][j+1] if j+1 < matrix[i].size
		incr = matrix[i+1][j] if i+1 < matrix.size && (!incr || matrix[i+1][j] < incr)
		matrix[i][j] += incr if incr
	}
}
p matrix[0][0]
__END__
content of matrix.txt here.

 Problem 82

まだまだ簡単。最下段から、行を右へ左へ処理しながら上へ向かうだけ。こういう、問題・入力に依存して可変長のメモリを確保したりしない、そのうえ問題を単純に走査するだけの解法は安心できる。

Matrix = DATA.lines.map{|ln| ln.chomp.split(",").map(&:to_i) }.transpose # transpose:問いの右から左が、下から上への処理になる。
Order = Matrix.size
raise "正方行列でない！" if Matrix.size != Matrix[0].size

row = Matrix[0].dup # 1-line memo. row is now at the first(top) line of Matrix.
1.upto(Order-1){|i|
	# move from up ↓↓↓↓↓↓↓↓↓↓
	0.upto(Order-1){|j|
		row[j] += Matrix[i][j]
	}

	next if i == Order-1 # 最後の行は横移動不要(※禁止ではない)。最小値だけを選び取って答えにするから。

	# move right →→→→→→→→→→
	0.upto(Order-2){|j|
		src, dst, move_cost = row[j], row[j+1], Matrix[i][j+1]
		row[j+1] = src + move_cost if src + move_cost < dst
	}

	# move left ←←←←←←←←←←
	(Order-1).downto(1){|j|
		src, dst, move_cost = row[j], row[j-1], Matrix[i][j-1]
		row[j-1] = src + move_cost if src + move_cost < dst
	}
}
p row.min
__END__
content of matrix.txt here.

Array#transposeを使う機会があるなんて思わなかった！好きなメソッドは transpose(今日だけ)。ま、使わなくてもいいんだけど線形にアクセスするために。ま、メモリ構造からは遠く離れた Rubyなんだけど。

 @2013-05-11 アップデート

N×N確保していた作業メモを 1行分だけで済ませるようにスクリプトを修正。

コメントに「transpose:問いの右から左が、下から上への処理になる。」ってあるけど、今問題文を見ると左から右になってる。まあ、どっちからどっちでも変わらないからね。問題文が左から右になったからってわけではないけど、アップデート後は上から下の処理に変えてる。下から上だと、どうしてもその必然性を探してしまうから。

 Problem 83

シリーズの締め。迷路のときとは違って 80×80ともなると手当たりしだいに探索の手を伸ばしていくと 10分以上の時間がかかる。優先度を付けると insertのコストが加わったにもかかわらず、笑っちゃうぐらい一瞬で終わった。

C++だったら queueの実装として std::multimapを使うところだけど配列をヒープ構造にするのもありだ。

Matrix = DATA.lines.map{|ln| ln.chomp.split(",").map(&:to_i).freeze }.freeze
raise "正方行列でない！" if Matrix.size != Matrix[0].size
matrix = Matrix.map{|ln| Array.new(ln.size) }
size = matrix.size
moved = lambda{|i,j, l,m|
	return false if not (0...size).include?(l) or not (0...size).include?(m)
	src, dst, move_cost = matrix[i][j], matrix[l][m], Matrix[l][m]
	return false if dst && dst < src + move_cost

	matrix[l][m] = src + move_cost
	return true
}
matrix[0][0] = Matrix[0][0]
queue = [[0,0]]
insert = lambda{|l,m|
	val = matrix[l][m]
	queue.insert(queue.index{|i,j| val <= matrix[i][j] }||queue.size, [l,m])
}
until queue.empty?
	i,j = *(queue.shift)
	break if matrix.last.last and matrix.last.last <= matrix[i][j]
	[[i-1,j],[i+1,j],[i, j-1],[i,j+1]].each{|l,m|
		if moved[i,j, l,m]
			insert[l,m]
		end
	}
end
p matrix.last.last
__END__
content of matrix.txt here.

<queue>ヘッダには priority_queueクラスがあるし、<algorithm>には make_heap, pop_heap, push_heap といった、配列(RandomAccessIteratorをそなえたコンテナ)にかぶせて使うための関数があった。そりゃあるわなあ。ソートキーが要素のみから算出できない今回の場合に priority_queueを使う(外部キー)か、multimapを使う(内部キー)かはやっぱり決めかねるけど。

最終更新: 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}

最終更新: 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" の有無だけだった。俺のも同等に速い。