最終更新: 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."