脳log[2011-09-16～]

最終更新: 2011-09-17T05:22+0900

♪ [javascript] trailing commas ,

いくつかの点(文字列の行継続とか)で実装の追認をしてる 5th ed.ならいざしらず 3rd ed.では配列の末尾のカンマは無視できないだろう(IE8が正しい?)と思って昨日日記に書いたのだけど、よくよく読むとやっぱり IEが間違ってるっぽかったので消したのだった。

11.1.4 Array Initialiser

Syntax
 ArrayLiteral:
  [ Elision_opt ]
  [ ElementList ]
  [ ElementList , Elision_opt ]
 ElementList:
  Elision_opt AssignmentExpression
  ElementList , Elision_opt AssignmentExpression
 Elision:
  ,
  Elision ,

The production ArrayLiteral : [ ElementList , Elision_opt ] is evaluated as follows:
1. Evaluate ElementList.
2. Evaluate Elision; if not present, use the numeric value zero.
3. Call the [[Get]] method of Result(1) with argument "length".
4. Call the [[Put]] method of Result(1) with arguments "length" and (Result(2)+Result(3)).
5. Return Result(1).

The production Elision : , is evaluated as follows:
1. Return the numeric value 1.

The production Elision : Elision , is evaluated as follows:
1. Evaluate Elision.
2. Return (Result(1)+1).

1. Elision_opt(=カンマの 0以上の並び)は、カンマひとつにつき配列の長さをひとつ伸ばす。

2. ElementList: Elision_opt AssignmentExpressionや、ElementList: ElementList , Elision_opt AssignmentExpressionのように、Elision_optの右に AssignmentExpressionが隣接してるときはその数え方で自然。

3. ArrayLiteral: [ Elision_opt ] や、ArrayLiteral: [ ElementList , Elision_opt ] の場合は、Elision_optのカンマはその個数プラス1の要素を作り出すように見えるので、末尾のカンマがひとつ無視されたように感じる。

こんな結果になるなんて、余計なお世話もいいところだと思うんだけどな……

>>> [1,2,3,,,].length
5
>>> [1,2,3,,].length
4
>>> [1,2,3,].length
3
>>> [1,2,3].length
3

サイズ1の undefined配列を作れたりはするけど……(べつに嬉しくない)

>>> [].length
0
>>> [,].length
1

ちなみに JSONでは、思想から予想される通りに、末尾の余分なカンマは不許可。要素の省略(undefinedになる)もできない。ちなみに配列と違ってオブジェクトの初期化では、末尾の余分なカンマは不許可(3rd ed.しか確かめてないが)。

Syntax
 ObjectLiteral :
  { }
  { PropertyNameAndValueList }
 PropertyNameAndValueList :
  PropertyName : AssignmentExpression
  PropertyNameAndValueList , PropertyName : AssignmentExpression

例えばこれが JavaScriptのオブジェクト {prop:value,...}や Rubyの連想配列 {key=>value,...}や Cの enum {LABEL=1,...}の話であれば、末尾のカンマをあえて無視するのもいいだろう。要素の追加や並べ替えに便利なんだから。でも、JavaScriptの配列はダメだ。そこでは初期化の際に要素の省略ができる。空白に意味があるのだ。カンマの前後の空白の要素に関して、末尾だけ特別扱い(してるように見える)なんてのは不細工きわまりない。

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