CODEWITHSUNDEEP
arraysrubyselectmatrixdirection
vrintle
vrintle

Reputation: 5596

Most efficient way to select elements in 2d array in Ruby

Let's say I have 2d array (or matrix) like,

matrix = [
 [1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]
]

And, I've to select all elements in eight directions of a certain element matrix[i][j], so I know,

How to select those elements, easily and efficiently? Any direct method?

For example, if my element is 4, then my selection should yield, [1, 7, 5, 6, 2, 8]. If it is, 5, then selection should be all except 5.

Edit: I've coded any solution yet, as I thought it'll be very poor, but here is my idea. Try it online!

matrix = [
 [1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]
]

res = []
i = 0
j = 1

# let [i,j] be index of my element
matrix.each_with_index{|row,r| row.each_with_index{|col,c| 
    res << col if c == j || r == i || r+c == i+j || r-c == i-j 
}}

p res

Upvotes: 1

Views: 607

Answers (4)

Cary Swoveland
Cary Swoveland

Reputation: 110745

Code

def extract(matrix, row, col)
  last_row = matrix.size-1
  last_col = matrix.first.size-1
  diag_sum = row + col
  diag_first_row = diag_sum - [diag_sum, last_col].min
  diag_last_row  = [last_row, diag_sum].min
  ante_diag_diff = row - col
  ante_diag_first_row = [ante_diag_diff, 0].max
  ante_diag_last_row = ante_diag_diff +
    [last_col, last_row - ante_diag_diff].min
  arr = [] 
  (0..last_col).each { |j| arr << matrix[row][j] unless j == col }
  (0..last_row).each { |i| arr << matrix[i][col] unless i == row }
  (diag_first_row..diag_last_row).each do |i|
    arr << matrix[i][diag_sum - i] unless i == row
  end
  (ante_diag_first_row..ante_diag_last_row).each do |i|
    arr << matrix[i][i - ante_diag_diff] unless i == row
  end
  arr
end

Example

matrix = Array.new(5) { Array.new(5) { rand(10..99) } }
  #=> [[52, 29, 61, 35, 27],
  #    [68, 99, 67, 18, 67],
  #    [79, 10, 73, 15, 36],
  #    [49, 94, 28, 24, 53],
  #    [37, 26, 65, 65, 43]]

(0..4).each do |i|
  (0..4).each do |j|
    puts "#{i}, #{j}: #{extract(matrix,i,j)}"
  end
 end

i  j
----------------------------------------------------------------------
0, 0: [29, 61, 35, 27, 68, 79, 49, 37, 99, 73, 24, 43]
0, 1: [52, 61, 35, 27, 99, 10, 94, 26, 68, 67, 15, 53]
0, 2: [52, 29, 35, 27, 67, 73, 28, 65, 99, 79, 18, 36]
0, 3: [52, 29, 61, 27, 18, 15, 24, 65, 67, 10, 49, 67]
0, 4: [52, 29, 61, 35, 67, 36, 53, 43, 18, 73, 94, 37]

1, 0: [99, 67, 18, 67, 52, 79, 49, 37, 29, 10, 28, 65]
1, 1: [68, 67, 18, 67, 29, 10, 94, 26, 61, 79, 52, 73, 24, 43]
1, 2: [68, 99, 18, 67, 61, 73, 28, 65, 35, 10, 49, 29, 15, 53]
1, 3: [68, 99, 67, 67, 35, 15, 24, 65, 27, 73, 94, 37, 61, 36]
1, 4: [68, 99, 67, 18, 27, 36, 53, 43, 15, 28, 26, 35]

2, 0: [10, 73, 15, 36, 52, 68, 49, 37, 61, 99, 94, 65]
2, 1: [79, 73, 15, 36, 29, 99, 94, 26, 35, 67, 49, 68, 28, 65]
2, 2: [79, 10, 15, 36, 61, 67, 28, 65, 27, 18, 94, 37, 52, 99, 24, 43]
2, 3: [79, 10, 73, 36, 35, 18, 24, 65, 67, 28, 26, 29, 67, 53]
2, 4: [79, 10, 73, 15, 27, 67, 53, 43, 24, 65, 61, 18]

3, 0: [94, 28, 24, 53, 52, 68, 79, 37, 35, 67, 10, 26]
3, 1: [49, 28, 24, 53, 29, 99, 10, 26, 27, 18, 73, 37, 79, 65]
3, 2: [49, 94, 24, 53, 61, 67, 73, 65, 67, 15, 26, 68, 10, 65]
3, 3: [49, 94, 28, 53, 35, 18, 15, 65, 36, 65, 52, 99, 73, 43]
3, 4: [49, 94, 28, 24, 27, 67, 36, 43, 65, 29, 67, 15]

4, 0: [26, 65, 65, 43, 52, 68, 79, 49, 27, 18, 73, 94]
4, 1: [37, 65, 65, 43, 29, 99, 10, 94, 67, 15, 28, 49]
4, 2: [37, 26, 65, 43, 61, 67, 73, 28, 36, 24, 79, 94]
4, 3: [37, 26, 65, 43, 35, 18, 15, 24, 53, 68, 10, 28]
4, 4: [37, 26, 65, 65, 27, 67, 36, 53, 52, 99, 73, 24]

Explanation

First observe that if the target element is in row i and column j, the elements [p,q] on the diagonal that passes through that point have the property that p+q == i+j. Similarly, the elements [p,q] on the ante-diagonal that passes through that point have the property that p-q == i-j

Suppose

row = 1
col = 2

then

last_row = matrix.size-1
  #=> 4 
last_col = matrix.first.size-1
  #=> 4 

diag_sum = row + col
  #=> 3 
diag_first_row = diag_sum - [diag_sum, last_col].min
  #=> 0 
diag_last_row  = [last_row, diag_sum].min
  #=> 3 

ante_diag_diff = row - col
  #=> -1 
ante_diag_first_row = [ante_diag_diff, 0].max
  #=> 0 
ante_diag_last_row = ante_diag_diff +
  [last_col, last_row - ante_diag_diff].min
  #=> 3

The remaining calculations are straightforward.

Here's a variant of the above that uses less code and may be slightly less efficient.

def extract(matrix, row, col)
  row_range = 0..matrix.size-1
  col_range = 0..matrix.first.size-1
  diag_sum = row + col
  ante_diag_diff = row - col
  arr = [] 
  col_range.each { |j| arr << matrix[row][j] unless j == col }
  row_range.each do |i|
     next if i == row
     arr << matrix[i][col]
     j = diag_sum - i
     arr << matrix[i][j] if col_range.cover?(j)
     j = i - ante_diag_diff
     arr << matrix[i][j] if col_range.cover?(j)         
  end
  arr
end

Upvotes: 2

iGian
iGian

Reputation: 11193

A recursive way

I'd like to propose a different approach, not tested if it is more or less efficient but can provide some control on order and more.

Lets start with this matrix, where elements tell their indexing:

mat = [
  ['00', '01', '02'],
  ['10', '11', '12'],
  ['20', '21', '22'],
  ['30', '31', '32']
]

And define an helper method just to get the shape of the matrix and to check which is well formed:

def shape(mat)
  raise 'Out of shape' if mat.map(&:size).uniq.size > 1
  return mat.size, mat[0].size
end

Implementation

Now, let's define a method that takes as input the starting point, the limits of the matrix (shape) and the direction.

def walk(i_0, j_0, i_max, j_max, direction, res=[])
  d_i, d_j = direction
  next_step = [i_0 + d_i, j_0 + d_j]
  if [-1, i_max].include?(next_step[0]) || [-1, j_max].include?(next_step[1])
    return res
  end
  res << next_step
  i_0, j_0 = next_step
  walk(i_0, j_0, i_max, j_max, direction, res)
end

The method returns the list of indexes starting from the origin and walking along the direction.

Usage examples

Example 1

i_0, j_0 = [2, 0]
i_max, j_max = shape(mat)
direction = [-1, 1]
walk(i_0, j_0, *shape(mat), direction)
#=> [[1, 1], [0, 2]]

Example 2

You can use it to extract the indexes given a list of directions.

It's possible to arrange the list of directions to give a scan order (clockwise, cclockwise) or just skip some directions, as you will.

directions = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]

i_0, j_0 = [2, 0]
directions = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]
directions.flat_map { |direction| walk(i_0, j_0, *shape(mat), direction) }
#=> [[3, 0], [1, 0], [0, 0], [2, 1], [2, 2], [3, 1], [1, 1], [0, 2]]

Example 3

(Which is an extension of example 2) You can directly get the elements from the matrix:

res = directions.flat_map do |direction|
  walk(i_0, j_0, *shape(mat), direction).map do |coords|
    i, j = coords
    mat[i][j]
  end
end

res
#=> ["30", "10", "00", "21", "22", "31", "11", "02"]

It can be possible to use a longer step (eg. direction = [2, 2]) upgrading the walk method.

Upvotes: 0

Salil
Salil

Reputation: 47532

Here is sample code, you can modify/simplify it further

class Matrix
  attr_reader :arr, :ele

  def initialize(arr, ele)
    @arr = arr
    @ele = ele
  end

  def find_elements
    position = arr.flatten.index(ele)
    len = arr.length
    x = position % len
    y = position / len
    horizontal_elements(y) + vertical_elements(x, y, len) + remaining_elements(x, y, len)
  end

  def horizontal_elements y
    arr[y] - [ele]
  end

  def vertical_elements x, y, len
    rows = (0..(len-1)).to_a - [y]
    rows.map{|row| arr[row][x] }
  end

  def remaining_elements(x, y, len)
    rows = []
    rows << y + 1 if y + 1 < len
    rows << y - 1 if y - 1 >= 0
    c_rows = []
    c_rows << x + 1 if x + 1 < len
    c_rows << x - 1 if x - 1 >= 0
    rows.map{|row| c_rows.map{|c_row| arr[row][c_row] } }.flatten
  end
end

matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]
ele = 4
(1..9).each do |i|
  puts '*' * 20
  puts "For #{i}"
  puts Matrix.new(matrix, i).find_elements.inspect
  puts '*' * 20
end

O/P will be something like following

Desktop $ ruby something.rb
********************
For 1
[2, 3, 4, 7, 5]
********************
********************
For 2
[1, 3, 5, 8, 6, 4]
********************
********************
For 3
[1, 2, 6, 9, 5]
********************
********************
For 4
[5, 6, 1, 7, 8, 2]
********************
********************
For 5
[4, 6, 2, 8, 9, 7, 3, 1]
********************
********************
For 6
[4, 5, 3, 9, 8, 2]
********************
********************
For 7
[8, 9, 1, 4, 5]
********************
********************
For 8
[7, 9, 2, 5, 6, 4]
********************
********************
For 9
[7, 8, 3, 6, 5]
********************

Upvotes: 1

ray
ray

Reputation: 5552

m is the matrix you have taken from a user that is a symmetric or non-symmetric 2-dimensional array.

# inputs
m = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]
p, q = 1, 0 # co-ordinate of number 4

# code for output
i, j, result = m.size, m[0].size, []

i.times { |r| result.push(m[r][q]) if r != p }
j.times { |c| result.push(m[p][c]) if c != q }
i.times do |r|
    j.times do |c|
        result.push(m[r][c]) if [p,q] != [r,c] && (p-r).abs == (q-c).abs
    end
end
> result
 => [1, 7, 5, 6, 2, 8]

Note: if the order of output is not needed to be preserved, we can manage with only 2 loops

Upvotes: 2

Related Questions