Analyzing 2D Matrix Traversals with Ruby

Introduction

Hello, aspiring Ruby programmer! Are you ready to journey into the world of matrices? Today, we will explore the realm of 2D matrices with a unique traversal order that promises excitement and intrigue. Fasten your seatbelt and let's dive in!

Task Statement

Imagine we have a 2D matrix where each cell contains a distinct symbol or integer. Our task is to decode this matrix by reading the cells in a particular pattern. The decoding begins from the top-left cell of the matrix. We move in a diagonal direction toward the bottom-left until we reach the left boundary. Upon hitting the left boundary, we move one cell down (unless we're at the bottom-left corner, in which case we move one cell to the right) and begin moving diagonally upward toward the upper-right. While moving diagonally upward, if we hit the top boundary, we move one cell to the right and start going downwards diagonally. If we hit the right boundary while moving upwards, we move one cell down and resume a bottom-left diagonal path. In essence, we zigzag across the matrix diagonally until every cell is traversed. Once we finish this zigzag traversal, we'll process the list of visited cell values to uncover the indices of perfect square numbers. The diagonal_traverse_and_squares(matrix) function should implement this traversal and return a list of positions of perfect squares in the traversed sequence. Take a 3x4 matrix, for example: plaintext [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]] Following the diagonal traversal, we get the list: [1, 5, 2, 3, 6, 9, 10, 7, 4, 8, 11, 12] . From this list, 1, 9, and 4 are the perfect squares found at the 1st, 6th, and 9th positions. Thus, our function returns: [0, 5, 8] (since indexing is 0-based).

Solution Building: Step 1

Firstly, let's explore the dimensions of the 2D matrix using Ruby's length method. We need to establish the landscape of our matrix by determining the number of rows and columns. Next, we initialize two arrays: traversal and results . The traversal array holds the values from the matrix captured during our distinctive diagonal zigzag path. Later, the results array is filled with the positions of the perfect square numbers found in the traversal array. Ruby def diagonal_traverse_and_squares(matrix) rows = matrix.length cols = matrix[0].length traversal = [] results = []

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Solution Building: Step 2

The next step involves executing the diagonal traversal of the 2D matrix. We begin at the top-left corner (cell [0][0]) and navigate through the matrix using two variables, row and col, to track the cell indices. An additional dir variable is set to 1, indicating that the starting direction is downward-left.

However, transitioning diagonally isn't straightforward; matching the matrix boundaries requires us to adjust our direction. In Ruby, a times loop iterates for the total number of cells, and we use conditional statements to control the direction and ensure we respect the matrix edges.

Ruby

  row = col = 0
  dir = 1
  (rows * cols).times do
    traversal << matrix[row][col]
  
    if dir == 1 # Moving down-left
      if row == rows - 1
        col += 1
        dir = -1
      elsif col == 0
        row += 1
        dir = -1
      else
        row += 1
        col -= 1
      end
    else # Moving up-right
      if col == cols - 1
        row += 1
        dir = 1
      elsif row == 0
        col += 1
        dir = 1
      else
        row -= 1
        col += 1
      end
    end
  end

  row = col = 0
  dir = 1
  (rows * cols).times do
    traversal << matrix[row][col]
  
    if dir == 1 # Moving down-left
      if row == rows - 1
        col += 1
        dir = -1
      elsif col == 0
        row += 1
        dir = -1
      else
        row += 1
        col -= 1
      end
    else # Moving up-right
      if col == cols - 1
        row += 1
        dir = 1
      elsif row == 0
        col += 1
        dir = 1
      else
        row -= 1
        col += 1
      end
    end
  end

Moving Down-Left (dir == 1)

If at the last row:
- Move right (col += 1)
- Change direction to up-right (dir = -1)
If at the first column:
- Move down (row += 1)
- Change direction to up-right (dir = -1)
Otherwise:
- Move diagonally down-left (row += 1, col -= 1)

Moving Up-Right (else)

If at the last column:
- Move down (row += 1)
- Change direction to down-left (dir = 1)
If at the first row:
- Move right (col += 1)
- Change direction to down-left (dir = 1)
Otherwise:
- Move diagonally up-right (row -= 1, col += 1)

Introduction

Task Statement

Solution Building: Step 1

Join the 1M+ learners on CodeSignal

Solution Building: Step 2

Solution Building: Step 3

Lesson Summary