Вот два ответа, показывающие разные стили.Первый более быстрый (важен только для ОГРОМНЫХ размеров местности), но менее "Ruby-esque";вторая более функциональна, но создает дополнительные промежуточные данные.Для вашего лучшего образования, я призываю вас убедиться, что вы понимаете это полностью и выбираете, как поступить так, как вам лучше.
Кроме того, я предположил, что 21 у вас естьв вашем вопросе есть ошибка, и вы хотели иметь 2 там.
Во-первых, оба решения начинаются с одного и того же кода, который создает массив массивов для ландшафта:
# 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
Второе решение находит все подсетки, а затем использует Enumerable#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
На моем компьютере простой метод массива массивов занимает ~ 0,6 снайти самый низкий пул 3х3 в случайной местности 400 × 400, в то время как матричный метод занимает ~ 1,3 с.Таким образом, стиль матрицы более чем вдвое медленнее, но все же достаточно быстр для вашего задания.:)