/ 最近 .rdf 追記 編集 設定 本棚

脳log[20110811] Problem 96, Problem 97, Problem 99, Problem 93



2011年08月11日 (木) [Ruby] 配列などコンテナとその要素をまとめて freeze! する freeze! メソッドが欲しい。

最終更新: 2011-08-20T02:11+0900

[ProjectEuler] Problem 96, Problem 97, Problem 99, Problem 93

 Problem 96

ナンバープレイス。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.

 Problem 97

Bignumがある Rubyでは関係ないけど、64ビット整数を前提に小細工(ループ展開)。

ten = 56866
978807.times{
	ten = (ten * 256) % 10000000000
}
p (ten + 1) % 10000000000

 Problem 99

場違いに簡単な問題。

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.

 Problem 93

スクリプトは不完全。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."