How to optimise code that parses a 2-d array in Ruby

user_10565289 0
Viewed 215

Note: This question poses a problem that I have already solved, however I feel my solution is very rudimentary and that other people, like myself, would benefit from a discussion with input from more experienced developers. Different approaches to solving the problem, as well as more sophisticated methods and algorithms would be really appreciated. I feel this is a good place to learn how Ruby can tackle what I consider to be a fairly difficult problem for a beginner.

Given a 6x6 2D Array 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

We define an hourglass in arr to be a subset of values with indices falling in this pattern in arr's graphical representation:

a b c
  d
e f g

There are 16 hourglasses in arr and an hourglass sum is the sum of an hourglass' values. Calculate the hourglass sum for every hourglass in arr, then print the maximum hourglass sum.

For example, given the 2D array:

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]
]

We calculate the following hourglass values:

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

Our highest hourglass value is from the hourglass:

0 4 3
  1
8 6 6

My solution is:

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
multidimensional-array ruby arrays algorithm
3 Answers

One option is to use Matrix methods.

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] are the row and column indices of the top-left corner of an optimal hourglass in arr.

user_2569700

Here is an option I came up with.

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

This solution uses the width_diff and height_diff to create an output matrix (4x4 for the sample data 0.upto(6 - 3).to_a #=> [0, 1, 2, 3]). The indexes of the weight_matrix (rxand ry) will be used as relative index compared to the larger number_matrix.

If your 2d array always has the same number of elements for each sub-array you can replace matrix.map(&:size).max with matrix[0]&.size || 0 to speed up determining the matrix width. The current solution uses the maximum size of the sub-arrays. Sub-arrays having a smaller size will use 0 for the missing elements thus not effecting the sum.

My solution might be a bit variable heavy. I've done this to have descriptive variable names, that hopefully tell you most you need to know about the solution. You can shorten variable names, or remove them completely when you feel like you don't need them.

If something isn't clear just ask away in the comments.

user_39825620

Without using the Matrix class, here's how I've done it for any arbitrary rectangular array:

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

The values we're interested in are just offsets from a current position. We can map out the values in the array relative to the current position by some row and column offset, sum them, then select the max of the sums.

user_2714750
Related