arrays - 如何优化在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

我们在 arr中定义一个沙漏是值的子集，而索引在 arr的图形表示中以这种模式落入:

a b c
  d
e f g

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

例如，给定2D数组:

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

我们最高的沙漏值(value)来自于沙漏:

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

一种选择是使用Matrix方法。

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中最佳沙漏的左上角的行和列索引。