这里有两个不同风格的答案。 第一种是较快的(只对科索沃地理统计局的地形面积很重要),但“Ruby-esque”则不太重要;第二种是功能更强,但会产生额外的中间数据。 为了让你自己接受最好的教育,我鼓励你确保充分了解这些内容,并选择如何以最适合你的方式开展这项工作。
Also, I ve assumed that the 21 you have in your question is a mistake, and you meant to have a 2 there.
第一,这两种解决办法首先采用相同的法典,为地形形成一系列阵列:
# Load the text file as an array of strings
lines = IO.readlines( pool.txt )
# Turn it into an array of arrays of numbers
terrain = lines.map{ |s| s.scan(/d+/).map(&:to_i) }
# Throw out the silly grid size; we ll infer it from real data instead!
terrain.shift
# Take the last line (pool size) out of the terrain
pool_size = terrain.pop.first
第一种解决办法穿透地形,计算每个次电网的平均数,跟踪最低数字:
# For fun, we ll allow terrain that doesn t have to be square
rows = terrain.length
cols = terrain.first.length
best_size = Float::INFINITY
0.upto(rows-pool_size-1) do |y|
0.upto(cols-pool_size-1) do |x|
# x,y is the upper left corner of a valid pool_size × pool_size grid
average = 0.0
0.upto(pool_size-1) do |m|
0.upto(pool_size-1) do |n|
# Add up each point in the sub-grid
average += terrain[y+n][x+m]
end
end
# The number of points we added is the square of the size
average /= (pool_size*pool_size)
# Mark this as the best seen so far
best_size = average if average < best_size
end
end
p best_size
#=> 1.25
第二种解决办法是所有次网,然后使用Evidable#min_by 。 找到最佳方法。 我们还制定了计算一系列数字平均数的方法,仅用于计算单数和自律法:
# See http://ruby-doc.org/stdlib-1.9.3/libdoc/matrix/rdoc/Matrix.html
require matrix
class Matrix
# Average all values in the array (as a float)
def average
parts = to_a.flatten
parts.inject(:+) / parts.length.to_f
end
end
# Hey look, a nice 2D grid of elevations!
terrain = Matrix[ *terrain ]
# Create an array of matrices, each one representing a possible pool
rows = 0...(terrain.row_size - size)
cols = 0...(terrain.column_size - size)
pools = rows.flat_map{|x| cols.map{ |y| terrain.minor(x,size,y,size) } }
# Find the lowest pool by calling the above average method on each
lowest = pools.min_by(&:average)
p lowest, lowest.average
#=> Matrix[[1, 1], [1, 2]]
#=> 1.25
On my computer the simple array-of-arrays method takes ~0.6s to find the lowest 3x3 pool in a random 400×400 terrain, while the matrix technique takes ~1.3s. So the matrix style is more than twice as slow, but still plenty fast for your assignment. :)
