Navigating Adjacent Cells in a Grid: An Exercise in 2D Traversal

Lesson 5

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 Python function named path_traverse. This function should perform a particularly ordered traversal through a 2D grid. The function will accept a grid, along with the starting cell coordinates, as parameters. Starting from the provided cell, the function should make moves in any one of the four possible directions toward an adjacent cell. However, a conditions govern 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 function will be a list that includes all the visited cell values in the order of their visitation.

Consider a 3x3 grid:


11 2 3
24 5 6
37 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 function 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 Python with the len() function. 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.

Python
1def path_traverse(grid, start_row, start_col):
2    rows, columns = len(grid), len(grid[0])
3    directions = [
4        (-1, 0),  # Up
5        (1, 0),   # Down
6        (0, -1),  # Left
7        (0, 1),   # Right
8    ]

In the directions list, each tuple 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).

Solution Building: Step 2

Once we have the grid's dimensions and the possible directions, we should validate the starting point and set up our visited cell recording mechanism.

Python
1def path_traverse(grid, start_row, start_col):
2    # Get the number of rows and columns in the grid
3    rows, columns = len(grid), len(grid[0])
4
5    # Check the validity of the input
6    if start_row < 0 or start_row >= rows or start_col < 0 or start_col >= columns:
7        return "Invalid input"
8
9    # Define all four possible directions of movement
10    directions = [(1, 0), (-1, 0), (0, -1), (0, 1)]
11    
12    # Start with the value at the starting cell
13    visited = [grid[start_row][start_col]]

Solution Building: Step 3

Let's initiate the grid traversal process in our function. We first set up an infinite loop that will only stop when we break it based on a condition.

Python
1while True:
2  # Initialize a current maximum as negative one 
3  curr_max = -1
4  # Loop over each adjacent cell in all the directions
5  for dir in directions:
6    # Placeholder code here
7    pass

Solution Building: Step 4

Inside the infinite loop, for each iteration, we'll have the function try to select the next cell with the maximum value among the adjacent cells. If we find such a cell, we'll capture its value, and it will be our next cell.

Python
1# Inside the loop
2for dir in directions:
3  # Calculate the new cell's row and column indices
4  new_row = start_row + dir[0]
5  new_col = start_col + dir[1]
6  
7  # If the new cell is out of the grid boundary, ignore it
8  if new_row < 0 or new_row >= rows or new_col < 0 or new_col >= columns:
9    continue
10
11  # If the new cell's value is greater than the current maximum
12  if grid[new_row][new_col] > curr_max:
13    # Save it as the next cell to visit
14    next_row, next_col, curr_max = new_row, new_col, grid[new_row][new_col]

Solution Building: Step 5

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

Python
1# If we don't have any valid cell to visit, break from the loop  
2if curr_max <= grid[start_row][start_col]: 
3  break
4# Otherwise, go to the next cell
5start_row, start_col = next_row, next_col
6
7# Append the cell's value to the result list
8visited.append(curr_max)

In the end, our beautiful function looks like this:

Python
1def path_traverse(grid, start_row, start_col):
2    # Get the number of rows and columns in the grid
3    rows, columns = len(grid), len(grid[0])
4
5    # Check the validity of the input
6    if start_row < 0 or start_row >= rows or start_col < 0 or start_col >= columns:
7        return "Invalid input"
8
9    # Define all four possible directions of movement
10    directions = [(1, 0), (-1, 0), (0, -1), (0, 1)]
11
12    # Start with the value at the starting cell
13    visited = [grid[start_row][start_col]]
14
15    # Start an infinite loop until we break it when there are no more moves
16    while True:
17        # Initialize a current maximum as negative one 
18        curr_max = -1
19
20        # Look at each adjacent cell in all the directions
21        for dir in directions:
22            # Calculate the new cell's row and column indices
23            new_row = start_row + dir[0]
24            new_col = start_col + dir[1]
25            
26            # If the new cell is out of the grid boundary, ignore it
27            if new_row < 0 or new_row >= rows or new_col < 0 or new_col >= columns:
28                continue
29
30            # If the value of the new cell is greater than the current maximum
31            if grid[new_row][new_col] > curr_max:
32                # Save it as the next cell to go to
33                next_row, next_col, curr_max = new_row, new_col, grid[new_row][new_col]
34
35        # If we don't have any valid cell we can go to, break from the loop   
36        if curr_max <= grid[start_row][start_col]: 
37            break
38          
39        # Otherwise, go to the next cell
40        start_row, start_col = next_row, next_col
41
42        # Append the value of the next cell to the result list
43        visited.append(curr_max)
44
45    # Return the list of visited cells' values    
46    return visited

Lesson Summary

Bravo! You've successfully solved a complex problem involving the traversal of a grid in a unique pattern. This function has tested not only your skills in Python programming but also your ability to visualize spatial patterns.

Having digested this knowledge, it's now time to test your understanding and apply these concepts to similar problems. Watch out for the ensuing practice session, where you can dabble with more challenging problems and refine your problem-solving skills. Keep up the good work and happy coding!

Enjoy this lesson? Now it's time to practice with Cosmo!

Practice is how you turn knowledge into actual skills.