脳log[2011-09-14～]

最終更新: 2011-08-31T22:36+0900

♪ 日本人とルール。

なんか日本人って違うぞ？という疑問に答える本(著者はホンダの人)と大好きなコピペ。ただ、裏をかいたつもりでも法律の恣意的な運用で逮捕されたりはするのかな？ひろゆきとかホリエモンはどれでしょう。

ずるい!? なぜ欧米人は平気でルールを変えるのか (ディスカヴァー携書)
青木 高夫
ディスカヴァー・トゥエンティワン
￥ 1,050

世の中には５種類の人間が居る。

ルールを知らない奴。
ルールを守る奴。
ルールを破る奴。
ルールの裏をかく奴。
ルールを作る奴。

書いた順番に弱い。

最終更新: 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. グリッツマン【最短経路の本】 シュプリンガー・ジャパン株式会社』をもう一回読んでみよう。当時はグラフっていえば棒グラフ？ってな知識しかなかったからね。世界の秘密をひとつ覗いた気になったもんだ。ちなみに最近は非線形科学(類語：複雑系、自己組織化、創発、冪乗則)とかシステム生物学がブーム。