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

Question

注意：这个问题提出了一个我已经解决的问题，但是我感觉我的解决方案非常基础，其他像我一样的人会受益于来自更有经验的开发者的讨论。不同的解决问题方法，以及更复杂的方法和算法将非常受欢迎。我认为这是学习如何用Ruby解决对初学者来说相当困难的问题的好地方。

给定一个6x6的二维数组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 = [
  [-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

- Richard Jarram

---

感谢@CarySwoveland的建议。我已经适当地编辑了问题。 - Richard Jarram

您不需要在结尾再次定义arr，因为它已经在之前定义过了。 （一般来说，请尽量格式化使读者不必横向滚动。）Ruby 的一个规范是使用 snake case 来命名 Ruby 变量和方法（例如，使用 hourglass_sum 而不是 hourglassSum）。当然，您不必遵循这个规范，但是如果不遵循的话，不要惊讶如果您看到一群愤怒的 Ruby 爱好者举着火炬和长叉走向您。 - Cary Swoveland

感谢@CarySwoveland，根据您的建议编辑了代码。 - Richard Jarram

“永远编写代码，就好像最终维护你的代码的人将是一个知道你住在哪里的暴力精神病患者。为可读性而编写代码。” — 约翰·伍兹 - the Tin Man

我建议检查一下是否"[codereview.se]"可能是更好的网站，或者更具有教育意义，可以优化代码。请查看它的"On-topic"信息以获取更多信息。 - the Tin Man

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

- Cary Swoveland

---

读者们：我本来期望 Matrix.build(4,4,&:itself) 能够运行，但是它却抛出了异常 #=> "...matrix.rb:103:in 'itself'; ArgumentError (wrong number of arguments (given 1, expected 0))。请问有人能够解释一下这个错误信息吗？ - Cary Swoveland

看起来，你传递给临时块作为方法调用的方法被传递了一个参数，但是这个方法本身并没有接受任何参数。基本上，“&:itself”等同于写“{|x| x.itself}”，但是你传递块的示例有两个参数。所以“&:”快捷方式在幕后构建了错误的代码，导致了参数错误。 - AJFaraday

在大多数情况下，生成的元素作为单个数组参数传递，并在遇到逗号时通过数组分解（在 hash.each { |key, value| } 中）隐式分配。如果 h = {a: 1}，那么 h.each { |e| p e } 将输出 [:a, 1]，因此 h.map(&:itself) #=> [[:a, 1]]。(1/2) - 3limin4t0r

Matrix::build 方法似乎不是这种情况。它似乎产生了两个单独的参数，而不是产生一个包含两个值的单一数组参数。Matrix.build(1, 1) { |e| p e } 输出 0（而不是 [0, 0]）。提供 Matrix.build(1, 1, &:itself) 将执行 Matrix.build(1, 1) { |i, j| :itself.to_proc.call(i, j) }，这相当于 Matrix.build(1, 1) { |i, j| i.itself(j) }。由于 Object#itself 不接受任何参数，因此您会遇到您遇到的消息。(2/2) - 3limin4t0r

...@3limin4t0r。3lim的等价性特别清晰。 - Cary Swoveland

Answer 2

这是我想出来的一个选项。

def width_height(matrix)
  [matrix.map(&:size).max || 0, matrix.size]
end

def sum_with_weight_matrix(number_matrix, weight_matrix)
  number_width, number_height = width_height(number_matrix)
  weight_width, weight_height = width_height(weight_matrix)

  width_diff  = number_width  - weight_width
  height_diff = number_height - weight_height

  0.upto(height_diff).map do |y|
    0.upto(width_diff).map do |x|
      weight_height.times.sum do |ry|
        weight_width.times.sum do |rx|
          weight = weight_matrix.dig(ry, rx) || 0
          number = number_matrix.dig(y + ry, x + rx) || 0
          number * weight
        end
      end
    end
  end
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],
]

weights = [
  [1, 1, 1],
  [0, 1, 0],
  [1, 1, 1],
]

sum_matrix = sum_with_weight_matrix(arr, weights)
#=> [
#   [-63, -34, -9, 12],
#   [-10,   0, 28, 23],
#   [-27, -11, -2, 10],
#   [  9,  17, 25, 18]
# ]
max_sum = sum_matrix.flatten.max
#=> 28

这个解决方案使用width_diff和height_diff创建一个输出矩阵（对于示例数据0.upto(6 - 3).to_a #=> [0, 1, 2, 3]，大小为4x4）。weight_matrix的索引（rx和ry）将被用作相对于较大的number_matrix的相对索引。

如果您的二维数组每个子数组始终具有相同数量的元素，则可以将matrix.map(&:size).max替换为matrix[0]&.size || 0以加快确定矩阵宽度的速度。当前的解决方案使用子数组的最大大小。子数组具有较小的大小将使用0表示缺少的元素，因此不会影响总和。

我的解决方案可能有点变量重。我这样做是为了有描述性的变量名，希望告诉您大部分需要知道的解决方案。当您觉得不需要它们时，可以缩短变量名称或完全删除它们。

如果有什么不清楚的，请在评论中提问。

- 3limin4t0r

Answer 3

不使用Matrix类，以下是我为任何任意矩形数组完成的方法：

offsets = [[-1, -1], [-1, 0], [-1, 1], [0, 0], [1, -1],  [1, 0],  [1, 1]]
sums = 1.upto(arr.length - 2).flat_map do |i|
  1.upto(arr[0].length - 2).map do |j|
    offsets.map {|(x, y)| arr[i+x][j+y] }.sum
  end
end

puts sums.max

我们感兴趣的值只是相对于当前位置的偏移量。我们可以通过一些行和列偏移量将数组中的值相对于当前位置映射出来，对它们求和，然后选择最大的总和。

- Chris Heald