最終更新: 2011-09-10T23:55+0900
(↑↑のリンク先を見て)行列を使うことがわかればなんとか。最初に考えた階差数列とか二項係数を使った手順とはなんだったのか。要の逆行列の計算(もう忘れた)は 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-21T01:48+0900
(?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-20T02:11+0900
ナンバープレイス。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.
Bignumがある Rubyでは関係ないけど、64ビット整数を前提に小細工(ループ展開)。
ten = 56866
978807.times{
ten = (ten * 256) % 10000000000
}
p (ten + 1) % 10000000000
場違いに簡単な問題。
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.
スクリプトは不完全。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-04T03:29+0900
日と日の境が行き過ぎてしまわないようにスクロール量を制限する。
うっとうしいかな？ スムーズスクロールも効かないしな。でも AutoPagerizeの機能の一部としてあってもいいような気もする。
動作確認済み> Firefox 5.0, Internet Explorer 9, Safari 5.0.2, Opera 11.50
* この日記(tDiary-2.3.3.20091124)にはまだ js_urlメソッドとか enable_jsメソッドとか無いのです。