最終更新: 2011-04-14T01:54+0900
まったく、CViewCommander::Command_REPLACE_ALL ってのは人類の理解の範囲を超えている。
これ、あえて異なる複数の分類を一括りのリストにしてるけど、実際のコードがそうなのだ。こんな処理が一つの関数の中に、変数を共有しながら―しかも型を偽って本来とは違う使い方が特定の処理ルートではなされていたりする―、一部の処理を共有しながら、インターリーブされてる。
BugReport70.patch (1.7KiB, 2011-04-07 02:50)
submit(<commit以前)はしない。怖すぎる。
「「すべて置換」は置換の繰返し」フラグが ONのときの対策がまだ。
コミットログも読まずに軽率な修正。>BugReport70.rev2.patch (2.7KiB, 2007-04-07 06:50)
これから読む。>「SourceForge.net Repository - [sakura-editor] Revision 1049」, 「SourceForge.net: Sakura Editor: Detail: 1636751 - 行置換のオプション化＆問題修正」
うむ。削除したコードがなぜあえて論理座標だったのかわからない。
って書いて削除したコードがパッチにあるけど、一つの行が複数のレイアウト行に分割されてることがある。一行処理して次の行……と思ったらまだ折り返された同じ行にいた、とか。前にも別件で書いてるけど、折り返しと矩形選択(+文字一括挿入／+置換)は本当にひどい組み合わせ。結果を予測できるものにするためには選択範囲の末尾の行から処理をしないといけない。そうすると文字の削除や挿入による折り返し位置の変化が後の処理に影響を与えないので。でもそうはなってない。だから、結果を維持する労力を割く必要もない「未定義」の動作だと考えてしまう。
最終更新: 2011-08-20T02:12+0900
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
まったく恥ずかしい。答えが合わないとなって当然問題を読み直してはいたんだけど、日を置いて改めて読んでみたら問題が何を求めてるのかが見えてきた。"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]}"
最終更新: 2014-04-25T14:53+0900
迷路より簡単。右下から左上に向かって、右の要素と下の要素を参照しながら順番に処理するだけ。
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.
まだまだ簡単。最下段から、行を右へ左へ処理しながら上へ向かうだけ。こういう、問題・入力に依存して可変長のメモリを確保したりしない、そのうえ問題を単純に走査するだけの解法は安心できる。
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なんだけど。
N×N確保していた作業メモを 1行分だけで済ませるようにスクリプトを修正。
コメントに「transpose:問いの右から左が、下から上への処理になる。」ってあるけど、今問題文を見ると左から右になってる。まあ、どっちからどっちでも変わらないからね。問題文が左から右になったからってわけではないけど、アップデート後は上から下の処理に変えてる。下から上だと、どうしてもその必然性を探してしまうから。
シリーズの締め。迷路のときとは違って 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を使う(内部キー)かはやっぱり決めかねるけど。