最終更新: 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-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を使う(内部キー)かはやっぱり決めかねるけど。
最終更新: 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-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]"
最終更新: 2011-03-12T02:24+0900
分母を一番深いところから順番に計算していく。
a = ([2] + (1..33).map{|k| [1,2*k,1] }.inject(&:+)).reverse
denom, numer = *a.inject([0,1]){|nd, x| [nd[1], x*nd[1]+nd[0]] }
require 'rational'
p Rational(numer, denom).numerator.to_s.chars.inject(0){|sum,c| sum - ?0 + c[0] }
xを増やしながらの総当たりで、最後に見つかった Dが答え。と思ったんだけど Dが見つかるペースがどんどこ落ちていく。一日以上かけても 969個の Dのうち 270個が残ってる。
Problem 18の延長で以前解いた。
前問に引き続いて、数学でもプログラミングでもなく、オラクルで。
最終更新: 2011-03-12T03:46+0900
"exactly five" って書いてあるから、同じ数字の並べ替えで作れる立方数が 6以上あってもダメだと思うんだ。
memo = Hash.new{|h,k| h[k] = [] }
n = 0
k_length = 1
loop{
n += 1
cube = n*n*n
k = cube.to_s.split(//).sort.join('')
if k.length != k_length
answer = memo.values.select{|cubes| cubes.size == 5 }
if not answer.empty?
answer.each{|cubes| p cubes }
exit
end
memo.clear
k_length = k.length
end
memo[k] << cube
}
# (x-1)/x <= log10(n) < 1 (n = ?,?,...)
count = 0
x = 0
loop{
x += 1
boundary = (x-1.0)/x
lower_bound = (1..9).to_a.reverse.find{|n| Math.log10(n) < boundary } || 0
count += 9 - lower_bound
break if lower_bound == 9
}
p count
またまた「Dreamshire | Project Euler Problem 63 Solution」の解答を検討してみたい。二重のループなんてない。logの計算だって 9回だけ。どういうことだ？
というストーリーをひねり出した。「9は 10より 0.046(=1-0.954)程度小さい数だ」ってくだりがいかにも苦しい。小数だからごまかしがきいてるけど、ぴったり 10一個分小さくなる場合は n桁、n-1桁、どっち？ (たぶんまだ n桁だな。1^1がそう)
ともあれ、明かされてみればワンライナーの問題だったよ。
p (1..9).inject(0){|sum,n| sum + (1/(1-Math.log10(n))).floor }
常用対数を直接求めるメソッドが用意されてるあたりが Rubyだなとおもた。
連分数っていうらしい。a_nの求め方、a += 1 while 0 <= r - (n - d*(a+1))**2 の条件部分が判然としない。スクリプト中のコメントにあるように、対象としてるルートの係数が必ず約分されて 1になることも理解できてない。
def next_frac(r, n, d) # (√r + n) / d = a + 1 / [(√r + n_) / d_]
a = 0
a += 1 while 0 <= r - (n - d*(a+1))**2
d_ = (r - (n - d*a)**2) / d
raise if (r - (n - d*a)**2) % d != 0 # why OK?
n_ = -(n - d*a)
return a, r, n_, d_
end
def period_of(r)
rnd = [r, 0, 1]
arr = []
loop{
a, *rnd = next_frac(*rnd)
arr << rnd
period = arr.size-1 - arr.index(rnd)
return period if 0 != period
return 0 if rnd[2] == 0 # √r is rational.
}
end
count = 0
1.upto(10000){|n|
count += 1 if period_of(n) % 2 == 1
}
p count
ところで、この問題を解くときに Math.sqrtを使うのってインチキくさくない？(だから使ってないんだけど)
最終更新: 2011-03-02T05:24+0900
何も考えずにコーディングしただけ。一瞬 CPUが考え込みます。
generators = [
lambda{ n = 0
lambda{ n+=1; n*(n+1)/2 }
}.call,
lambda{ n = 0
lambda{ n+=1; n*n }
}.call,
lambda{ n = 0
lambda{ n+=1; n*(3*n-1)/2 }
}.call,
lambda{ n = 0
lambda{ n+=1; n*(2*n-1) }
}.call,
lambda{ n = 0
lambda{ n+=1; n*(5*n-3)/2 }
}.call,
lambda{ n = 0
lambda{ n+=1; n*(3*n-2) }
}.call,
]
# 数を準備
d4polynumbers = generators.map{|g|
() while (p = g.call) < 1000
a = [p]
a.push(p) while (p = g.call) < 10000
a
}
# 端緒(の集まり)
bunch_of_chain = d4polynumbers[d4polynumbers.size-1].map{|p|
[[p, d4polynumbers.size-1]]
}
# 端緒を伸ばすもの
extender = lambda{|chain, pool|
xx = chain.last.first.to_s[-2,2]
( (0...(pool.size)).to_a - chain.map{|_| _.last } ).map{|i|
[i, pool[i]]
}.map{|i, nums|
nums.find_all{|num|
num.to_s[0,2] == xx
}.map{|num|
chain + [[num, i]]
}
}.inject(&:+)
}
# 伸ばしていく
(d4polynumbers.size-1).times{
bunch_of_chain = bunch_of_chain.map{|chain|
extender[chain, d4polynumbers]
}.inject(&:+)
}
# 輪っか？
bunch_of_cyclic_chain = bunch_of_chain.reject{|chain|
chain.first.first.to_s[0,2] != chain.last.first.to_s[-2,2]
}
# 出力
bunch_of_cyclic_chain.each{|chain|
puts chain.map{|a,_| a }.join("\t")
puts chain.map{|_,b| "P#{b+3}" }.join("\t")
puts "sum: #{chain.map{|a,_| a }.inject(&:+)}"
}
先は長いのにもう失速してる。「良いもの。悪いもの。: Project Eulerを100問解いてみた」テトレーションとか聞いたこともない単語なんだけど……。
中学生の時に 3^{50} の一の位は何かという問題が出た。でも Problem 188は何乗したらいいかもわからない。下手の考え休むに似たりっていうけどどうしたもんかなあ。ない知恵を絞るのも悪くないと思うんだけど。
最終更新: 2011-02-20T21:45+0900
10%未満っていうのは絶妙なポイントなのかな。全然 9%未満に落ちない。
def prime? x
return false if x < 2
return true if x == 2
quo, rem = x.divmod(2)
return false if rem == 0
t = 1
while t < quo
t += 2
quo, rem = x.divmod(t)
return false if rem == 0
end
return true
end
x, t = 1, 0
primes_on_diagonals = 0
loop{
t += 2
3.times{
x += t
primes_on_diagonals += 1 if prime? x
}
x += t
puts "#{primes_on_diagonals} primes out of #{2*t+1} (#{100*primes_on_diagonals/(2*t+1)}%, side length=#{t+1})"
exit if 100 * primes_on_diagonals / (2*t+1) < 10
}
encrypted_text = [79,59,12,...,22,73,0,0] # last 2 elements are padding.
text = ""
0.step(encrypted_text.size-1, 3){|i|
text += (encrypted_text[i+0] ^ (71 ^ " "[0])).chr
text += (encrypted_text[i+1] ^ (79 ^ " "[0])).chr
text += (encrypted_text[i+2] ^ (68 ^ " "[0])).chr
}
text.chop!.chop! # remove padding
puts text
puts "sum: #{text.bytes.inject(:+)}"
1を満たす素数を発見しながらそれを使って、1の集合から2へ、2の集合から3へ、3の集合から4へ、要素をプロモートしていけばよさそう。
# 寝る前にやる。
寝てしまった。答えが出ない。素数を分割するんでなく、素数のペアを組み合わせて素数かどうか判定した方がいいかもしれない。そろそろ身にしみて理解してきたけど、素数って印象よりありふれ過ぎてる。
ちょっとくらい時間がかかってもいーやって考えてたけど、何日もかけても四つ組みが 7つと、五つ組が 0個しか見つからないことがわかったので、1分以内に答えを出すべくもうちょっと考える。
def prime? x
return false if x < 2
return true if x == 2
quo, rem = x.divmod(2)
return false if rem == 0
t = 1
while t < quo
t += 2
quo, rem = x.divmod(t)
return false if rem == 0
end
return true
end
set012 = [[],[3],[]]
require 'mathn'
Prime.new.each{|prime|
break if 10000 <= prime
dmod3 = prime.to_s.bytes.inject(0){|sum,byte| sum+byte-?0 } % 3
set012[dmod3] << prime
}
set1, set2 = set012[1], set012[2]
set2[0] = 3
# set1 = [3,7,13,...]
# set2 = [3,5,11,...]
make_group_of_two = lambda{|set|
pair = {}
0.upto(set.size-2){|i|
(i+1).upto(set.size-1){|j|
if prime?("#{set[i]}#{set[j]}".to_i) and prime?("#{set[j]}#{set[i]}".to_i)
(pair[[set[i]]]||=[]) << set[j]
end
}
}
return pair
}
group1, group2 = make_group_of_two.call(set1), make_group_of_two.call(set2)
extend_group = lambda{|g|
group = {}
g.each_pair{|rest, last1s| # rest + one of last1s = group
last1s.each{|last1|
next1s = last1s
gg, out = rest.clone, last1
gg.size.times{|i|
gg[gg.size-1-i], out = out, gg[gg.size-1-i]
next1s &= g[gg]||[]
}
if ! next1s.empty?
group[rest+[last1]] = next1s
end
}
}
return group
}
group1, group2 = extend_group.call(group1), extend_group.call(group2) # sets of 3 primes
group1, group2 = extend_group.call(group1), extend_group.call(group2) # sets of 4 primes
group1, group2 = extend_group.call(group1), extend_group.call(group2) # sets of 5 primes
printer = lambda{|rest, last1s|
last1s.each{|last1|
puts %[#{rest.inject(&:+)+last1}:\t#{rest.join("\t")}\t#{last1}]
}
}
group1.each(&printer)
group2.each(&printer)
分単位の時間で答えはでたけどもその五つ組の合計が意外に大きくて、10000以上の素数を組に加えても最小の組み合わせになりうる。計算量の増大の仕方がひどくて、これ以上桁数を増やして試行するのは無理だというのに。
じゃないよね。
\begin{array}{rcl}
q & = & a_0 + 10a_1 + 10^2a_2 +……+ 10^na_n \quad\mbox{(}a_n\mbox{は 0以上 9以下の整数)}\\
& = & (a_0 + a_1 + a_2 +……+ a_n) + 9a_1 + 99a_2 +……+(10^n-1)a_n\\
\end{array}
a_0+a_1+a_2+……+a_n が 3の倍数の整数 qは 3の倍数です。
たしか 4の倍数についても同じような判定規則があった気がした。忘れたけど。
たしか 5の倍数についてもどこかの桁を見るだけで(略
4は 100を作るから下2桁だけ。5は 10を作るから下1桁だけを見ればいい。
一番時間を食ってるのは make_group_of_two. 異なる二要素の組み合わせということで n^2-n 回の素数判定を行ってる。素数判定自体も nの大きさに比例する(※1:1ではないけど)ループを持っている。大変なはずだ。
とりあえず、今の素数判定より賢い素数判定があるのはわかってるけどわからないので使ってない。(注:わかる => 知ってる, 理解できる) 丁寧にコードを読んだらわかるかもだけどそれはチートっぽい。大学入試の数論関係の問題だって、解答をチラ見したら誰だって理解できんだよ。
最終更新: 2011-02-12T22:42+0900
Bignumはできれば使いたくない。aが 100未満なので 8桁ずつ。
answer = [0, 0, 0] # sum, a, b
1.upto(99){|a|
digits = "1"
1.upto(99){|b|
sum = 0
carry = 0
0.step(digits.size-1, 8) {|i|
l, r = [0, digits.size-i-8].max, digits.size-i
carry, digits8 = (digits[l...r].to_i * a + carry).divmod(100000000)
digits8 = "00000000#{digits8}"[-8,8]
digits[l...r] = digits8
digits8.each_byte{|byte|
sum += byte - ?0
}
}
if carry != 0
digits8 = carry.to_s
digits = digits8 + digits
digits8.each_byte{|byte|
sum += byte - ?0
}
end
if answer[0] < sum
*answer = sum, a, b
end
}
}
p answer
とかいいながら Bignum。
count = 0
numer, denom = 1, 1
1000.times{
numer, denom = numer + denom + denom, numer + denom
count += 1 if numer.to_s.length != denom.to_s.length
}
p count
最終更新: 2011-02-10T04:56+0900
ただただ、手と CPUを動かすだけで精一杯。(頭は役に立ってないよ)
primes = [2]
is_prime = lambda{|x|
result = true
primes.each{|prime|
quo, rem = x.divmod(prime)
if rem == 0
result = false
break
end
break if quo < prime
}
return result
}
# replace 2 digits or 3 digits. キ・メ・ウ・チ
def find_8_prime_family(a)
return [] if a.size < 8
a.map!{|x| x.to_s }
h = Hash.new{|h,k| h[k] = [] }
# 2 digits
0.upto(a.first.size-3){|i|
(i+1).upto(a.first.size-2){|j|
h.clear
a.each do |prime|
if prime[i] == prime[j]
h[prime[0...i]+prime[(i+1)...j]+prime[(j+1)...(prime.size)]].push prime
end
end
h.each do |_,v|
return v if v.size == 8
end
}
}
# 3 digits
0.upto(a.first.size-4){|i|
(i+1).upto(a.first.size-3){|j|
(j+1).upto(a.first.size-2){|k|
h.clear
a.each do |prime|
if prime[i] == prime[j] and prime[j] == prime[k]
h[prime[0...i]+prime[(i+1)...j]+prime[(j+1)...k]+prime[(k+1)...(prime.size)]].push prime
end
end
h.each do |_,v|
return v if v.size == 8
end
}
}
}
return []
end
x = 1
start = 0 # start of primes of a width.
loop {
x += 2
next unless is_prime.call x
print "#{x}\r"
if primes[start].to_s.length != x.to_s.length
a = find_8_prime_family primes.last(primes.size-start)
if ! a.empty?
puts a.sort.join(" ")
exit
end
start = primes.size
end
primes.push x
}
桁数ごとに探索範囲を決めて、総当たり。
問題が xについても同じ数の組み合わせであることを求めてると思わなくてチェックしてないけど、結果的に xも 2x,3xなんかと同じ数字で構成されてた。
digits = 10
loop {
digits *= 10
(digits/2).upto((digits*10-1)/6){|x|
print "#{x}\r"
x2 = (x*2).to_s.split(//).sort
if [3,4,5,6].all?{|n|
x2 == (x*n).to_s.split(//).sort
} then
puts [1,2,3,4,5,6].map{|n| x*n }.join(" ")
exit
end
}
}
浮動小数点数なんてファジーなものを使っちゃったよ。Math.sqrtの使用をこれまで頑なに避けてたのも、結果が Floatになるからだったり。
count = 0
23.upto(100){|n|
cmb = 1.0
1.upto(n/2){|r|
cmb /= r
cmb *= (n-r+1)
count += (n-r == r) ? 1 : 2 if 1_000_000 < cmb
}
}
p count
問題文が難しかった。3割ぐらいは推測。
あっけなく答えが出たので to_s.reverse.to_i みたいなのをなくすべく、Integer#reverse を自作してみたら、かえって遅くなったし。
class Integer
# 負数については考えてない。
def reverse
x = 0
this = self
begin
this, rem = this.divmod(10)
x = 10*x + rem
end while 0 < this
x
end
end
count = 0
10.upto(10_000-1){|x|
is_lychrel = true
50.times{
x = x + x.reverse
if x == x.reverse
is_lychrel = false
break
end
}
count += 1 if is_lychrel
}
p count