脳log[2010-04-07～]

最終更新: 2013-08-20T01:04+0900

♪ [Ruby] 「少なくとも優秀ではない」ことを否定する(≠優秀である)。

「makeplex salon：あなたのスキルで飯は食えるか？　史上最大のコーディングスキル判定 (1/2) - ITmedia エンタープライズ」経由で「人生を書き換える者すらいた。: 人材獲得作戦・４　試験問題ほか」

粘菌でも迷路問題を解けるというのだから負けてはいられない。Rubyで一時間半弱かかった。

#! ruby
# coding: Shift_JIS

# 迷路データ

maze = <<MAZE
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************
MAZE

# マップ

class Point
	def initialize(x, y)
		@x, @y = x, y
	end
	attr_reader :x, :y

	def ==(other)
		@x == other.x && @y == other.y
	end
	def to_s
		"(#{@x},#{@y})"
	end

	def left
		Point.new(@x-1, @y)
	end
	def right
		Point.new(@x+1, @y)
	end
	def up
		Point.new(@x, @y-1)
	end
	def down
		Point.new(@x, @y+1)
	end
end

class Map
	def initialize(maze)
		lines = maze.strip.split(/\r\n?|\n/)
		@height = lines.length
		@width = lines.first.length
		y = -1
		@map = lines.map{|line| y += 1
			x = -1
			line.split(//).map{|ch| x += 1
				if(ch == 'G')
					@goal = Point.new(x, y)
					nil
				elsif(ch == 'S')
					@start = Point.new(x, y)
					nil
				elsif(ch == '*')
					-1
				else
					nil
				end
			}
		}
	end
	attr_reader :height, :width
	attr_reader :start, :goal

	def []=(point, value)
		@map[point.y][point.x] = value
	end
	def [](point)
		@map[point.y][point.x]
	end
	def up(point)
		return -1 if point.y-1 < 0
		return @map[point.y-1][point.x]
	end
	def down(point)
		return -1 if self.height <= point.y+1
		return @map[point.y+1][point.x]
	end
	def left(point)
		return -1 if point.x-1 < 0
		return @map[point.y][point.x-1]
	end
	def right(point)
		return -1 if self.width <= point.x+1
		return @map[point.y][point.x+1]
	end
end

map = Map.new(maze)
#puts "width×height = #{map.width}×#{map.height}"
#puts "start:#{map.start} / goal:#{map.goal}"

map[map.goal] = 0;
#puts "goal=#{map[map.goal]}"

# 先端

nodes = [map.goal]
while node = nodes.shift
	next if node == map.start
	[node.left, node.right, node.up, node.down].each{|nxt|
		case(map[nxt])
		when -1
			# 壁
		when nil
			# 未踏
			map[nxt] = map[node] + 1
			nodes.push(nxt)
		else
			# 既に到達したルートがある
			if(map[node] + 1 < map[nxt])
				map[nxt] = map[node] + 1
				nodes.push(nxt) unless nodes.include?(nxt)
			end
		end
	}
end

# Map to result

map.height.times{|y|
	map.width.times{|x|
		point = map[Point.new(x,y)]
		print point == -1 ? '***' : ("% 3d"%point)
	}
	puts
} if false

result = maze.strip.split(/\r\n?|\n/)

node = map.start
until node == map.goal
	[node.left, node.right, node.up, node.down].each{|nxt|
		if(map[nxt] == map[node] - 1)
			node = nxt
			result[nxt.y][nxt.x] = '$'
			break
		end
	}
end

puts result.join("\n")

ノードっていうのはひとマスのこと。「先端」っていうコメントが適当すぎる(植物では頂端分裂組織っていうらしい)。方針はゴールからスタートに向けて、一マス移動するごとに一ポイントを加算しながら全方位に触手を伸ばしていき、すでに他の触手が通過した道は、自分が最適な場合にのみ侵入するこの判断は不要。全ての触手が行き場を失うかスタートに到達するかしたら終了。スタートから一ずつ減っていく数字をたどると(一少ない数をもつ隣接マスが二つ以上あっても解答に求められていないので無視する)ゴールへ着き、それが最短経路(だったらいいな)。

最初は粘菌方式をまねようと思ったが、通路をすべて覆った状態からスタートして、スタートとゴールにつながっていない島を切り捨て、袋小路から撤退するのはいい。遠回りと近道を取捨選択するためにどういう評価をすればいいのかを決められなかった。どうすればいいの？粘菌は何を考えてる？例えば

二番目のリンク先のトラックバックを見てる。みんな優秀なのね、C++で一時間もかかってないし。何人かが言及している「BFS」。それって一般的知識？ 幅優先探索(Breadth-First Search)か最良優先探索(Best-First Search)の略だということはわかった。

壁のもつポイントを -1 に設定したことで、壁に侵入しないことを保証する when節を省略してもよかったんじゃないだろうか。気付くのが遅れたが。

ゴールにも $ って書き込んでら。(スタートには書きこまんように気をつけたんだが)

粘菌すごい。

培地に、三個以上の餌を置く。粘菌は迷路の実験のように最短距離を結ぶか？

結果は違った。

粘菌は、丸く、複数の経路を持つ管を作った。「最短経路だと一カ所故障したら必ず孤立する場所が出ます。だから粘菌は、一カ所が故障しても全体はつながり、なおかつ距離がなるべく短い経路を作ったのです」

部分部分がどういう反応をするとそういう結果になるんだろ？？？

 @2013-08-19 こういうことらしいです。わかりません。

粘菌の行動原理は、量子ドット間の近接場光を介したエネルギー移動プロセスに類似している

最終更新: 2010-04-04T06:25+0900

♪ [無題]

 「麻枝准dis - 感想考察批評日常」

そんなあなたに、とある科学の超電磁砲の 4巻はいかがでしょう。俺はこの巻を読んで、作者は冗談では済ませられない、のっぴきならない一歩を踏み出したと感じた。まだ失望してもムカついてもいないが、危ういものを感じながら 5巻を待っている。

最終更新: 2010-04-17T12:02+0900

♪ [無題]

 比例計算

 「全長200kmの道路があります。
 最初の100kmを時速50kmで、
 次の100kmを時速100kmで走りました。
 200kmの道路全体では時速何キロで走りましたか?」

 に非常によく似た問題があった。

 「(100km/h + 50km/h) ÷ 2 で 75km/h!!」

 とお客さまに答えそうになる馬鹿が出た…。
 (省略)

悲しいことに全然笑えない。100km(50km/hで走った距離)と 100km(100km/hで走った距離)を見比べて 1:1だから、足して 2で割って平均を出せばいいやと考えるのは仕方がないというか、頭の中で方程式は解けないからと目の前の数字に飛びついちゃったんだよね。(上の問題はただのたとえらしいけど)算数の問題って火曜サスペンスと同じで与えられる判断材料(数字)に過不足がないことが当たり前になってるから、それに慣れてると考えずに反射的に数字をこねくって答えを出してしまいがち例えばというのもありそう。

(馬鹿ですが)気を取り直して、この場合は走行距離でなく走行時間の比率を基にすれば暗算できたんだろうか。

「全長200kmの道路があります。
  200kmを走り終わったとき、
  2/3の時間を時速50kmで、
  1/3の時間を時速100kmで走っていました。
  道路全体では時速何キロで走りましたか?」

  50 × 2/3 + 100 × 1/3 = 66 (km/h)

ブコメを見た。水溶液濃度の話も出てた。そして最も簡単な考え方は「200km ÷ 3h = 66km/h」だった。ああなんて遠回り。

「調和平均だっけ」とも書かれていた。調和平均の定義を調べて計算したら「2×100×50÷(100+50)」なぜだか(自分の頭ではマジカル)答えが出た。でもこれだと走行距離が 95kmと 105kmだったときにどうすればいいかわからなくなりそう。

最終更新: 2010-04-04T07:43+0900

♪ [正規表現] 正規表現の空の文字クラスのブラウザ実装 > 文字クラス(suika.fam.cx)

まとめはリンク先に任せるとして、最新の Opera(10.51)ではどうかね、と思ってアドレスバーに javascript……と打ち込んだら空の文字クラスのテストスクリプトと思しき、まさに今打ち込もうとしていたものが補完された。笑える(他に Operaの使い道はないのか)。このときの履歴だろう。さておき、結果は

// Opera10.51
/[]/.test("a") //=> false
/[^]/.test("a") //=> true

9.61のときとは違って一般に期待される結果になっているよう。次いで IE8の結果は……どちらもスクリプトエラー。

// IE8
/[]/.test("a") //=> "正規表現の中に ']' を指定してください。" (Perlと同じ。だけど IEのバージョンももう 8だよ)
/[^]/.test("a") //=> "正規表現の中に ']' を指定してください。" (Perlと同じ。だけど IEのバージョンももう 8だよ)

// このエラーが導くのは、パターンのこういう解釈と結果。
/[]]/.test("]") //=> true
/[^]]/.test("]") //=> false

変わっていない。ECMAScript3に準拠するならマッチ結果の食い違いはともかくエラーはないはずだけど。

ちょっと前にニュースになった IE9 Preview版(IEBlog : About the Platform Preview)もせっかくだしインストールして試してみた。「IEBlog : The New JavaScript Engine in Internet Explorer 9」なんて記事も見つけたし。結果は /[]/.test("a") も /[^]/.test("a") もクラッシュ。残念至極。

最終更新: 2010-03-29T02:44+0900

♪ [無題]

 Google画像検索についての続き。>前回

Alt+←で前のページに戻れるようになっている。余計な閲覧履歴がはさまって一回で戻れなかったりもしない一方ソニーは。ただ、一瞬前の画像に戻るような動作を見せてから前のページに移動するのが後付けっぽくてスマートでないし、まれにページ移動に失敗して前の画像に移動するだけのことがある。行き過ぎて前の画像に戻りたいこともあるだろうし、どの画像から第二のモードに入ったかを覚えておいたらいいと思うんだけどね。

最終更新: 2010-03-28T06:40+0900

♪ TSF関連再読

• TSF を使う (1) - Windows Input Method の歴史 - NyaRuRuの日記
• Speak Up: Support Dictation With Text Services Framework

最初のリンク先の「余談その 1 - 誰がプリエディットを描画しているか？」で説明されているように、未確定文字列を IMEに表示してもらうアプリケーションと自分で描画するアプリケーションが存在する。メモ帳とサクラエディタは前者。ワードパッドと Firefoxは後者。全然意識してなかったけど、確かに Firefoxなどでは確定前の文字列によってその後ろの文字列が押し流されていく。また、テキストを選択した状態で日本語を入力し始めた場合の動作も異なっていて、Firefoxやワードパッドでは入力をキャンセルしたとしても最初に選択されていた文字列が消えてしまう。確定前の文字列がアプリケーションの状態を変更することがあるのに全然気づいてなかった。マウスクリックによって文字列の挿入位置を確定直前に変更することもできなくて、未確定文字列が確定されてしまうだけ。こんなにも使い勝手がちがうとは(全然気にしてなかったけど)。

 Google日本語入力

たなかゆう……で「田中優美清春香菜」「田中優美清秋香菜」が出てくるのが強みだねえ。2ch語や四字熟語のもじりなどが上位にきて間違いを助長されると困るけど。

Windows XP SP3 + Opera10.10 + Google日本語入力 = Operaクラッシュの件(Google日本語入力をインストールしたところ、Operaが起動できなくなりました。 - Google 日本語入力ヘルプ)で触れられていたが、Google日本語入力は TSFでいうところの Text Serviceとして動いていて IMM32に直接は対応していないらしいので、TSFベースの文脈依存変換のテストに使えるかと思ってインストールしたのだが Google日本語入力に文脈依存変換はないみたい。少なくとも(実装方法が似てそうな)再変換機能は確実にないらしく、いくつも要望があがっている。

再変換は使わないからいいんだけどこっちの方、「『半角/全角』で日本語入力をオフにした際、それまでの未確定文字を全て消したい - Google 日本語入力ヘルプ」「IMEをオフにしたとき、変換確定していない文字を消去できるようにして欲しい - Google 日本語入力ヘルプ」「変換確定前の半角／全角キー押下によるキャンセル動作 - Google 日本語入力ヘルプ」この一つの要望だけはかなえてもらわないと使えない。

 MSDN

Parameters

(省略)

acpEnd [in]

Specifies the ending character position. If this parameter is 1, then return all text in the text store.

(省略)

Remarks

(省略)

If acpEnd is -1, then it should be handled as if set at the end of the stream. Otherwise, it will be greater than or equal to zero.

なんで 1？最初の一文字を取得したいときはどうすれば？と思ったけど、-1の間違いだよね。びっくりさせる。

最終更新: 2010-03-25T02:39+0900

♪ 5月12日発売 [CD] 【BKK to NRT】 キングレコード

BKK to NRT
Neko Jump
キングレコード
￥ 2,940

1stアルバム『[DVD Audio] 【Neko Jump (初回限定版)】 bmi』を再販売してくれるほうが嬉しいけどね。