Ordered Grid Traversal in Scala

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 making 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 Scala method named pathTraverse . 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 would halt when there are no cells left that satisfy our criteria. The final result of the method will be a list that includes all the visited cell values in the order of their visitation. Consider a 3x3 grid: text 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 that 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 Scala using the .length property. 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. Scala def pathTraverse(grid: Array[Array[Int]], startRow: Int, startCol: Int): List[Int] = {val rows = grid.length val columns = grid(0).length val directions = List((-1, 0), // Up (1, 0), // Down (0, -1), // Left (0, 1) // Right)} In the directions list, each tuple represents a direction in terms of a pair (rowOffset, colOffset) . 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 loop and return the list of visited cells' values.

Scala

// If we don't have any valid cell to visit, break from the loop  
if (currMax <= grid(startRow)(startCol)) { 
  return visited
}
// Otherwise, go to the next cell
val nextRow = startRow + dir._1
val nextCol = startCol + dir._2

// Append the cell's value to the result list
visited :+= currMax

// If we don't have any valid cell to visit, break from the loop  
if (currMax <= grid(startRow)(startCol)) { 
  return visited
}
// Otherwise, go to the next cell
val nextRow = startRow + dir._1
val nextCol = startCol + dir._2

// Append the cell's value to the result list
visited :+= currMax

In the end, our beautiful method looks like this:

Scala

def pathTraverse(grid: Array[Array[Int]], startRow: Int, startCol: Int): List[Int] = {
  // Get the number of rows and columns in the grid
  val rows = grid.length
  val columns = grid(0).length

  // Check the validity of the input
  if (startRow < 0 || startRow >= rows || startCol < 0 || startCol >= columns) {
    return List("Invalid input".toInt)
  }

  // Define all four possible directions of movement
  val directions = List((1, 0), (-1, 0), (0, -1), (0, 1))

  // Start with the value at the starting cell
  var visited = List(grid(startRow)(startCol))

  // Start a loop until we have no more moves
  while (true) {
    // Initialize a current maximum as negative one 
    var currMax = -1
    var nextRow = startRow
    var nextCol = startCol

    // Look at each adjacent cell in all the directions
    for (dir <- directions) {
        // Calculate the new cell's row and column indices
        val newRow = startRow + dir._1
        val newCol = startCol + dir._2
            
        // If the new cell is out of the grid boundary, ignore it
        if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= columns) {
            continue
        }

        // If the value of the new cell is greater than the current maximum
        if (grid(newRow)(newCol) > currMax) {
            // Save it as the next cell to go to
            currMax = grid(newRow)(newCol)
            nextRow = newRow
            nextCol = newCol
        }
    }

    // If we don't have any valid cell we can go to, break from the loop   
    if (currMax <= grid(startRow)(startCol)) {
      return visited
    } else {
      startRow = nextRow
      startCol = nextCol

      // Append the value of the next cell to the result list
      visited :+= currMax
    }
  }

  visited
}

def pathTraverse(grid: Array[Array[Int]], startRow: Int, startCol: Int): List[Int] = {
  // Get the number of rows and columns in the grid
  val rows = grid.length
  val columns = grid(0).length

  // Check the validity of the input
  if (startRow < 0 || startRow >= rows || startCol < 0 || startCol >= columns) {
    return List("Invalid input".toInt)
  }

  // Define all four possible directions of movement
  val directions = List((1, 0), (-1, 0), (0, -1), (0, 1))

  // Start with the value at the starting cell
  var visited = List(grid(startRow)(startCol))

  // Start a loop until we have no more moves
  while (true) {
    // Initialize a current maximum as negative one 
    var currMax = -1
    var nextRow = startRow
    var nextCol = startCol

    // Look at each adjacent cell in all the directions
    for (dir <- directions) {
        // Calculate the new cell's row and column indices
        val newRow = startRow + dir._1
        val newCol = startCol + dir._2
            
        // If the new cell is out of the grid boundary, ignore it
        if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= columns) {
            continue
        }

        // If the value of the new cell is greater than the current maximum
        if (grid(newRow)(newCol) > currMax) {
            // Save it as the next cell to go to
            currMax = grid(newRow)(newCol)
            nextRow = newRow
            nextCol = newCol
        }
    }

    // If we don't have any valid cell we can go to, break from the loop   
    if (currMax <= grid(startRow)(startCol)) {
      return visited
    } else {
      startRow = nextRow
      startCol = nextCol

      // Append the value of the next cell to the result list
      visited :+= currMax
    }
  }

  visited
}

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