Unique Grid Traversal with Ruby Methods

Introduction

Hello, and welcome back to our coding lesson series. In this unit, we have a fascinating problem at hand that uses the concept of 2D arrays or grids . What's interesting about this problem is that it involves not only the simple traversal of the grid but also performing this traversal in a unique manner. Initially, the concept might seem a bit tricky, but as we dissect the task and take it step by step, you're sure to enjoy how it unfolds. Are you ready to embark on this adventure? Let's dive right in!

Task Statement

The task before us involves the creation of a Ruby method named path_traverse . This method should perform a particularly ordered traversal through a 2D grid. The method will accept a grid, along with the starting cell coordinates, as parameters. Starting from the provided cell, the method should make moves in any one of the four possible directions toward an adjacent cell. However, a condition governs this selection: the new cell value should be strictly greater than the current cell's value. This pattern would continue as we keep selecting the next available larger cell value. The traversal will halt when there are no cells left that satisfy our criteria. The final result of the method will be an array that includes all the visited cell values in the order of their visitation. Consider a 3x3 grid: 1 2 3 4 5 6 7 8 9 If we start at the cell with the value 5, we can logically move to either 6 or 8 . Let's say we choose 6; the only cell we can now move to is 9 . After this, we have no more moves left that fit our criteria. Hence, the method returns [5, 6, 9] .

Solution Building: Step 1

The first thing we need to do is determine the dimensions of our grid, which is relatively easy in Ruby with properties like size . We can also establish the directions that our traversal can take. In the context of matrices, when we say we are moving "up," we are moving one step towards the first row (decreasing the row index). Similarly, moving "down" corresponds to moving one step towards the last row (increasing the row index), and moving left or right relates to decrementing or incrementing the column index, respectively. Ruby def path_traverse(grid, start_row, start_col) rows = grid.size columns = grid[0].size directions = [[-1, 0], # Up [1, 0], # Down [0, -1], # Left [0, 1] # Right] In the directions array, each sub-array represents a direction in terms of a pair [row_offset, col_offset] . So, if we are at a cell (r, c), moving up corresponds to going to the cell (r-1, c), moving down corresponds to (r+1, c), moving left corresponds to (r, c-1), and moving right corresponds to (r, c+1) .

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 5

Finally, if there are no valid neighboring cells to visit, we'll break our infinite loop and return the list of visited cells' values.

Ruby

# If we don't have any valid cell to visit, break from the loop  
if curr_max <= grid[start_row][start_col]
  break
end
# Otherwise, go to the next cell
start_row, start_col = next_row, next_col

# Append the cell's value to the result list
visited << curr_max

# If we don't have any valid cell to visit, break from the loop  
if curr_max <= grid[start_row][start_col]
  break
end
# Otherwise, go to the next cell
start_row, start_col = next_row, next_col

# Append the cell's value to the result list
visited << curr_max

In the end, our beautiful method looks like this:

Ruby

def path_traverse(grid, start_row, start_col)
  rows = grid.size
  columns = grid[0].size

  return "Invalid input" if start_row < 0 || start_row >= rows || start_col < 0 || start_col >= columns

  directions = [[1, 0], [-1, 0], [0, -1], [0, 1]]
  visited = [grid[start_row][start_col]]

  loop do
    curr_max = -1

    directions.each do |dir|
      new_row = start_row + dir[0]
      new_col = start_col + dir[1]

      next if new_row < 0 || new_row >= rows || new_col < 0 || new_col >= columns

      if grid[new_row][new_col] > curr_max
        next_row, next_col, curr_max = new_row, new_col, grid[new_row][new_col]
      end
    end

    if curr_max <= grid[start_row][start_col]
      break
    end

    start_row, start_col = next_row, next_col
    visited << curr_max
  end

  visited
end

def path_traverse(grid, start_row, start_col)
  rows = grid.size
  columns = grid[0].size

  return "Invalid input" if start_row < 0 || start_row >= rows || start_col < 0 || start_col >= columns

  directions = [[1, 0], [-1, 0], [0, -1], [0, 1]]
  visited = [grid[start_row][start_col]]

  loop do
    curr_max = -1

    directions.each do |dir|
      new_row = start_row + dir[0]
      new_col = start_col + dir[1]

      next if new_row < 0 || new_row >= rows || new_col < 0 || new_col >= columns

      if grid[new_row][new_col] > curr_max
        next_row, next_col, curr_max = new_row, new_col, grid[new_row][new_col]
      end
    end

    if curr_max <= grid[start_row][start_col]
      break
    end

    start_row, start_col = next_row, next_col
    visited << curr_max
  end

  visited
end

Introduction

Task Statement

Solution Building: Step 1

Join the 1M+ learners on CodeSignal

Solution Building: Step 2

Solution Building: Step 3

Solution Building: Step 4

Solution Building: Step 5

Lesson Summary