最終更新: 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を使う(内部キー)かはやっぱり決めかねるけど。
最終更新: 2011-03-21T02:43+0900
Problem 31と同じ問題。その解答(20110125p01.03)。ただし、Problem 31には通用した俺の解法では全然終わらない。
Target = 100
a = [1] + [0]*Target
(Target-1).downto(1){|pick|
0.upto(Target-pick){|i|
a[i+pick] += a[i]
}
}
p a[Target]
素数ごとに一から再試行してるけど計算量はたかがしれてた。
require 'mathn'
prime_gen = Prime.new
primes = []
prime_gen.each{|prime|
primes.push prime
a = [1] + [0]*prime
primes.each{|pr|
0.upto(prime-pr){|i|
a[i+pr] += a[i]
}
}
answer = a.index{|x| 5000 < x }
if answer
p answer
exit
end
}
まったくひどい解答。76から続くシリーズの締めらしく、何も考えないと計算量が膨大になる。手続き的な解法から一歩進む必要がある。それか一分ルールを無視して何時間もかけて良しとするか。
Target = 100000
a = [1] + [0]*Target
(Target-1).downto(1){|pick|
0.upto(Target-pick){|i|
a[i+pick] += a[i]
}
}
p a.index{|x| x%1_000_000 == 0}
最終更新: 2012-02-29T17:34+0900
前のバージョンはここ(20110312p01.02)。step2を最適化*すると倍くらい速くなって 1分半(ウチのPC基準で。C++だとコンマ1秒)。それに伴い素因数の組み合わせを求める必要がなくなったので、100万要素の配列の配列が 100万要素の Fixnum配列になってメモリ使用量が再び数MBレベルになった。
LIMIT = 1_000_000
pfs = Array.new(LIMIT+1, 1)
count = LIMIT*(LIMIT+1)/2 - 1 # 1) 2からLIMIT以下の分母 d につき d 通りの分子を予め計上する。
2.upto(LIMIT){|d| # 0) 2からLIMIT以下の分母 d に対して、
print d,"\r"
d.step(LIMIT, d){|_| pfs[_] *= -d } if pfs[d] == 1
# 2) 分子が d で分母が d の倍数になるものを加減する。
count += pfs[d]/pfs[d].abs * (LIMIT/d)*(LIMIT/d+1)/2 if pfs[d].abs == d
}
p count
一週間後にはこのコードが理解できなくなってること請けあい。
ググった>「Dreamshire | Project Euler Problem 72 Solution」。φ関数の値を合計するとかで、Rubyでも10秒未満。Problem 69に出てきた関数だけど、その問題はインチキしたから理解してないんよね。
LIMIT = 1000000
phi = (0..LIMIT).to_a
2.upto(LIMIT){|n|
n.step(LIMIT, n){|m|
phi[m] *= (n-1.0)/n
} if phi[n] == n
}
p phi.inject(&:+).floor-1
繰り返しの構造は似てるのにこの実行時間の差はなんだ？ と思ったら print d,"\r" の有無だけだった。俺のも同等に速い。
* 全体でみると同じ数字を足したり引いたりを繰り返してる気がしたので個々の dに特有の値だけを加減するように。
最終更新: 2011-03-14T21:52+0900
♪ 前後の衛星写真をくらべて言葉を失った。地形がかわっとる。町がない。思い出せばリポーターは最初からこの状況を伝えようとしていた。そして、言葉からでは想像が難しかったことが衛星写真で明らかになったように、衛星写真でわかることは実際の万分の一もない。
1号機に続いて 3号機でも(建物内の水素ガスが)爆発。2号機の冷却機能喪失。原発設置のハードルがさらに上がってしまったのが残念。非現実的なコストを積み上げて想定される災害対策を行っても、心情的に無理なんじゃないか。
専門家は癌を死の病だと盲目的におそれる患者(キャスターがその役)に対するように、不安を煽らないように煽らないようにしゃべっていた。でもそれでは不信を招く。これだけ浴びたらこういう症状が出ます、という情報も知りたい。当事者には汚染の有無だけが重要で、汚染はあるんだし、避難勧告に従っていれば大丈夫っていっても、避難できなかった人が被曝して「「除染」後の検査でも高い放射線量の値を示したため、第２次被曝医療機関に搬送されていた」んだけど。
不勉強。
最終更新: 2011-03-14T23:14+0900
昨日(20110312p01)の延長。Problem 72の解答と同じ部分より違う部分を見つける方が難しい。
LIMIT = 12000
pfs = Array.new(LIMIT+1){ [] }
count = 0
2.upto(LIMIT){|d| # 0) LIMIT以下のすべての分母 d に対して、
print d,"\r"
d.step(LIMIT, d){|_| pfs[_] << d } if pfs[d].empty?
n_min, n_max = d/3, (d-1)/2 # (n_min, n_max]
next unless n_min < n_max
count += n_max - n_min # 1) とりあえず一通りの分子を計上し、
# 2) 8分の6など通分可能なものを差し引きする。
(1..(pfs[d].size)).each{|r|
cms = pfs[d].combination(r).map{|pf| pf.inject(&:*) }
count -= (-1)**(r%2+1) * cms.map{|cm| n_max/cm - n_min/cm }.inject(&:+)
}
}
p count
問題文のヒントを最大限に利用したが数分かかる。総当たりでなく組み合わせ単位でテストしてその順列を計上したらマシになるかも。順列を考えるときに先頭の桁に 0を置くようなミスを犯しそうだがね。
factorial = [1,1] # [0!,1!,...]
factorial.push(factorial.size*factorial.last) until 9 < factorial.size
chain_length = lambda{
memo = {
169 => 3, 363601 => 3, 1454 => 3,
871 => 2, 45361 => 2,
872 => 2, 45362 => 2
}
f = lambda{|start|
return memo[start] if memo.has_key?(start)
next_ = start.to_s.chars.map{|c| factorial[c[0]-?0] }.inject(&:+)
return memo[start] = 1 + (start == next_ ? 0 : f.call(next_))
}
}.call
p (1...1_000_000).inject(0){|sum,n| sum += 1 if chain_length.call(n) == 60; sum }
最終更新: 2011-03-15T00:15+0900
「HCF(n,d)=1」には用語の説明があると思ったんだけどなかった。n/dの nと dは最大公約数が 1の既約分数だとすると意味がとおるので HCF=Highest Common Factorだと決めた(でっちあげ)。
分数とはなんぞやだとか切断だとか小難しく考えてしまったが(実際には考えられるほど知らない)、ワンライナーだった。3/7より少し小さい100万個の分数を小数になおして、一番小さいものを見つける。有理数にして比較しないのは時間がかかるから。公約数をみつけたりする時間だろうか。
require 'rational'
p Rational(*(2..1_000_000).inject([0,1]){|answer,d|
answer[0]/answer[1].to_f < (d*3-1)/7/d.to_f ? [(d*3-1)/7,d] : answer
})
Project Euler Problem #71 « KeyZero Conversation
分数を初めてならった小学生が必ず間違える分数の足し算(通分せずに分母どうし分子どうしを加算する)にこんな意味があるとか！
分単位のお時間がかかります。(訳:一時間はかからないけど……)
何倍も速くなるので「Integer#prime_division」を使う代わりに 100万要素の配列を使ってる。トレードオフで使用メモリは数MBから 100MB超になるが。 小手先のチューンよりアルゴリズムを改良しろってのはもっともだけど、かなしいかな、できることとできないことがあるのです。
LIMIT = 1_000_000
pfs = Array.new(LIMIT+1){ [] }
count = 0
2.upto(LIMIT){|d| # 0) LIMIT以下のすべての分母 d に対して、
print d,"\r"
count += d-1 # 1) とりあえず d-1 通りの分子を計上し、
d.step(LIMIT, d){|_| pfs[_] << d } if pfs[d].empty?
# 2) 8分の6など通分可能なものを差し引きする。
(1..(pfs[d].size)).each{|r|
cms = pfs[d].combination(r).map{|pf| pf.inject(&:*) }
count -= (-1)**(r%2+1) * cms.map{|cm| (d-1)/cm }.inject(&:+)
}
}
p count
Ruby 1.9からバックポートされてきた(のだと思われる見覚えのないメソッド) cycle, tap, combination, permutation, productといったメソッドが便利だ。あとは自然数を無限に生成し続ける無限リストのようなものをどれだけ簡単に書けるかだ。なにかショートカットがあるのだろうか。これでは長すぎる。
Enumerable::Enumerator.new(lambda{|&block| n=0; loop{ block.call n+=1 } }, :call).each{|x| p x }
それと、block.callの部分を yieldにできないのもわかりにくい。Procと blockと lambdaの微妙な違いによるものなのだろうか。
Rubyによる他所の Project Eulerの解答をみていてこういう書き方も知ってるけど、カウンタが Floatになっちゃうのが不満。
1.upto(1/0.0){|n| p n }
あれ？ Fixnumだ。Floatになるのは stepだった。
1.step(1/0.0){|n| p n } # 1.0, 2.0, 3.0,...
明示的に Fixnumの増分: 1を指定しても n は Float. この違いはなんだろう。
cycleの使い道として zipを想定していたが拒否されてしまった。
irb> [1,2,3,4,5].zip([0]) => 1, 0], [2, nil], [3, nil], [4, nil], [5, nil irb> [1,2,3,4,5].zip([0].cycle) TypeError: can't convert Enumerable::Enumerator into Array from (irb):2:in `zip' from (irb):2 from :0 irb> RUBY_DESCRIPTION => "ruby 1.8.7 (2010-01-10 patchlevel 249) [i386-mswin32]"