如何优化在 Ruby 中解析二维数组的代码

Question

注意：这个问题提出了一个我已经解决的问题，但是我觉得我的解决方案非常初级，其他人，比如我自己，会从更有经验的开发人员的意见的讨论中受益。解决问题的不同方法，以及更复杂的方法和算法将不胜感激。我觉得这是一个学习 Ruby 如何解决我认为对初学者来说相当困难的问题的好地方。

给定一个 6x6 2D 数组arr：

1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

我们将沙漏 in 定义arr为值的子集，其中的索引属于 inarr的图形表示中的这种模式：

a b c
  d
e f g

有 16 个沙漏，arr沙漏总和是沙漏值的总和。计算 中每个沙漏的沙漏总和arr，然后打印最大沙漏总和。

例如，给定二维数组：

arr = [
  [-9, -9, -9,  1, 1, 1], 
  [ 0, -9,  0,  4, 3, 2],
  [-9, -9, -9,  1, 2, 3],
  [ 0,  0,  8,  6, 6, 0],
  [ 0,  0,  0, -2, 0, 0],
  [ 0,  0,  1,  2, 4, 0]
]

我们计算以下沙漏值：

-63, -34, -9, 12, 
-10, 0, 28, 23, 
-27, -11, -2, 10, 
9, 17, 25, 18

我们最高的沙漏值来自沙漏：

0 4 3
  1
8 6 6

我的解决办法是：

def hourglass_sum(arr)
  hourglasses = []

  arr.each_with_index do |row, i|
    # rescue clause to prevent iterating outside the array
    unless arr[i].nil?

      arr[i].length.times do |iteration|
        # generate n 3x3 arrays
        r1 = arr[i][iteration...iteration+3]
        r2 = arr[i+1][iteration...iteration+3] if arr[i+1] != nil
        r3 = arr[i+2][iteration...iteration+3] if arr[i+2] != nil

        # rescue clause to stop creating 3x3 arrays that fall outside given input array
        if arr[i+1] != nil && arr[i+2] != nil
          # take all values except indices 0 and 5 from the 9 element array
          result = r1 + [r2[1]] + r3
          hourglasses << result.sum unless result.include? nil
        end
      end
    end
  end
  p hourglasses.max
end

arr = [[-9, -9, -9, 1, 1, 1], [0, -9,  0,  4, 3, 2], [-9, -9, -9, 1, 2, 3], [0, 0, 8, 6, 6, 0], [0, 0 ,0, -2, 0, 0], [0, 0, 1, 2, 4, 0]]

hourglass_sum(arr)
# => 28

Answer 1

一种选择是使用矩阵方法。

require 'matrix'

ma = Matrix[*arr]
  #=> Matrix[[-9, -9, -9,  1, 1, 1],
  #          [ 0, -9,  0,  4, 3, 2],
  #          [-9, -9, -9,  1, 2, 3],
  #          [ 0,  0,  8,  6, 6, 0],
  #          [ 0,  0,  0, -2, 0, 0],
  #          [ 0,  0,  1,  2, 4, 0]] 

mi = Matrix.build(6-3+1) { |i,j| [i,j] }
  #=> Matrix[[[0, 0], [0, 1], [0, 2], [0, 3]],
  #          [[1, 0], [1, 1], [1, 2], [1, 3]],
  #          [[2, 0], [2, 1], [2, 2], [2, 3]],
  #          [[3, 0], [3, 1], [3, 2], [3, 3]]]

def hourglass_val(r,c,ma)
  mm = ma.minor(r,3,c,3)
  mm.sum - mm[1,0] - mm[1,2]
end

max_hg = mi.max_by { |r,c| hourglass_val(r,c,ma) }
  #=> [1,2] 
hourglass_val(*max_hg,ma)
  #=> 28

[1,2]是 中最佳沙漏左上角的行索引和列索引arr。