/ 最近 .rdf 追記 設定 本棚

log[ProjectEuler: 2011-08-26]



20110826() [BAD BOY] (25) 歩道の車止めに右のハドルバーエドをカツーンとぶつけてよろめきながら石垣につっこんだーンが外れて前輪は一見してぶれてないけどクイックリリースとVブレーキアームとフロトフークにごっつい擦り傷が……黒いフークに白い擦り傷……錆びたらどうすんだ■バイクだったりチャリだったりこんなふうにして二年に一本くらいの割りでズボンの膝に穴をあけてる■この場所1号線のバイパス沿いなんだけどあまりに人通りが少ないからなのか点滅信号の交差点でもないのに歩行者信号だけが待ってても青にならない確かめてないけど歩行者が押しボタンを押して歩行者信号を青にしたときはすべての車用の信号が赤にならないと危険だただでさえ歩道橋の陰になって左折車から横断歩道が見えないのに歩行者信号が赤であることドライバーが慣れてしまっていたらどうなるでしょうね

最終更: 2011-09-17T21:10+0900

[ProjectEuler] Problem 102, Problem 107

 Problem 102

説明はできない条件は二つで足りると思ったが間違いだったので三つにしたそうしたら通った

require 'matrix'
AX, AY, BX, BY, CX, CY = 0,1,2,3,4,5
O = Vector[0,0]
count = 0
DATA.each_line{|ln|
	nums =  ln.chomp.split(',').map(&:to_i)
	a, b, c = Vector[nums[AX],nums[AY]], Vector[nums[BX],nums[BY]], Vector[nums[CX],nums[CY]]
	ab, ao, ac = b-a, O-a, c-a
	bc, bo, ba = c-b, O-b, a-b
	ca, co, cb = a-c, O-c, b-c
	ab_cosOAB, ab_cosCAB = ao.inner_product(ab) / ao.r, ac.inner_product(ab) / ac.r
	bc_cosOBC, bc_cosABC = bo.inner_product(bc) / bo.r, ba.inner_product(bc) / ba.r
	ca_cosOCA, ca_cosBCA = co.inner_product(ca) / co.r, cb.inner_product(ca) / cb.r
	count += 1 if ab_cosOAB >= ab_cosCAB and bc_cosOBC >= bc_cosABC and ca_cosOCA >= ca_cosBCA
}
p count
__END__
content of triangles.txt here.

一応の説明を試みると三本の辺それぞれから見て辺を構成しない頂点が原点より見上げる位置にあるどうかをコサインの大小で判定してるただコサインは X軸対称なので見上げてるのか見下ろしてるのかは実際のところわからないだから二つの辺では不十分で三つの辺すべてで判定しなければいけない※この最後の文ではやっぱり説明できてない気がする


検索した外積なんて(言葉しか)知りません問題文Cartesian planeもわからなかったので無視したんだったなんで Cartesianがデカトになるの?

 Problem 107

メソド名を決めるまでで 9割が終わってる

軽い辺から順番に有効にしていき有効な辺のみで最初にすべての頂点を通ることができたとき最後に有効にした辺この辺は隣接する点のうち最も離れている二つを結ぶ最短経路これより軽い辺を組み合わせてこの二点を結ぶことはできないしこれより重い辺を組み合わせて結ぶのは不必要な無駄を抱えるあとはこのように確定した辺の両端を一個の点とみなすようにしながら再帰的に確定していく

def find_the_required_edge_with_maximum_weight(matrix)
	active_edge = Hash.new{|h,k| h[k] = {} }
	(0...matrix.size).map{|src|
		((src+1)...matrix.size).reject{|dst| matrix[src][dst].nil? }.map{|dst|
			[src,dst]
		}
	}.inject(&:+).sort_by{|src, dst| matrix[src][dst] }.each{|src, dst| # lighter edge first
		active_edge[src][dst] = active_edge[dst][src] = true

		visited = [false] * matrix.size
		firstvisit = {src=>true, dst=>true}
		until firstvisit.empty?
			v = firstvisit.shift[0]
			visited[v] = true
			if visited.all?
				return [src, dst]
			end
			active_edge[v].each{|nxt,|
				firstvisit[nxt] = true unless visited[nxt]
			}
		end
	}
	return nil
end

matrix = DATA.lines.map{|ln| ln.chomp.split(",").map{|_| _ == '-' ? nil : _.to_i } }
sum_of_weight = matrix.map{|row| row.compact.inject(&:+) }.inject(&:+) / 2
reduced_sum_of_weight = 0
loop{
	src, dst = *find_the_required_edge_with_maximum_weight(matrix)
	weight = matrix[src][dst]
	break if weight == 0
	reduced_sum_of_weight += weight

	matrix[src][dst] = matrix[dst][src] = 0
	matrix.map!{|row| row.map!{|_| _ && weight < _ ? nil : _ } }
}
puts "#{sum_of_weight - reduced_sum_of_weight} saved. (#{sum_of_weight} -> #{reduced_sum_of_weight})"

__END__
content of network.txt here.

もう限界が近いのですよ風呂の中でああでもないこうでもないと考えてやっと辿り着いたのが上の答えsum_of_weightの割る 2は忘れるので注意


Problem 107を検索した「最小全域木「プリム法「クラスカル法

クラスカル法のつもりで書いたのが下上のより 10倍速い0.5秒が 0.05秒になるレベル

matrix = DATA.lines.map{|ln| ln.chomp.split(",").map(&:to_i) }
sum_of_weight = matrix.map{|row| row.inject(&:+) }.inject(&:+) / 2
reduced_sum_of_weight = 0

trees = (0...matrix.size).map{|v| {v=>true} }
(0...matrix.size).map{|src|
	((src+1)...matrix.size).reject{|dst| matrix[src][dst] == 0 }.map{|dst|
		[src,dst]
	}
}.inject(&:+).sort_by{|src, dst| matrix[src][dst] }.each{|src, dst| # lighter edge first
	i_src, i_dst = trees.index{|tree| tree[src] }, trees.index{|tree| tree[dst] }
	if i_src != i_dst
		reduced_sum_of_weight += matrix[src][dst]
		trees[[i_src, i_dst].min].update(trees[[i_src, i_dst].max])
		trees.delete_at([i_src, i_dst].max)
		break if trees.size == 1
	end
}

puts "#{sum_of_weight - reduced_sum_of_weight} saved. (#{sum_of_weight} -> #{reduced_sum_of_weight})"

__END__
content of network.txt here.

ある段階で最短に見えた経路も木が育って起点が増えるにつれて最短でなくなることがある気がしたのでまわりくどい条件を課してたんだけどいらん心配だったみたい起点とか関係なしに軽い辺から繋いでるんだから連結して起点が増えたところで後から付け替える余地はなかった

[単行] R. ブランデンベル, P. グリッツマン【最短経路の本】 シュプリンガー・ャパン株式会社をもう一回読んでみよう当時はグラフっていえば棒グラフ?ってな知識しかなかったからね世界の秘密をひとつ覗いた気になったもんだちなみに最近は非線形科学(語:複雑系自己組織化創発冪乗則)とかシスム生物学がブーム


20110819() [ProjectEuler]っそうこれは線型方程式を解くだけなので簡単でなんて言ってみたいぜ手で解く手順は見当がついても脳のキャパをオーバーしてるのでうまくコングできないWishlist『プログラミングのための線形代数を掘り出してきたのでそのうち

最終更: 2011-09-10T23:55+0900

[ProjectEuler] Problem 101

 Problem 101

(↑↑のリンク先を見て)行列を使うことがわかればなんと最初に考えた階差数列とか二項係数を使った手順とはなんだったの要の逆行列の計算(もう忘れた)Rubyがやってくれるしだけど最初は行列の要素が整数だったせいで正しい逆行列が得られなくてハマった

浮動小数点数や有理数その他に対応するためにMatrix#inverseは演算の手続きだけを提供してるということなんだと思うけど全くでたらめな結果が正常に返ってくるのは驚き元の行列と逆行列の要素がどちらも整数になることがわかってる場合はなおさら型指定がないことで扱いが難しくなってしまってる

このへん(ja.wikipedia.org)まで理解したいなあ

require 'matrix'

# (a0,a1,a2,a3,...) -> (n) -> a0 + a1*n + a2*n^2 + a3*n^3 +...
Poly = lambda{|*kk|
	kk.reverse!
	return lambda{|n|
		return kk.inject(0){|sum,k|
			sum * n + k
		}
	}
}
Q = [1,-1,1,-1,1,-1,1,-1,1,-1,1]
QSeq = Poly[*Q] # (n) -> 1 − n + n^2 − n^3 + n^4 − n^5 + n^6 − n^7 + n^8 − n^9 + n^10

Main = lambda{
	sum_of_FIT = 0
	a, n = [QSeq[0]], 0
	until a == Q
		aseq = Poly[*a]
		raise if aseq[n] != QSeq[n]
		n += 1 while aseq[n] == QSeq[n]
		sum_of_FIT += aseq[n]
		a = Next_OP[QSeq, n]
	end
	p sum_of_FIT
}

Next_OP = lambda{|seq, k|
	return (Matrix[
		*(1..k).map{|i| _ = [1.0]; (k-1).times{ _.push(_.last*i) }; _ }
	].inverse * Matrix[
		*(1..k).map{|_| [seq[_]] }
	]).column(0).to_a.map(&:round)
}

Main.call

20110811() [Ruby] 配列などコンテナとその要素をまとめて freeze! する freeze! メソドが欲しい

最終更: 2011-08-20T02:11+0900

[ProjectEuler] Problem 96, Problem 97, Problem 99, Problem 93

 Problem 96

ナンバープレイス30秒くらいかかります。数独ソルバは前にも書いたことがある(20100511)その時とくらべてしたことといえば優先度を付けたくらい場合によってそれが効果的なのは Problem 83のとき(20110325p01.03)に実感してる

def main
	tl3digits = []
	numarr = ''
	DATA.each_line{|line| line.chomp!
		if /^\d{9}$/ =~ line
			numarr << line
			tl3digits << solve(numarr)[0,3].to_i if numarr.size == 9*9
		else
			numarr = ''
		end
	}
	puts "#{tl3digits.size} puzzles were solved."
	puts "The sum of 3-digit numbers is #{tl3digits.inject(&:+)}."
end

def solve(nums)
	pns = possible_numbers(nums) # [[index,X,Y,...],...]
	pns_shortest = 10
	pns_shortest_index = -1
	pns.each_with_index{|pn,i|
		if pn.size-1 < pns_shortest
			pns_shortest = pn.size-1
			pns_shortest_index = i
		end
	}
	if 10 <= pns_shortest
		return nums # solved!
	elsif 0 == pns_shortest
		return nil # false branch. no solution.
	else
		pn = pns[pns_shortest_index]
		index = pn.shift
		return pn.map{|n|
			nums_ = nums.dup
			nums_[index] = n
			solve(nums_)
		}.compact[0] # nil or solution
	end
end

def possible_numbers(nums)
	pns = []
	(0...9).each{|y|
		(0...9).each{|x|
			i = index(x,y)
			next unless nums[i] == ?0
			pns << [i] + ((?1..?9).to_a - determined_numbers(nums, h_indices(x,y)) - determined_numbers(nums, v_indices(x,y)) - determined_numbers(nums, b_indices(x,y)))
		}
	}
	return pns
end

def index(x,y)
	return x + y*9
end
def h_indices(x,y)
	return y*9 ... (y+1)*9
end
def v_indices(x,y)
	return (0...9).map{|y| x + y*9 }
end
def b_indices(x,y)
	i = index(x-x%3, y-y%3)
	return [i, i+1, i+2, i+9, i+10, i+11, i+18, i+19, i+20]
end
def determined_numbers(nums, indices)
	return indices.map{|i| nums[i] }.reject{|n| n == ?0 }
end

main;

__END__
content of sudoku.txt here.

 Problem 97

Bignumがある Rubyでは関係ないけど64ト整数を前提に小細工(ープ展開)

ten = 56866
978807.times{
	ten = (ten * 256) % 10000000000
}
p (ten + 1) % 10000000000

 Problem 99

場違いに簡単な問題

max_lineno, max_number = 0, 0
lineno = 0
DATA.each_line{|line| line.chomp!; next if line.empty?; lineno += 1
	base, exp = *line.split(",", 2).map(&:to_i)
	number = exp * Math.log(base)
	max_lineno, max_number = lineno, number if max_number < number
}
p max_lineno
__END__
content of base_exp.txt here.

 Problem 93

スクリトは不完全4つの数{1,2,5,8}と四則演算とカッコを使って 36を作る方法がわからない

Ops = [:+, :-, :*, :/].freeze
Ops3 = Ops.product(Ops, Ops).freeze
max_fnxn = 0 # fnxn: first non-expressive number
max_fnxn_c4 = nil
(0..9).to_a.combination(4){|c4|
	xns = [true]
	c4.permutation.to_a.product(Ops3).each{|_| nums, ops = *_
		num = nums.last.to_f
		3.times{|i|
			num = num.send(ops[i], nums[i])
		}
		xns[num.to_i] = true if num.finite? and 0 < num.to_i and num.ceil == num.floor
	} # 24 * 64
	fnxn = xns.index(nil) || xns.length
	if max_fnxn < fnxn
		max_fnxn = fnxn
		max_fnxn_c4 = c4
	end
} # 210
puts "{#{max_fnxn_c4.sort.join(',')}} forms 1 to #{max_fnxn-1} numbers."

例えば、(5 - (1/2)) * 8 = 36数字の順列 ABCDと演算子の順列___をそのまま連結して A_(B_(C_D)) を作るだけでは全ての式を網羅できてなかった左右対称になるのを除いて次の 3通りに順列と順列を組み合わせた((A_B)_C)_D, (A_(B_C))_D, (A_B)_(C_D)

Ops = [:+, :-, :*, :/].freeze
Ops3 = Ops.product(Ops, Ops).freeze
Evaluate = lambda{|exp|
	s = []
	until exp.empty?
		h = exp.shift
		if h.kind_of?(Symbol)
			s[-2] = s[-2].send(h, s[-1])
			s.pop
		else
			s.push(h)
		end
	end
	return s[-1]
}
max_fnxn = 0 # fnxn: first non-expressive number
max_fnxn_c4 = nil
(0..9).to_a.combination(4){|c4|
	xns = [true]
	c4.map(&:to_f).permutation.to_a.product(Ops3).each{|_| nums, ops = *_
		[
			[nums[0], nums[1], ops[0], nums[2], ops[1], nums[3], ops[2]], # ((A_B)_C)_D
			[nums[0], nums[1], nums[2], ops[0], ops[1], nums[3], ops[2]], # (A_(B_C))_D
			[nums[0], nums[1], ops[0], nums[2], nums[3], ops[1], ops[2]]  # (A_B)_(C_D)
		].each{|exp|
			num = Evaluate.call(exp)
			xns[num.to_i] = true if num.finite? and 0 < num.to_i and num.ceil == num.floor
		} # 3
	} # 24 * 64
	fnxn = xns.index(nil) || xns.length
	if max_fnxn < fnxn
		max_fnxn = fnxn
		max_fnxn_c4 = c4
	end
} # 210
puts "{#{max_fnxn_c4.sort.join(',')}} forms 1 to #{max_fnxn-1} numbers."

20110330() Project Euler Problem 851999998だと思ったが incorrectだと蹴られる9が並んでるので慎重に桁を数えたがそういうミスではなかったもう解らない

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

20110325() 見えないところでの思いやりが本当の思いやりなのだと思う「誰にでも見える思いやりなんてのは思いやりではないのではないだろう たぶん最近多い ACCMについてこの CMいいと思うけどなあ行動を促してるんだと思う思うだけではダメで行動に移さなければいけない思いは見えないけど行動すればそれは誰にでも見えるそれを思いやりと(そのCMでは)呼ぶんだと見せる必要はないけど見えても嘘にはならないんじゃない(こういうことは書いてもわかり合えるとは思わないのでコメトしないでここに書いてる)目立つのを嫌って行動できない日本人は多そう考えすぎそれも言い訳を子供の時にたたき込まれてたら照れもなくできるんだろうとも思うトと

最終更: 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を使う(内部キ)かはやっぱり決めかねるけど


20110320()

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

20110315()

最終更: 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に特有の値だけを加減するように


20110313() 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 }

20110312() 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/dndは最大公約数が 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にできないのもわかりにくいProcblocklambdaの微妙な違いによるものなのだろう

Rubyによる他所の Project Eulerの解答をみていてこういう書き方も知ってるけどカウンタが Floatになっちゃうのが不満

1.upto(1/0.0){|n| p n }

あれ? FixnumFloatになるのは stepった

1.step(1/0.0){|n| p n } # 1.0, 2.0, 3.0,...

明示的に Fixnumの増: 1を指定しても nFloat. この違いはなんだろう


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]"

20110310() 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は一回しか使わない10external node.
  2. 先頭の桁(外側のドの最小値)を最大にするためにexternal node10,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. 分子と分母のバラスの取り方は勘で

20110308() 本の: グラックカドライバーをアップデトしない低能達ップデトしないよ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. 10n乗は常に n+1桁になる
  2. 9n乗は 10n乗より小さいため n+1桁には絶対に届かずある程度までは n桁を保つがそのうち n-1桁に落ちる
  3. 8n乗は 9n乗より早く n-1桁に落ちる
  4. 以下 1n乗まで
  5. 「ある程度って具体的には?
  6. 10を約0.954乗すると 9になる910より 0.046(=1-0.954)程度小さい数だ
  7. この 0.046がいくつ集まると 10一個分小さい(=桁が落ちる)ことになるだろう21.7(=1÷0.046)
  8. 9の場合21乗までは n乗が n桁を保っているが 22乗は違う

というーリーをひねり出した910より 0.046(=1-0.954)程度小さい数だってくだりがいかにも苦しい小数だからごまかしがきいてるけどったり 10一個分小さくなる場合は nn-1っち? (たぶんまだ n桁だな11がそ)

ともあれ明かされてみればワンライナーの問題だったよ

p (1..9).inject(0){|sum,n| sum + (1/(1-Math.log10(n))).floor }

常用対数を直接求めるメソドが用意されてるあたりが Rubyだなとおもた

 Q64

連分数っていうらしいanの求め方、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を使うのってインチキくさくない?(だから使ってないんだけ)


20110301()

最終更: 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 Euler100問解いてみたトレーションとか聞いたこともない単語なんだけど……

中学生の時に 350 の一の位は何かという問題が出たでも Problem 188は何乗したらいいかもわからない下手の考え休むに似たりっていうけどどうしたもんかなあない知恵を絞るのも悪くないと思うんだけど


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

最終更: 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の前後の空白は右下に向いて(11列目)(22), (12列目)(23), (13列目)(21) の並びで現れるはずだ
  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の集合から22の集合から33の集合から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以上の素数を組に加えても最小の組み合わせになりうる計算量の増大の仕方がひどくてこれ以上桁数を増やして試行するのは無理だというのに


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

ゃないよね

q = a 0 + 10 a 1 + 10 2 a 2 + + 10 n a n ( a n は 0以上 9以下の整数) = ( a 0 + a 1 + a 2 + + a n ) + 9 a 1 + 99 a 2 + + ( 10 n - 1 ) a n

a0+a1+a2++an3の倍数の整数 q3の倍数です。

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

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


 @2011-02-19

4100を作るから下2桁だ510を作るから下1桁だけを見ればいい

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

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

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