/ 最近 .rdf 追記 設定 本棚

脳log[2011-08-26~]



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


2011年08月25日 (木) A following B と B followed by A の間違いやすさは異常。ちなみにどちらも BA. (これとかこれのことですよ)


2011年08月24日 (水) Firefox6. ただしくつまらない方向に向かってるよね。そういう大衆迎合的なのは IEと Google Chromeに任せておけばいいものを。「browser.urlbar.formatting.enabled」URLの大部分が霞んで読みにくい。ドメイン(の一部)を強調するにしても他にやりようはないのか。そのうち http://も隠されるぞ。あるのに見えないとか最悪だ。確認手段は https接続のときにこれまでも表示されていた緑背景・青背景部分だけの方がいいんじゃないのか。「alert is not defined.」alertだけでなく confirmと openも上書きされてる。他にもあるだろう。アドレスバーを簡易コンソールにできなくなった(危ぶんだが bookmarkletはこれまで通り動いた)。アドレスバーのスクリプトが実行されてないわけではない。alertが目を付けられた理由を誰か短く説明して。【Bug 451833 – Highlight the domain name in the address bar】【Bug 527530 – Social Engineering Issue with "javascript:" URLs


2011年08月23日 (火) 予約した。『["電気式華憐音楽集団 10th anniversary white box"]』アマゾンでは特典のピックはつかないけど。


2011年08月19日 (金) [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

2011年08月18日 (木) 「アドミナブル・アンド・サイ」なんで abdominal(アブドミナル)じゃないの? アドミナブルはスペルがわかりません。■■■ いや、検索結果の数は「アブドミナル アンド サイ」の方が多かった。1620対3000 by google. ただし Bingでは逆転して 256対165。英語的に、ボディビル的に、正しいのはどっち?■■■ Vagrant Storyには abdomenっていう部位があった。難しかった。かといって stomachもいまいちだしねえ。


2011年08月17日 (水) な、なんだってー。構文木がコウブンボクじゃないとか……。もしやと赤黒木を Wikipediaでみると、こちらもセキコクボクではなかった。赤黒黄とかどんな冗談。もうひとつ、B木もビーボクじゃなかった。ぎゃー。もういい。red-black treeと B treeで十分だ。(こういうデータ構造を本で読んだのって Windows PCを触り始めた翌年の、オブジェクト指向やらオートマトンの本を図書館で借りたのと同じ頃(だけ)だ。県立図書館++。それにくらべて今の自分は……)

最終更新: 2011-08-21T01:48+0900

[SakuraEditor] 正規表現検索。トリック。不完全。

 (?imx-imx)        孤立オプション
                     i: 大文字小文字照合
                     m: 複数行
                     x: 拡張形式
 (?imx-imx:式)     式オプション
 補記 1. 文法依存オプション
  + ONIG_SYNTAX_RUBY
    (?m): 終止符記号(.)は改行と照合成功
  + ONIG_SYNTAX_PERL と ONIG_SYNTAX_JAVA
    (?s): 終止符記号(.)は改行と照合成功
    (?m): ^ は改行の直後に照合する、$ は改行の直前に照合する

サクラエディタが自動で mフラグをくっつけて m/pattern/km みたいなのを正規表現ライブラリに渡すので油断していた。インラインでフラグを変更する方法がある。

ところで、mフラグは実装間で意味に一貫性が無く、また鬼車のフラグも間違いを誘うような名前をしているので注意が必要。みんな ECMAScriptに倣え!

 + 孤立オプションの有効範囲は、その孤立オプションを含んでいる式集合の終わりまでである
   例. (?:(?i)a|b) は (?:(?i:a|b)) と解釈される、(?:(?i:a)|b)ではない

フラグの意味に加えて、その有効範囲の面倒くさいことよ。これに対処するくらいなら他の方法を考えるレベル。Onigmoは PCREみたいに、パターンのコンパイル時オプションとして「改行」を意味する文字を指定することに対応してくれないのかな。>NEWLINE CONVENTIONS(pcre.txt)


mフラグを OFFにする目的は何かといえば、JavaScriptと bregonigにおいては $ と ^ が改行前後にマッチしないように、Rubyにおいては . が改行にマッチしないように、ということだ。

「$ と ^ が改行前後にマッチしないように」は言い換えると「^ と $ が文書の頭と末尾にだけマッチするように」ということだが、サクラエディタにおいては従来、文書の先頭・末尾と各行文字列の先頭・末尾は区別できず、各行文字列末尾と改行直前の区別は曖昧だった。であれば、この問題は複数行検索が実現するときまで先送りしても差し支えないだろう。(ないよね?)


2011年08月15日 (月) トラックボール。解像度がフルHD以上の液晶ディスプレイが広すぎると感じたらマウスから持ち替えてみる価値はある。


2011年08月11日 (木) [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."

2011年08月06日 (土) これまで何度も Operaを使ってみようとして 10分もせずに挫けた理由。Tabキーがフォームにしかフォーカスを移動しない。Ctrl+矢印だとつきとめたので半年後くらいにまた試す。■■■Opera. 画面内の要素に一発でフォーカスが当たるのはすごく良いんだけど、まさしく前々から望んでいた機能なんだけど、Ctrl+↓だと画面内の一番下、Ctrl+↑だと画面内の一番上の要素にフォーカスするのはいただけない。そんなんでは Ctrl+(↑↓↓↓……)とか Ctrl+(↓↑↑↑……)みたいな操作を常に要求されてしまうではないか。キーを押し直したくはない。■■■@2011-08-10 必ずしも一番上とか下とかではなかった。予測できません。


2011年08月05日 (金) 「○○する」と書かず「○○となる」と書く例を頻繁に見かける。ぎごちなくみえて好きじゃない。


2011年08月04日 (木) 戦闘機にとって人間は脆弱なパーツに過ぎない。


2011年08月03日 (水) はてブで『耳刈ネルリ』の文字をみかけた。売れるといいね。次作を待ってるんだけどファミ通文庫は『荒野の恋』や『暴風ガールズファイト』『カーリー』を最後まで出せなかった根性なしだからなあ。『ヒツギでSOSO!』の人も続刊がないし、森橋ビンゴの『ラビオリ・ウェスタン』も単発で終わっちゃった。売れる物を売るだけじゃ先細りするばかりなのに。もっと、俺好みのを。

最終更新: 2011-08-04T03:29+0900

[tDiary] PageDownキーによるスクロール量をごにょごにょするプラグイン。

日と日の境が行き過ぎてしまわないようにスクロール量を制限する。

うっとうしいかな? スムーズスクロールも効かないしな。でも AutoPagerizeの機能の一部としてあってもいいような気もする。

動作確認済み> Firefox 5.0, Internet Explorer 9, Safari 5.0.2, Opera 11.50

* この日記(tDiary-2.3.3.20091124)にはまだ js_urlメソッドとか enable_jsメソッドとか無いのです。